Endliche Automaten und reguläre Grammatiken
Ein Getränkeautomat im Bahnhof merkt sich nicht jede Münze einzeln. Er „weiß“ nur, wie viel Geld bisher eingeworfen wurde, und das genügt ihm, um zu entscheiden, ob er ein Getränk ausgibt. Mit sehr wenig Gedächtnis steuert er also einen ganzen Ablauf. Genau dieses Prinzip beschreibt der endliche Automat. Am Ende der Seite beantworten wir, was ein solcher Automat mit seinem begrenzten Gedächtnis nicht mehr leisten kann.
Der endliche Automat
Ein Automat liest ein Eingabewort Zeichen für Zeichen. Nach jedem Zeichen wechselt er seinen Zustand. Wie er wechselt, legt allein der aktuelle Zustand und das gelesene Zeichen fest.
Im Zustandsdiagramm sind Zustände Kreise, Übergänge beschriftete Pfeile, der Startzustand hat einen eingehenden Pfeil ohne Ursprung, und akzeptierende Zustände sind doppelt umrandet.
Der Rechenweg heißt auch Konfigurationsfolge: $q_0 \xrightarrow{a} q_1 \xrightarrow{a} q_1 \xrightarrow{b} q_0$. Das leere Wort $\varepsilon$ wird genau dann akzeptiert, wenn der Startzustand akzeptierend ist.
Ein Automat hat die Zustände $q_0$ (Start), $q_1$ (akzeptierend) und das Alphabet $\{a, b\}$. Übergänge: $q_0 \xrightarrow{a} q_1$, $q_0 \xrightarrow{b} q_0$,…
Ein Automat hat die Zustände $q_0$ (Start), $q_1$ (akzeptierend) und das Alphabet $\{a, b\}$. Übergänge: $q_0 \xrightarrow{a} q_1$, $q_0 \xrightarrow{b} q_0$, $q_1 \xrightarrow{a} q_1$, $q_1 \xrightarrow{b} q_0$.
- a) Prüfen Sie, ob die Wörter
ba,abundbbakzeptiert werden.
- b) Beschreiben Sie die akzeptierte Sprache in Worten.
Ein Getränkeautomat in einem Bahnhof in Hannover akzeptiert 1-€- und 2-€-Münzen; ein Getränk kostet 2 €. Wird zu viel eingezahlt, gibt der Automat das Getränk aus und…
Ein Getränkeautomat in einem Bahnhof in Hannover akzeptiert 1-€- und 2-€-Münzen; ein Getränk kostet 2 €. Wird zu viel eingezahlt, gibt der Automat das Getränk aus und das überzahlte Geld als Wechselgeld zurück.
- a) Geben Sie die Zustände (eingezahlter Betrag) an.
- b) Stellen Sie das Zustandsdiagramm in Textform (als Übergangstabelle) dar.
Automaten entwerfen
Beim Entwurf fragen Sie sich: Was muss sich der Automat über das bisher Gelesene merken? Jede unterschiedliche Antwort braucht einen eigenen Zustand.
Auch Steuerungen sind Automaten, nur ohne akzeptierenden Zustand: Eine Ampel durchläuft zyklisch ihre Zustände, ein Takt-Signal löst jeden Wechsel aus. Die Eingabe ist dann eine Folge von Ereignissen, die Ausgabe der aktuelle Zustand.
Eine Ampelsteuerung an einer Kreuzung in Bochum durchläuft die Zustände Rot, Rot-Gelb, Grün, Gelb. Ein Signal takt löst den Wechsel aus. a) Modellieren Sie die Steuerung…
Eine Ampelsteuerung an einer Kreuzung in Bochum durchläuft die Zustände Rot, Rot-Gelb, Grün, Gelb. Ein Signal takt löst den Wechsel aus.
- a) Modellieren Sie die Steuerung als endlichen Automaten (Zustände, Übergänge).
- b) Welche Zustandsfolge entsteht nach fünf Takten, wenn der Start bei Rot liegt?
Entwerfen Sie einen deterministischen endlichen Automaten über $\{0, 1\}$, der genau die Wörter mit einer geraden Anzahl von Einsen akzeptiert. a) Geben Sie Zustände,…
Entwerfen Sie einen deterministischen endlichen Automaten über $\{0, 1\}$, der genau die Wörter mit einer geraden Anzahl von Einsen akzeptiert.
- a) Geben Sie Zustände, Startzustand, akzeptierende Zustände und Übergangstabelle an.
- b) Testen Sie
1011und0110.
Ein Passwortprüfer soll Zeichenfolgen über $\{L, Z\}$ (Buchstabe, Ziffer) akzeptieren, die mit einem Buchstaben beginnen und mindestens eine Ziffer enthalten. a)…
Ein Passwortprüfer soll Zeichenfolgen über $\{L, Z\}$ (Buchstabe, Ziffer) akzeptieren, die mit einem Buchstaben beginnen und mindestens eine Ziffer enthalten.
- a) Entwerfen Sie einen DFA und begründen Sie die Zustände.
- b) Geben Sie einen regulären Ausdruck und eine reguläre Grammatik an.
- c) Wandeln Sie Ihren Automaten so um, dass zusätzlich genau drei Zeichen gefordert sind, und beschreiben Sie die Änderung.
Reguläre Grammatiken und reguläre Ausdrücke
Statt eines Automaten, der Wörter prüft, kann man auch ein Regelsystem angeben, das Wörter erzeugt.
Ein Wort wird abgeleitet, indem man mit $S$ beginnt und immer ein Nichtterminal durch die rechte Seite einer Regel ersetzt, bis nur Terminale übrig bleiben. Der Ableitungsschritt wird mit $\Rightarrow$ geschrieben.
Reguläre Ausdrücke beschreiben dieselben Sprachen kompakt:
| Ausdruck | Bedeutung | Beispiel |
|---|---|---|
| $ab$ | Verkettung | nur ab |
| $a \mid b$ | Auswahl | a oder b |
| $a^{*}$ | beliebig oft, auch null Mal | $\varepsilon$, a, aa, … |
| $a^{+}$ | mindestens einmal | a, aa, … |
Reguläre Sprachen sind genau die Sprachen, die ein endlicher Automat erkennt, ein regulärer Ausdruck beschreibt und eine reguläre Grammatik erzeugt.
Gegeben ist die Grammatik $G$ mit $S \to aS \mid b$. a) Leiten Sie die Wörter b, ab und aab ab. b) Beschreiben Sie die erzeugte Sprache durch einen regulären Ausdruck.
Gegeben ist die Grammatik $G$ mit $S \to aS \mid b$.
- a) Leiten Sie die Wörter
b,abundaabab.
- b) Beschreiben Sie die erzeugte Sprache durch einen regulären Ausdruck.
Ein Automat soll Wörter über $\{a, b\}$ akzeptieren, die auf ab enden. a) Entwerfen Sie einen Automaten und geben Sie die Übergangstabelle an. b) Geben Sie eine reguläre…
Ein Automat soll Wörter über $\{a, b\}$ akzeptieren, die auf ab enden.
- a) Entwerfen Sie einen Automaten und geben Sie die Übergangstabelle an.
- b) Geben Sie eine reguläre Grammatik für diese Sprache an.
Vom Automaten zur Grammatik und zurück
Beide Modelle lassen sich ineinander übersetzen:
-
Automat → Grammatik: Jeder Zustand wird ein Nichtterminal, der Startzustand wird $S$. Für jeden Übergang $P \xrightarrow{x} Q$ gibt es die Regel $P \to xQ$. Ist $Q$ akzeptierend, kommt zusätzlich $P \to x$ dazu.
-
Grammatik → Automat: Jedes Nichtterminal wird ein Zustand. Für $A \to aB$ zeichnet man $A \xrightarrow{a} B$. Für $A \to a$ führt ein Pfeil zu einem neuen akzeptierenden Endzustand $E$.
Zur Erinnerung: Aus einem nichtdeterministischen Automaten lässt sich immer ein DFA bauen, dessen Zustände Mengen der alten Zustände sind (hier z. B. $\{A, E\}$ nach dem ersten c). Beide erkennen dieselbe Sprache.
Gegeben ist die Grammatik $S \to aA$, $A \to bA \mid cS \mid c$. a) Geben Sie drei Wörter der Sprache mit Ableitung an. b) Konstruieren Sie den zugehörigen Automaten. c)…
Gegeben ist die Grammatik $S \to aA$, $A \to bA \mid cS \mid c$.
- a) Geben Sie drei Wörter der Sprache mit Ableitung an.
- b) Konstruieren Sie den zugehörigen Automaten.
- c) Entscheiden Sie mit Begründung, ob
abbcaczur Sprache gehört.
Grenzen endlicher Automaten
Nun zur Frage vom Anfang: Ein Automat hat nur endlich viele Zustände, also nur ein beschränktes Gedächtnis. Kann er etwa die Sprache $L = \{a^n b^n \mid n \ge 0\}$ erkennen? Zu ihr gehören ab, aabb, aaabbb, …
Angenommen, ein DFA mit $k$ Zuständen erkennt $L$. Liest er das Wort $a^{k}$, durchläuft er nach jedem a einen Zustand, also $k+1$ Zustände (mit dem Start). Davon müssen zwei gleich sein, denn es gibt nur $k$ verschiedene (Schubfachprinzip). Der Automat kann dann nicht mehr unterscheiden, ob er $i$ oder $j$ Mal ein a gelesen hat, obwohl $i \ne j$. Da beide Wörter $a^i$ und $a^j$ im selben Zustand enden, verläuft der Rest der Rechnung gleich. Weil der Automat a^i b^i akzeptiert, akzeptiert er deshalb auch a^j b^i. Wegen $i \ne j$ gehört a^j b^i aber nicht zu $L$. Widerspruch.
Was fehlt, ist ein unbegrenzter Speicher. Ein Stack (Kellerspeicher) reicht hier schon aus: Für jedes a legt man ein Symbol auf den Stack, für jedes b nimmt man eins herunter. Das Wort ist korrekt, wenn der Stack am Ende genau leer ist. Automaten mit Stack heißen Kellerautomaten; sie erkennen die kontextfreien Sprachen. Die Grammatik $S \to aSb \mid \varepsilon$ erzeugt $L$, sie ist kontextfrei, aber nicht regulär.
Gegeben ist die Sprache $L = \{a^n b^n \mid n \ge 0\}$. a) Begründen Sie anschaulich, warum kein endlicher Automat $L$ erkennen kann (Zählen unbeschränkt). b)…
Gegeben ist die Sprache $L = \{a^n b^n \mid n \ge 0\}$.
- a) Begründen Sie anschaulich, warum kein endlicher Automat $L$ erkennen kann (Zählen unbeschränkt).
- b) Beschreiben Sie, welches zusätzliche Speichermodell (Stack) ausreicht.
- c) Erläutern Sie die Bedeutung für Grenzen regulärer Ausdrücke, z. B. beim Prüfen beliebig tiefer Klammerung.
Auf einen Blick
-
Ein DFA besteht aus Zuständen, Alphabet, Übergangsfunktion, Startzustand und akzeptierenden Zuständen. Er akzeptiert ein Wort, wenn er nach dem letzten Zeichen in einem akzeptierenden Zustand steht.
-
Entwurf: Fragen Sie, was sich der Automat merken muss. Jede verschiedene Antwort ergibt einen Zustand. Die Übergangstabelle muss vollständig sein.
-
Reguläre Grammatik: Regeln der Form $A \to a$ oder $A \to aB$. Reguläre Ausdrücke ($\mid$, $^{*}$, $^{+}$), reguläre Grammatiken und endliche Automaten beschreiben dieselben Sprachen.
-
Umwandlung: Zustand ↔ Nichtterminal, Übergang $P \xrightarrow{x} Q$ ↔ Regel $P \to xQ$. Dabei kann Nichtdeterminismus entstehen.
-
Grenzen: Unbeschränktes Zählen oder beliebig tiefe Verschachtelung (z. B. $a^n b^n$, Klammerung) ist nicht regulär. Dafür braucht man einen Stack.
-
Operatoren: Sie sollen Wörter prüfen, Automaten entwerfen, Grammatiken angeben und Grenzen begründen können.
Zurück zum Anfang: Der Getränkeautomat kommt mit wenigen Zuständen aus, weil nur endlich viele Beträge zu unterscheiden sind. Sobald unbeschränkt viel gemerkt werden muss, reicht ein endlicher Automat nicht mehr.