Diskussion:Leeres Wort

Konfusion bei abstrakten Symbolen

Im Artikel steht:

$\varepsilon$-Übergänge in Nichtdeterministischen endlichen Automaten sind Tupel $(q_{1},\varepsilon ,q_{2})$ aus der Übergangsrelation $\Delta$ mit Zuständen $q_{1},q_{2}$. Ein solcher Übergang bedeutet, dass der Automat seinen Zustand von $q_{1}$ nach $q_{2}$ ändern kann, ohne dass ein Zeichen gelesen wird. $\varepsilon$-Übergänge sind damit einer der Gründe für Nichtdeterminismus. Sie werden im Graphen als Kanten kenntlich gemacht, die mit einem $\varepsilon$ beschriftet sind.

Es ist also immer von den Zuständen q₁ und q₂ die Rede; in der Grafik sind sie allerdings mit p und q bezeichnet. Sollte dies nicht besser angeglichen werden?

Gruß, Friz -- 77.12.197.20 19:42, 4. Mär. 2011 (CET)

Ich würde eher sagen: Nicht angleichen. Der Text handelt allgemein von $\varepsilon$-Übergängen und die Abbildung zeigt lediglich einen ganz bestimmten Automat, der einen $\varepsilon$-Übergang aufweist. Man stelle sich vor, der abgebildete Automat hätte mehrere $\varepsilon$-Übergänge. Sollen die damit verbundenen Zustände dann etwa auch alle im Text auftauchen? Natürlich nicht. Aus einem anderen Betrachtungswinkel gesehen, spricht der Text bereits von allen möglichen $\varepsilon$-Übergängen, wobei die Zustände generisch bezeichnet sind. --Daniel5Ko 21:18, 4. Mär. 2011 (CET)

Verständnisfrage

Ein $\varepsilon$-Übergang führt also u.U. zu nichtdeterministischen Zuständen, was ja im Allgemeinen nicht gewünscht ist. Da frage ich mich, wofür kann er dann _gut_ sein; wird er sozusagen als Platzhalter verwendet bspw. für ein nicht vorhandenes Token, oder ist er für logische Beweise notwendig? -- Friz 77.12.224.6 17:51, 16. Mär. 2011 (CET)

Epsilon-Übergänge führen immer zu Nichtdeterminismus (außer, man käme auf die verrückte Idee von Epsilon-Schleifen). Wie im verlinkten Artikel zu nichtdeterministischen endlichen Automaten steht, wird ein Automat durch sie nicht fähiger als ohne diese Übergänge. Sie sind also nicht zwingend notwendig. Sie sind aber praktisch, wenn man bestimmte Automatenkonstruktionen vereinfachen will, um zu zeigen, dass es einen endlichen Automaten für die gewünschte Sprache gibt (siehe ebenfalls im verlinkten Artikel das Beispiel der Vereinigung zweier Sprachen). Soll der Automat von einer deterministischen Maschine simuliert werden, muss man den Nichtdeterminismus natürlich irgendwie loswerden. Ansonsten ist Nichtdeterminismus aber nicht per se schlecht. --Zahnradzacken 18:48, 16. Mär. 2011 (CET)