Reguläre Grammatiken und Grenzen endlicher Automaten
Eine Wetterstation in Hamburg schickt ihre Meldungen als Zeichenfolge an einen Server. Der Server soll prüfen, ob eine Meldung formal richtig aufgebaut ist, bevor er sie speichert. Wie beschreibt man eindeutig, welche Zeichenfolgen erlaubt sind? Und welche Prüfungen schafft ein einfacher Automat mit endlich vielen Zuständen gar nicht? Am Ende der Seite kannst du beides begründen.
Grammatik und Ableitung
Eine Grammatik erzeugt Wörter nach Regeln. Du startest mit einem Startsymbol und ersetzt so lange Symbole, bis nur noch Zeichen des Alphabets übrig sind.
Ein Ableitungsschritt wird mit $\Rightarrow$ geschrieben. Die Schreibweise $A \to x \mid y$ ist eine Abkürzung für die zwei Regeln $A \to x$ und $A \to y$. Das Symbol $\varepsilon$ steht für das leere Wort.
Ob ein Wort nicht zur Sprache gehört, begründest du so: Du zeigst, dass keine Regelfolge dieses Wort ergibt. Bei $G$ von oben steht das $b$ immer ganz am Ende und kommt genau einmal vor. Deshalb ist $ba$ kein Wort der Sprache.
Gegeben ist die Grammatik $G$ mit Startsymbol $S$ und den Produktionen: $S \to aS \mid bA$, $A \to b \mid \varepsilon$ a) Leiten Sie das Wort $aabb$ Schritt für Schritt…
Gegeben ist die Grammatik $G$ mit Startsymbol $S$ und den Produktionen:
$S \to aS \mid bA$, $A \to b \mid \varepsilon$
- a) Leiten Sie das Wort $aabb$ Schritt für Schritt ab.
- b) Geben Sie zwei weitere Wörter der Sprache an.
- c) Entscheiden Sie, ob $ba$ zur Sprache gehört, und begründen Sie.
Gegeben ist die Grammatik mit den Produktionen $S \to 0S \mid 1S \mid 1$. a) Nennen Sie Terminal- und Nichtterminalsymbole. b) Leiten Sie $0101$ ab. c) Beschreiben Sie…
Gegeben ist die Grammatik mit den Produktionen $S \to 0S \mid 1S \mid 1$.
- a) Nennen Sie Terminal- und Nichtterminalsymbole.
- b) Leiten Sie $0101$ ab.
- c) Beschreiben Sie die erzeugte Sprache in Worten.
Reguläre Grammatiken
Nicht jede Grammatik ist gleich mächtig. Für reguläre Grammatiken gibt es eine strenge Form der Produktionen.
Das Nichtterminal steht also immer ganz rechts und nur höchstens eins pro Regel. Beim Ableiten wächst das Wort Zeichen für Zeichen von links nach rechts.
Geben Sie eine reguläre Grammatik an, die genau die Wörter $a^n$ mit $n \ge 1$ erzeugt (also $a, aa, aaa, \dots$). Leiten Sie $aaa$ ab.
Geben Sie eine reguläre Grammatik an, die genau die Wörter $a^n$ mit $n \ge 1$ erzeugt (also $a, aa, aaa, \dots$). Leiten Sie $aaa$ ab.
Von Automat zu Grammatik und zurück
Endliche Automaten und reguläre Grammatiken beschreiben genau dieselben Sprachen. Du kannst deshalb jeden Automaten in eine Grammatik umwandeln und umgekehrt.
Der Grund: Ein Automat liest ein Zeichen und wechselt den Zustand. Die Grammatik erzeugt ein Zeichen und wechselt das Nichtterminal. Die Endzustände sagen, wo das Wort enden darf, und das entspricht $E \to \varepsilon$.
Das Beispiel ist ein Automat für Wörter über $\{a,b\}$, die das Teilwort $ab$ enthalten.
Für die Gegenrichtung kehrst du die Regeln um:
-
$A \to aB$ wird der Übergang $A \xrightarrow{a} B$.
-
$A \to \varepsilon$ macht $A$ zum Endzustand.
-
$A \to a$ wird ein Übergang $A \xrightarrow{a} F$ zu einem neuen Endzustand $F$ ohne weitere Übergänge.
Gibt es zu einem Zustand und einem Zeichen mehrere Regeln, ist der Automat nichtdeterministisch. Das ist hier erlaubt.
Ein Automat hat die Zustände $A$ (Start), $B$ (Endzustand) und die Übergänge $A\xrightarrow{0}A$, $A\xrightarrow{1}B$, $B\xrightarrow{0}A$, $B\xrightarrow{1}B$. a)…
Ein Automat hat die Zustände $A$ (Start), $B$ (Endzustand) und die Übergänge $A\xrightarrow{0}A$, $A\xrightarrow{1}B$, $B\xrightarrow{0}A$, $B\xrightarrow{1}B$.
- a) Beschreiben Sie die akzeptierte Sprache in Worten.
- b) Wandeln Sie den Automaten in eine reguläre Grammatik um (Zustände als Nichtterminale). Geben Sie dabei auch die $\varepsilon$-Produktion für den Endzustand an.
- c) Leiten Sie $0101$ mit der Grammatik ab.
Gegeben ist die Grammatik: $S \to aA$, $A \to bA \mid aB$, $B \to a \mid b$. a) Ermitteln Sie die erzeugte Sprache und beschreiben Sie sie in Worten. b) Zeichnen Sie…
Gegeben ist die Grammatik: $S \to aA$, $A \to bA \mid aB$, $B \to a \mid b$.
- a) Ermitteln Sie die erzeugte Sprache und beschreiben Sie sie in Worten.
- b) Zeichnen Sie einen passenden Automaten (nichtdeterministisch ist erlaubt, ein zusätzlicher Endzustand ist zulässig).
- c) Modifizieren Sie die Grammatik so, dass zusätzlich das Wort $a$ erzeugt wird.
Eine Wetterstation in Hamburg sendet Meldungen der Form: ein oder mehrere Zeichen $t$ (Temperatur), danach genau ein Zeichen $w$ (Wind), danach beliebig viele Zeichen…
Eine Wetterstation in Hamburg sendet Meldungen der Form: ein oder mehrere Zeichen $t$ (Temperatur), danach genau ein Zeichen $w$ (Wind), danach beliebig viele Zeichen $r$ (Regen).
- a) Geben Sie eine reguläre Grammatik für diese Meldungen an.
- b) Entwickeln Sie einen passenden Automaten.
- c) Prüfen Sie $ttwrr$ und $wt$.
Ein Automat über $\{a,b\}$ akzeptiert Wörter mit einer geraden Anzahl von $a$, wobei beliebig viele $b$ vorkommen dürfen. a) Geben Sie den Automaten an. b) Leiten Sie…
Ein Automat über $\{a,b\}$ akzeptiert Wörter mit einer geraden Anzahl von $a$, wobei beliebig viele $b$ vorkommen dürfen.
- a) Geben Sie den Automaten an.
- b) Leiten Sie daraus systematisch eine reguläre Grammatik ab.
- c) Zeigen Sie mit der Grammatik die Ableitung von $abab$ und erklären Sie, warum $ab$ nicht erzeugt wird.
Grenzen regulärer Sprachen
Die Wetterstation von oben ist mit einem Automaten zu prüfen. Aber nicht alles lässt sich so prüfen. Betrachte die Sprache
$$L = \{a^n b^n \mid n \ge 0\} = \{\varepsilon, ab, aabb, aaabbb, \dots\}$$Es soll also genauso viele $b$ wie $a$ geben.
Eine Grammatik für $L$ ist leicht: $S \to aSb \mid \varepsilon$. Sie ist aber nicht regulär, weil in $S \to aSb$ ein Terminalsymbol hinter dem Nichtterminal steht. Es gibt sogar gar keine reguläre Grammatik für $L$, und das lässt sich begründen.
Der Automat hat kein Gedächtnis außer seinem aktuellen Zustand. Um die $a$ zu zählen, bräuchte er für jede Anzahl $n$ einen eigenen Zustand, also unendlich viele.
Betrachten Sie die Sprache $L=\{a^n b^n \mid n \ge 0\}$. a) Geben Sie eine Grammatik an, die $L$ erzeugt. Ist Ihre Grammatik regulär? Begründen Sie. b) Erklären Sie,…
Betrachten Sie die Sprache $L=\{a^n b^n \mid n \ge 0\}$.
- a) Geben Sie eine Grammatik an, die $L$ erzeugt. Ist Ihre Grammatik regulär? Begründen Sie.
- b) Erklären Sie, warum kein endlicher Automat $L$ akzeptieren kann. Argumentieren Sie mit der endlichen Zahl der Zustände und dem Wort $a^n b^n$ für große $n$.
- c) Nennen Sie ein weiteres praktisches Beispiel einer Aufgabe, die ein endlicher Automat nicht leisten kann.
Ein Programmierer behauptet, mit einem endlichen Automaten könne man prüfen, ob in einem beliebig langen Text die Klammern $($ und $)$ korrekt gesetzt sind. a) Nehmen…
Ein Programmierer behauptet, mit einem endlichen Automaten könne man prüfen, ob in einem beliebig langen Text die Klammern $($ und $)$ korrekt gesetzt sind.
- a) Nehmen Sie Stellung zu der Behauptung und begründen Sie.
- b) Zeigen Sie, dass man für eine feste maximale Schachtelungstiefe 2 einen endlichen Automaten angeben kann. Geben Sie dessen Zustände und Übergänge an.
- c) Erläutern Sie, was dies über die Grenzen regulärer Grammatiken aussagt.
Zurück zum Anfang: Die Meldungen der Wetterstation haben eine feste Form: erst Temperatur, dann Wind, dann Regen. Diese Form beschreibt eine reguläre Grammatik, und ein endlicher Automat prüft sie. Ein Vergleich beliebig langer Anzahlen wäre dagegen mit einem endlichen Automaten nicht möglich.