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 das richtige Format hat. Man kann dieses Format auf zwei Arten beschreiben: durch einen Automaten, der Wörter erkennt, oder durch eine Grammatik, die Wörter erzeugt. Beide Beschreibungen sind bei regulären Sprachen gleich mächtig. Und es gibt Formate, die sich mit keiner von beiden beschreiben lassen. Am Ende kannst du begründen, warum.
Reguläre Grammatiken und Ableitungen
Ein Automat erkennt Wörter. Eine Grammatik geht den umgekehrten Weg: Sie erzeugt Wörter durch Ersetzungsregeln.
Eine Schreibweise spart Platz: $S \to aS \mid bA$ bedeutet zwei Produktionen, $S \to aS$ und $S \to bA$.
Beim Ableiten startest du mit $S$ und ersetzt in jedem Schritt das Nichtterminal nach einer Produktion. Ein Schritt wird mit $\Rightarrow$ notiert. Sobald kein Nichtterminal mehr da ist, ist das Wort fertig.
Die Sprache dieser Grammatik: beliebig viele $a$ (auch keines), dann ein $b$, dann optional noch ein $b$. Also $L = \{a^n b,\ a^n bb \mid n \ge 0\}$.
Allgemein: Um zu zeigen, dass ein Wort zur Sprache gehört, gibst du eine Ableitung an. Um zu zeigen, dass es nicht dazugehört, begründest du, warum jede Ableitung scheitern muss.
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.
Grammatiken entwerfen
Wie entwirft man eine Grammatik für eine gegebene Sprache? Denke in Stationen: Jedes Nichtterminal merkt sich, „wo man im Wort gerade ist“.
Das Muster „Nichtterminal ruft sich selbst auf“ (Rekursion) erzeugt beliebig lange Wiederholungen. Die Reihenfolge der Nichtterminale legt fest, in welcher Reihenfolge die Teile des Wortes entstehen.
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.
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$.
Automat und Grammatik umwandeln
Automaten und reguläre Grammatiken beschreiben genau dieselben Sprachen, nämlich die regulären Sprachen. Die Umwandlung ist mechanisch:
Der Grund: Der Automat liest ein Zeichen und wechselt den Zustand. Die Grammatik erzeugt ein Zeichen und wechselt das Nichtterminal. Ein Wort wird akzeptiert, wenn man im Endzustand aufhören darf. Das entspricht genau der $\varepsilon$-Produktion.
Umgekehrt (Grammatik → Automat) gehst du rückwärts: Nichtterminale werden Zustände, $X \to aY$ wird ein Übergang $X \xrightarrow{a} Y$. Für eine Produktion $X \to a$ führst du einen zusätzlichen Endzustand $F$ ein und zeichnest $X \xrightarrow{a} F$. Für $X \to \varepsilon$ wird $X$ Endzustand. Entstehen dabei zwei Übergänge mit gleichem Zeichen aus einem Zustand, ist der Automat nichtdeterministisch. Das ist 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.
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
Kann man alles mit endlichen Automaten prüfen? Nein. Ein Automat hat nur endlich viele Zustände und besitzt außer dem aktuellen Zustand keinen Speicher.
Betrachte $L = \{a^n b^n \mid n \ge 0\}$: erst $n$ mal $a$, danach genau gleich viele $b$.
Eine Grammatik dafür ist leicht: $S \to aSb \mid \varepsilon$. Sie ist aber nicht regulär, denn in $S \to aSb$ steht nach dem Nichtterminal noch ein Terminal. Das ist genau der Trick, der das Mitzählen ermöglicht.
Anschaulich: Zum Zählen der $a$ müsste sich der Automat die Anzahl merken. Für beliebig großes $n$ bräuchte er beliebig viele Zustände.
Zurück zum Anfang: Die Wetterstation-Meldungen („$t^+ w\, r^*$“) sind regulär, ein Server kann sie mit einem kleinen Automaten prüfen. Ein Format, das „genauso viele $r$ wie $t$“ verlangt, wäre es nicht.
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.