Allgemeine Informatik WS 2000/01
Prof. Dr. H. Neumann $\bullet$ Dr. K. Murmann $\bullet$ S. Geschwentner $\bullet$ Dr. F. Schwenker

11. Aufgabenblatt (bis zum 14.02.2001)

28. Aufgabe.
Gegeben sei die Grammatik $G= (S_N,S_T,P,\omega_s\in S_N)$ mit der Nichtterminalmenge $S_N = \{ A, B \}$, der Terminalmenge $S_T = \{ a, b, c, d\}$, dem Startsymbol $\omega_s = A\in S_N$ und der Produktionenmenge $P=\{ A \to Bc, B \to aBb, B \to d \}$.

Beschreiben Sie die von $G$ erzeugte Sprache $L=L(G)$ informell. Welche der folgenden Symbolfolgen gehören zu $L$? (Begründen Sie Ihre Antwort!)


aadbbc aaadbbbbc adb dc

29. Aufgabe.
Gegeben sei der endliche Automat $M=(Z,I,\delta:Z\times I\to Z,z_0\in Z, T\subseteq Z)$ mit der Zustandsmenge $Z=\{z_0,z_1,z_2,z_3\}$, dem Eingabealphabet $I=\{a,b\}$, dem Anfangszustand $z_0 \in Z$, der Menge der Endzustände $T=\{z_3\}$ und der Zustandsübergangsfunktion $\delta$ gegeben durch die Tabelle:

	$a$	$b$
$z_0$	$z_3$	$z_1$
$z_1$	$z_1$	$z_1$
$z_2$	$z_1$	$z_1$
$z_3$	$z_2$	$z_0$

Geben Sie eine graphische Darstellung (Zustandsgraph) von $M$ an.

30. Aufgabe.
Beschreiben Sie die vom endlichen Automaten $M$ aus Aufgabe 29 akzeptierte Sprache $L$ informell.

Zusatzaufgabe: Geben Sie einen regulären Ausdruck für $L$ an.