Endliche Automaten und reguläre Grammatiken
Am Fahrkartenautomaten am Kölner Hauptbahnhof wirfst du Münzen ein, bis der Fahrpreis erreicht ist, dann druckt der Automat das Ticket. Er „merkt" sich nur, wie viel schon eingezahlt wurde, nicht die Reihenfolge der Münzen. Genau dieses Prinzip beschreibt der endliche Automat: Er hat endlich viele Zustände und wechselt bei jeder Eingabe den Zustand. Am Ende dieser Seite kannst du erklären, warum ein solcher Automat manche Aufgaben lösen kann und andere nicht.
Zustände, Übergänge, akzeptierte Sprache
Ein Automat liest ein Wort Zeichen für Zeichen. Die Zeichen stammen aus einem Alphabet $\Sigma$, zum Beispiel $\Sigma = \{a, b\}$. Nach jedem Zeichen befindet sich der Automat in einem Zustand.
Beispiel: Der folgende Automat akzeptiert alle Wörter über $\{a, b\}$, die mindestens ein $a$ enthalten.
Prüfe das Wort bab: $q_0 \xrightarrow{b} q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_1$. Der Automat endet in $q_1$, also wird bab akzeptiert. Bei bb bleibt er in $q_0$: nicht akzeptiert.
Dieselbe Information passt in eine Übergangstabelle:
| Zustand | bei $a$ | bei $b$ |
|---|---|---|
| $\to q_0$ | $q_1$ | $q_0$ |
| $q_1$ (akzeptierend) | $q_1$ | $q_1$ |
Der Pfeil $\to$ markiert den Startzustand, „(akzeptierend)" die Endzustände.
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 stellst du dir die Frage: Was muss sich der Automat merken? Jede unterscheidbare Information wird ein Zustand. Mehr braucht der Automat nicht, denn er hat keinen weiteren Speicher.
Steuerungen wie eine Ampel sind ebenfalls Automaten. Die Zustände sind die Ampelphasen, die Eingabe ist ein Taktsignal, und bei jedem Takt wechselt der Zustand. Es gibt dann meist keinen Endzustand, wichtig ist die Abfolge der 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,…
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.
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?
Reguläre Grammatiken und reguläre Ausdrücke
Statt eines Automaten, der Wörter erkennt, kann man Wörter auch erzeugen. Das leistet eine Grammatik.
Die Schreibweise $A \to aB \mid b$ ist eine Abkürzung für die zwei Regeln $A \to aB$ und $A \to b$.
Reguläre Ausdrücke beschreiben dieselben Sprachen kompakt:
| Ausdruck | Bedeutung |
|---|---|
a |
das Zeichen $a$ |
xy |
erst $x$, dann $y$ |
x\\|y |
$x$ oder $y$ |
x* |
$x$ beliebig oft, auch gar nicht |
x+ |
$x$ mindestens einmal |
Die Sprache „endet auf 0" lautet (0|1)*0. Die Sprache „mindestens ein $a$" lautet b*a(a|b)*.
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
Automaten und reguläre Grammatiken beschreiben genau dieselben Sprachen, nämlich die regulären Sprachen. Dasselbe gilt für reguläre Ausdrücke. Man kann sie ineinander umwandeln.
Der Grund: Jedes gelesene Zeichen erzeugt ein Terminal, der Zustand entspricht dem „Rest", der noch folgen kann. Ein Wort endet, wenn man in einem Endzustand ankommt.
Grammatik → Automat geht in die Gegenrichtung. Nichtterminale werden Zustände, aus $Q \to xP$ wird $Q \xrightarrow{x} P$. Für jede Regel $Q \to x$ ohne Nichtterminal führst du einen zusätzlichen akzeptierenden Zustand $F$ ein, mit $Q \xrightarrow{x} F$.
Dabei kann es vorkommen, dass ein Zustand für dasselbe Zeichen zwei Ziele hat (ein nichtdeterministischer Automat). Ein Wort wird dann akzeptiert, wenn mindestens ein Weg zum Endzustand führt. Du kannst daraus einen DFA machen, indem du Zustände zusammenfasst, die gemeinsam erreicht werden.
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.
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.
Grenzen endlicher Automaten
Ein endlicher Automat hat nur endlich viele Zustände und sonst keinen Speicher. Daher kann er sich nur eine beschränkte Menge an Information merken. Betrachte die Sprache
$$L = \{a^n b^n \mid n \ge 0\} = \{\varepsilon,\ ab,\ aabb,\ aaabbb, \dots\}.$$Um zu entscheiden, ob ein Wort in $L$ liegt, muss man erst die $a$ zählen und dann genauso viele $b$ finden.
Mit einem Stack (Kellerspeicher) geht es: Für jedes $a$ legst du ein Symbol auf den Stack, für jedes $b$ nimmst du eines herunter. Ist der Stack am Ende leer, stimmen die Anzahlen.
Dieselbe Grenze gilt für reguläre Ausdrücke. Sie können nicht prüfen, ob in einem Text beliebig tief verschachtelte Klammern korrekt geschlossen sind, etwa ((())). Dafür muss man mitzählen, wie viele Klammern noch offen sind, und dieser Zähler ist unbeschränkt. Für solche Aufgaben, etwa bei Compilern für Java, braucht man stärkere Mittel.
Zurück zum Fahrkartenautomaten vom Anfang: Er kann Münzen nur bis zu einem festen Betrag „zählen". Das ist beschränkt, deshalb reicht ein endlicher Automat. Die Sprache $a^n b^n$ verlangt unbeschränktes Zählen, deshalb reicht er dort nicht.
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, Startzustand, Endzuständen und einer Übergangsfunktion. Ein Wort wird akzeptiert, wenn der Automat nach dem letzten Zeichen in einem Endzustand steht.
-
Beim Entwurf fragst du: Was muss der Automat sich merken? Jede Information ist ein Zustand. Die Übergangstabelle muss vollständig sein.
-
Eine reguläre Grammatik hat Regeln der Form $A \to aB$ oder $A \to a$. Die Ableitung beginnt bei $S$ und endet, wenn nur noch Terminale übrig sind.
-
Reguläre Ausdrücke (
|,*,+) beschreiben reguläre Sprachen kompakt. Automaten, reguläre Grammatiken und reguläre Ausdrücke sind gleichmächtig. -
Umwandlung: Zustand ↔ Nichtterminal, Übergang ↔ Regel $Q \to xP$, Endzustand ↔ zusätzliche Regel $Q \to x$. Dabei können nichtdeterministische Übergänge entstehen, die man zu einem DFA zusammenfassen kann.
-
Grenzen: Sprachen wie $\{a^n b^n\}$ oder beliebig tief verschachtelte Klammern erfordern unbeschränktes Zählen. Dafür braucht man zusätzlichen Speicher (Stack).
Checkliste zu den Operatoren:
-
Prüfen Sie, ob ein Wort akzeptiert wird, indem Sie den Weg durch den Automaten verfolgen.
-
Entwerfen Sie einen Automaten, indem Sie zuerst die zu merkenden Informationen festlegen.
-
Begründen Sie die Grenze: endlich viele Zustände, unbeschränktes Zählen.