Zur Wiederholung: Abschnitt 3.3 (Nichtdeterministische endliche Automaten) ohne Abschnitt 3.3.1
Vorbemerkungen: Der 101-Automat (Seite 28, Aufgabe 2) wurde von uns schon behandelt. Die Grammatik dazu war Aufgabe vom 18.12.2021. Eine Grammatik zum Automaten ergibt sich so: S --> 0S | 1A A --> 0B | 1A B --> 0S | 1C | 1 C --> 0B | 1A Auf Seite 29 ist der dazugehörige nichtdeterministische Automat abgebildet. In Tabellenform dargestellt ist die Zustandsübergangsfunktion δ:
Die Grammatik ist wie folgt gebildet worden: S --> 0S | 1S | 1A A --> 0B B --> 1 oder noch kürzer: S --> 0S | 1S | 101
Zusammenfassung: Durch das zugegebenermaßen etwas merkwürdige Konzept eines nichtdeterministischen Automaten mit einer eingebauten "guten Fee" ist es möglich, die zugehörige Grammatik sehr stark zu vereinfachen.
Den 007-Automaten (Seite 32) haben wir bereits behandelt in den Aufgaben am 13.01.2021.
Die Lösungen dazu: Das Eingabealphabet ist Σ = { 0, 1, 2, 3 ,4, 5, 6, 7, 8, 9 }. Die Menge der Zustände ist Z = { Z0, Z1, Z2, Z3 }. Die Menge der Endzustände ist ZE = { Z3 }. Der Startzustand ist z0 = Z0. Der Automat akzeptiert beispielsweise folgenden drei Eingabeworte: 007, 12300456780079 und 120000000000789. Das Wort 007 wird wie folgt akzeptiert: Z0 --0--> Z1 --0--> Z2 --7-->Z3 Das Wort 120006007006 wird wie folgt akzeptiert: Z0 --1--> Z0 --2--> Z0 --0--> Z1 --0--> Z2 --0--> Z2 --6--> Z0 --0--> Z1 --0--> Z2 --7--> Z3 --0--> Z3 --0--> Z3 --6--> Z3 Die Zustandsübergangsfunktion δ in Tabellenform:
| 0 | 7 | 1,2,3,4,5,6,8,9 | ----------------------------------- Z0 | Z1 | Z0 | Z0 | ----------------------------------- Z1 | Z2 | Z0 | Z0 | ----------------------------------- Z2 | Z2 | Z3 | Z0 | ----------------------------------- Z3 | Z3 | Z3 | Z3 | -----------------------------------
Die Produktionen der Grammatik zum Automaten sehen wie folgt aus:
Z0 --> 0Z1 | 1Z0 | 2Z0 | .. | 9Z0 Z1 --> 0Z2 | 1Z0 | 2Z0 | .. | 9Z0 Z2 --> 0Z2 | 7Z3 | 7 | 1Z0 | .. | 6Z0 | 8Z0 | 9Z0 Z3 --> 0Z3 | 1Z3 | .. | 9Z3 | 0 | .. | 9
Aufgabe 1: Konstruiere den dazugehörigen nichtdeterministischen Automaten und gib hier seine Zustandsübergangsfunktion δ in Tabellenform an:
Aufgabe 2: Zeige, dass sich aus dem nichtdeterministischen Automaten eine deutlich einfachere Grammatik entwickeln lässt.