Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
NFA - \epsilon-Übergänge
Mir ist bei der Beschäftigung mit nichtdeterministischen Automaten eine Frage bezüglich des folgenden Beispiels gekommen.
https://imgur.com/9vzrIO1
Habe im Skript bei der Definition von NFAs keine formale Definition gefunden, was nun bei ε-Übergängen geschieht, und will deshalb noch einmal wirklich sicher gehen.
Vielen Dank bereits im Voraus für eine Antwort!
Julian
Das Alphabet, das in der Übergangsfunktion verwendet wird, ist das Alphabet des Automaten geschnitten mit der Menge, die nur Epsilon enthält.
Folglich werden Epsilonübergänge explizit angegeben. In deinem Beispiel wäre also die Menge leer.
(Zumindest, wenn ich das selbst richtig aus meinen Unterlagen herauslese.)
Laut Definition 3.7, die kanonische Fortsetzung von δ:
δ(q,w)=δ(q,w₁⋯w[sub]n[/sub])=U[sub]q’∈δ(q,w₁⋯w[sub]n-1[/sub])[/sub]δ(q’,w[sub]n[/sub])
Hier kann man 1 unter anderem als ε1∈∑[sub]ε[/sub][sup]*[/sup] schreiben.
Damit ist hier δ(q₀,1)=δ(q₀,ε1)=U[sub]q’∈δ(q₀,ε)[/sub]δ(q’,1)=U[sub]q’∈{q₁}[/sub]δ(q’,1)=δ(q₁,1)={q₂}
Genau genommen müsste man in der Definition eine Vereinigung über alle möglichen Darstellungen von w als w₁⋯w[sub]n[/sub]∈∑[sub]ε[/sub][sup]*[/sup] machen. Dies ist jedoch (soweit ich weiß) implizit gemeint. Beachte n variiert je nach Anzahl der genutzten ε.
Die Antwort von Destranix ist IMHO falsch
1 „Gefällt mir“
Stimmt, die kanonische Fortsetzung hatte ich nicht bedacht. Demnach wäre meine letzte Schlußfolgerung zwar korrekt, baut allerdings auf der falsche Annahme auf, dass Delta nicht die kanonische Fortsetzung sein.