Seite 1 von 1

Definition "Läufe auf Eingabewörtern"

Verfasst: 9. Mär 2017 14:33
von Smith
Hallo,

Sind mit dem Ausdruck "Alle Läufe auf Eingabewort w" bezüglich eines Automaten A alle Möglichkeiten gemeint einen Weg einzuschlagen, der zum Ziel (erfolgreiche Eingabe des Wortes) führen kann (immer nur den momentan abzulaufenden Buchstaben betrachtend, ohne voraus zu schauen wie es weiter gehen wird),
oder sieht es so aus, dass nur die eingeschlagenen Wege, die tatsächlich dazu führen, dass das ganze Wort in A abgelaufen werden kann, als Läufe gelten?

Kann also beispielsweise für ein Wort \(w_o = aabba\) ein Lauf auch \(aabb\) sein, wobei der Automat (in diesem Fall wohl NFA) eine "Sackgasse" eingeschlagen hat, also nicht weiter kommt?
Oder gilt ein solcher Weg nicht als Lauf und es kommen nur jene in Betracht, die am Ende tatsächlich zu \(aabba\) führen?

Re: Definition "Läufe auf Eingabewörtern"

Verfasst: 9. Mär 2017 20:52
von tobi_m
(* Studentenantwort *)

Hallo,

falls es hilft: Auf Übungsblatt 3 in der Musterlösung zur Aufgabe G3.1b), bei der man zu einem NFA alle möglichen Läufe eines Wortes angeben sollte, werden auch solche angegeben, die in einer "Sackgasse" landen.

Viele Grüße

Re: Definition "Läufe auf Eingabewörtern"

Verfasst: 11. Mär 2017 10:42
von Smith
Danke, klar hilft das :)