Ich lese gerade das Buch Einführung in die Theorie der Berechnung (2. oder 3. Aufl.) Von Michael Sipser und bin auf eine Frage in Kapitel 1 - Reguläre Sprachen gestoßen , nämlich wenn der Autor die Beweisidee von Satz 1.49 vorlegt - "Die Klasse der regulären Sprachen ist unter der Sternoperation geschlossen." mit NFA.
Der vorgeschlagene Ansatz ist, dass wir, wenn wir eine reguläre Sprache und beweisen wollen, dass auch regulär ist, einen NFA und ihn in ein wie im Bild unten ändern können , das dann eine bestimmte NFA-Erkennung ist .
Er bemerkte:
Eine (etwas schlechte) Idee ist einfach, den Startzustand zu der Menge der Akzeptanzzustände hinzuzufügen. Dieser Ansatz fügt der erkannten Sprache sicherlich hinzu , kann aber auch andere, unerwünschte Zeichenfolgen hinzufügen.
Ich habe die "schlechte" NFA wie folgt gezeichnet und versucht herauszufinden, warum dies zu unerwünschten Zeichenfolgen führt. Ich kann jedoch kein Beispiel dafür finden, wann eine unerwünschte Zeichenfolge erkannt wird. Warum führt diese Idee dazu, dass die NFA unerwünschte Zeichenfolgen erkennt?
Könnte jemand mich darauf hinweisen oder mir einen Hinweis geben, oder habe ich den Autor falsch verstanden? Danke im Voraus!
quelle