Coder Wiki | HowTos | Konstruktion eines Kellerautomaten

In diesem Kochrezept bilden wir einen Kellerautomaten ? für die Sprache: L = {aⁿb^m | m < n}.

Beginnen wir mit einem Beispiel für 3 typische Anwendungen.
Der ursprüngliche Kellerautomat sieht so aus:

Anwendung 1: Lies a₁, Pop k₀, neuer Zustand ist s₁, Push a₁ (anstelle k₀) ergibt folgende neue Konfiguration.
δ (s₀,a₁, k₀) = (s₁,a₁)

Anwendung 2: Lies nichts!, Pop k₀, neuer Zustand ist s₁, Push k₀
δ (s₀,ε, k₀) = (s₁, k₀)

Anwendung 3: Lies a₁, Pop k₀, neuer Zustand ist s₁, Push a₁k₀
δ (s₀,a₁, k₀) = (s₁,a₁k₀)

Wir verwenden hier die ausführliche Schreibweise. Die Kurzschreibweise wäre ein Tupel ? aus Ausgangszustand, einzulesendem Wort und dem aktuellem Kellerband.

Wir beginnen mit:

δ (S₀,a,k₀)

(S₁,k₀)

Zuerst lesen wir alle "a" in den Keller

δ (S₀,a,k₀)	=	(S₁,ak₀)
δ (S₀,a,a)	=	(S₁,aa)

Dann löschen wir die b's aus der Eingabe gegen die a's aus dem Keller

δ (S₁,b,a)	=	(S₂,ε)
δ (S₁,b,a)	=	(S₂,ε)

Zusammengesetzt sieht es dann so aus:

δ (S₀,a,k₀)	=	(S₁,k₀)
δ (S₀,a,k₀)	=	(S₁,ak₀)
δ (S₀,a,a)	=	(S₁,aa)
δ (S₁,b,a)	=	(S₂,ε)
δ (S₁,b,a)	=	(S₂,ε)

Coder How To's

Konstruktion eines Kellerautomaten