Definition "Läufe auf Eingabewörtern"

Smith
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 13. Apr 2015 15:45

Definition "Läufe auf Eingabewörtern"

Beitrag von Smith » 9. Mär 2017 14:33

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?
Phil

tobi_m
Neuling
Neuling
Beiträge: 2
Registriert: 11. Sep 2016 19:22

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

Beitrag von tobi_m » 9. Mär 2017 20:52

(* 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

Smith
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 13. Apr 2015 15:45

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

Beitrag von Smith » 11. Mär 2017 10:42

Danke, klar hilft das :)
Phil

Antworten

Zurück zu „Archiv“