[informatik-bonn] Re: aufgaben
- From: Markus Hirsch <hirschmarkus@xxxxxx>
- To: "'informatik-bonn@xxxxxxxxxxxxx'" <informatik-bonn@xxxxxxxxxxxxx>
- Date: Wed, 11 Jun 2003 16:27:54 +0200
Hi,
> habe gerade rausgefunden, das es doch funktioniert. Evtl. wird aus
> meinem neuen Beweis verstandlich warum.
Ah... nein. Kurze Anmerkung: laut Aussage vom Blum ist es ihm egal, dass
bei seinem Algorithmus eine Grammatik mit Produktionen entsteht, die teilweise
ins Nirvana fuehren, bzw. fuhren koennen (naemlich dann, wenn die \beta_i
ausschlie?lich nach \epsilon fuehren). Da die Produktionen \beta_i -> epsilon
ja nicht in P' landen, ist die Grammatik zwar epsilon-frei, enthaelt aber auch
Produktionen, die nicht aufgeloest werden koennen.
Natuerlich kann man diejenigen, die ausschliesslich nach epsilon fuehren,
anschliessend wieder rausreduzieren. BTW: Produktionen A -> epsilon werden in P'
gar nicht erst aufgenommen, deswegen funktioniert Dein zweiter Schritt so nicht
ganz.
Das Prinzip ist aber natuerlich richtig.
Ich sehe allerdings noch ein Problem, wenn
Du Produktionen der Form \beta_i -> epsilon|b_i hast, b_i in V^+.
Dann kriegst Du die Produktionen in P', die aus A -< beta_1...beta_n c
entstehen,
IMO nicht mehr weg -> Du hast am Ende immer noch exponentiell mehr Produktionen
als vorher, weil Du eben sowohl den Fall, dass du beta_i durch epsilon ersetzt,
als
auch den, dass du beta_i durch b_i ersetzt, beruecksichtigen musst.
> Da du ja anscheinend
> mit dem CVS Probleme hast, habe ich dir das .ps mal perl mail
> zugeschickt.
Ahm... Mein Problem mit dem CVS ist, dass nach meinem Verstaendnis doch
ein Passwort fuer den Zugang zum Server notwendig ist, oder nicht? Und besagtes
Passwort kenne ich nicht.
> > ACK. Ich werde wahrscheinlich morgen oder ubermorgen sowieso mal beim Blum
> > vorbeischauen mussen;
> Was verschafft dir die Ehre? :-)
Anmeldung fuer die Info-B-Pruefung. Er machte uebrigens einen sehr gestressten
und entnervten Eindruck. Nach eigener Aussage ist er gerade dabei, sein Buch
zu ueberarbeiten...
> > > http://www.securityfocus.com/
> > Werde ich mir anschauen, merci.
> Ah, wenn du dir das mal ansiehst wird du merken, da? das eher als Spa?
> gedacht war.
> Ware zumindest nicht die netteste Art um an das CVS zu kommen. :-)
Und ich wollte gerade Fragezeichen zurueckschicken...
> Bye, Lutz
Und tschuess
Markus
Other related posts:
