Aufgaben: Reguläre Grammatiken und Grenzen

Gegeben ist die Grammatik $G$ mit Startsymbol $S$ und den Produktionen:

$S \to aS \mid bA$, $A \to b \mid \varepsilon$

1. a) Leiten Sie das Wort $aabb$ Schritt für Schritt ab.

1. b) Geben Sie zwei weitere Wörter der Sprache an.

1. 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$.

1. a) Nennen Sie Terminal- und Nichtterminalsymbole.

1. b) Leiten Sie $0101$ ab.

1. c) Beschreiben Sie die erzeugte Sprache in Worten.

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.

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$.

1. a) Beschreiben Sie die akzeptierte Sprache in Worten.

1. 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.

1. 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$.

1. a) Ermitteln Sie die erzeugte Sprache und beschreiben Sie sie in Worten.

1. b) Zeichnen Sie einen passenden Automaten (nichtdeterministisch ist erlaubt, ein zusätzlicher Endzustand ist zulässig).

1. 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 $r$ (Regen).

1. a) Geben Sie eine reguläre Grammatik für diese Meldungen an.

1. b) Entwickeln Sie einen passenden Automaten.

1. c) Prüfen Sie $ttwrr$ und $wt$.

Betrachten Sie die Sprache $L=\{a^n b^n \mid n \ge 0\}$.

1. a) Geben Sie eine Grammatik an, die $L$ erzeugt. Ist Ihre Grammatik regulär? Begründen Sie.

1. 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$.

1. c) Nennen Sie ein weiteres praktisches Beispiel einer Aufgabe, die ein endlicher Automat nicht leisten kann.

Ein Automat über $\{a,b\}$ akzeptiert Wörter mit einer geraden Anzahl von $a$, wobei beliebig viele $b$ vorkommen dürfen.

1. a) Geben Sie den Automaten an.

1. b) Leiten Sie daraus systematisch eine reguläre Grammatik ab.

1. c) Zeigen Sie mit der Grammatik die Ableitung von $abab$ und erklären Sie, warum $ab$ nicht erzeugt wird.

Ein Programmierer behauptet, mit einem endlichen Automaten könne man prüfen, ob in einem beliebig langen Text die Klammern $($ und $)$ korrekt gesetzt sind.

1. a) Nehmen Sie Stellung zu der Behauptung und begründen Sie.

1. 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.

1. c) Erläutern Sie, was dies über die Grenzen regulärer Grammatiken aussagt.