DKA

Deterministischer Kellerautomat für die Sprache $a^nb^n$ :

Der Übergang $\varepsilon$/S/ hat eine besondere Bedeutung: Das Zeichen $\varepsilon$ kennst du schon als leeres Wort, d.h. also als Wort, das keine Zeichen enthält. Bei einem Kellerautomaten hat das Zeichen $\varepsilon$ eine ähnliche Bedeutung: Der Übergang $\varepsilon$/S/ ausgeführt, ohne dass ein Zeichen von der Eingabe gelesen wird. Natürlich kann der Übergang nur dann ausgeführt werden, wenn der Kellerautomat im Zustand Z1 ist und das oberste Zeichen des Kellers S ist.

Deterministischer Kellerautomat für die Sprache $(^n)^n$ :