[informatik-bonn] algoschrott

  • From: Lutz Oberst <oberst@xxxxxxxxxxx>
  • To: informatik-bonn@xxxxxxxxxxxxx
  • Date: Sat, 3 May 2003 10:30:54 +0200

Hallo,

kann es sein, daß der Algorithmus von Seite 157 kaputt ist?

Folgender NEA:
      a           \epsilon
q_0 -------> q_1 -----------> q_f


Q' anfangs {q_0} und {q_0} nicht markiert.

Dann wird \delta({q_0}, a):={q_1} durch die foreach Schleife
gesetzt und Q'=Q' \cup {q_1}.
Ausserdem jetzt {q_0} markiert, und {q_1} nicht markiert.

Soweit funktioniert der Alg. prima.

Jetzt wird S aber auf {q_1} gesetzt, da diese Menge die einzige
unmarkierte ist und alle Eingabesymbole
ausser \epsilon (wg. \epsilon \notin \Sigma) werden durchprobiert.

for alle x \in \Sigma
        T := FZ ( \delta ({q_1}, x) )
        ....

T ist aber immer undefiniert bzw \emptyset, da der einzige
mögliche Übergang \delta({q_1}, \epsilon) nie überprüft
wird. Das FZ kann den \epsilon-Übergang auch nicht erkennen,
da es ja auf den Output von \delta angewiesen ist,
\delta aber nur auf \epsilon reagieren würde, was ja
wiegesagt nicht ausprobiert wird.

Somit geht es bei q_1 nicht mehr weiter.

Ist das mal wieder ein Blumorithmus oder habe ich
da was falsch verstanden?

Bye, Lutz
-- 
signature intentionally left blank


Other related posts:

  • » [informatik-bonn] algoschrott