[informatik-bonn] Re: aufgaben

  • From: Lutz Oberst <oberst@xxxxxxxxxxx>
  • To: informatik-bonn@xxxxxxxxxxxxx
  • Date: Tue, 10 Jun 2003 13:35:29 +0200

On Tue, Jun 10, 2003 at 01:02:57AM +0200, Markus Hirsch wrote:

> Hallo,
Hallo,

> ...ist die Frage, ob der Algorithmus so uberhaupt funktioniert. Vielleicht 
> kann mir ja
> jemand sagen, was an folgender Uberlegung falsch ist:

Der Fehler ist die Annahme, es handele sich hier um einen Algorithmus,
ich vermute vielmehr, daß wir es hier mit einem B*um-o-rithmus zu tun haben.
:-)

> Angenommen, Du hast eine Produktion A->A_1...A_kC mit A_i in V und A_i in 
> W_n^*, 
> C -> a mit a Terminalsymbol. So, wie der Algorithmus aufgeschrieben ist, kame 
> eine
> Produktion A -> A_2C in P', eine Produktion A -> A_3C usw., weil jede 
> Epsilon-Regel insbesondere
> auch von einem Symbol in V ausgeht, und man die umgebenden A_i jeweils zu 
> einem alpha zusammen-
> fasst. Wenn Du Dir jetzt die verschiedenen Kombinationen uberlegst,
> die in P' aufgenommen werden, kriegst Du recht viele Produktionen
> -- allerdings ist die Grammatik dann
> nicht wirklich epsilon-frei.

Genau, daher kann das eigentlich nur so gemeint sein, daß
für die A_i gilt: A_i \in (V \setminus {W_n^*}).

Dann kann man aber die Geschichte mit den Kombinationen nicht mehr
machen und die Grammatik wächst nicht expotentiell.

> Man musste IMO, damit der Algo funktioniert, anschlie?end ahnlich zu ALLKFA
> noch einmal die Produktionen
> rauswerfeb, von denen aus man nicht mehr wegkommt.

Stimmt, das hat aber dann auch den Effekt, daß alle Kombinationen
rausfallen, so daß man zum gleichen Ergebnis kommt, wie mit der
verschärften Bedingung von oben für die A_i.

> PS: Ohne nerven zu wollen: was muss man tun, um Zugang zum Server zu kriegen?

http://www.securityfocus.com/

> Schone Gru?e
> Markus

Bye, Lutz
-- 
signature intentionally left blank


Other related posts: