Diskussion:Leeres Wort

Letzter Kommentar: vor 13 Jahren von Zahnradzacken in Abschnitt Verständnisfrage

Konfusion bei abstrakten Symbolen

Bearbeiten

Im Artikel steht:

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

Es ist also immer von den Zuständen q1 und q2 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)Beantworten
Ich würde eher sagen: Nicht angleichen. Der Text handelt allgemein von  -Übergängen und die Abbildung zeigt lediglich einen ganz bestimmten Automat, der einen  -Übergang aufweist. Man stelle sich vor, der abgebildete Automat hätte mehrere  -Ü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  -Übergängen, wobei die Zustände generisch bezeichnet sind. --Daniel5Ko 21:18, 4. Mär. 2011 (CET)Beantworten

Verständnisfrage

Bearbeiten

Ein  -Ü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)Beantworten

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)Beantworten