Kellerautomaten

Kellerautomat-Aufgaben.pdf

$X=\{a,b\}$ $Z=\{q_0,q_1,q_2\}$ $ZE=\{q_1\}$ $\Gamma =\{\#,a,b\}$

Wort 1: $q_0\to q_1(a\#)\to q_1(aa\#)\to q_1(a\#)q_1(\#)\to q_0$ Wort 2: Nicht akzeptiert Wort 3: Nicht akzeptiert

Der Automat überprüft, ob die gleiche Anzahl von $a$ und $b$ Zeichen in einem Wort enthalten ist. Die Buchstaben müssen dabei auch in Stapel sortiert sein.

$\Sigma =\{a,b\}$ $T=\{\}$