Vorlesung Informatik 3
Einführung in die Theoretische Informatik
(12 – Kellerautomaten, PDA)
Prof. Dr. Th. Ottmann
Analyseproblem für cf. Sprachen
Beispiel: L = { anbn ; n ≥ 0} ist cf, denn L = L(G) für die cf Grammatik G mit
den Regeln S → aSb, S → ε, aber es gibt keinen endlichen Automaten,
der genau die Worte aus L akzeptiert.
Ziel: Erweiterung des Automatenmodells zum Model des Kellerautomaten
(PDA) so, dass PDAs genau die cf Sprachen erkennen können.
Idee: Ergänze endliche Automaten um einen Kellerspeicher (Stack), in dem
Informationen unbegrenzter Größe zwischengespeichert werden können.
2
Kellerautomat
3
Beispiel einer Konfigurationenfolge
Beispiel: PDA, der L = { anbn ; n ≥ 0} erkennt.
Sei K ein PDA mit 3 Zuständen s0, s1, sf.
K speichert jedes gelesene a im Keller und streicht beim Lesen von b jeweils
ein a aus dem Kellerspeicher. Zugleich prüft der Automat K, ob zuerst eine
Folge von a und dann eine Folge von b auf dem Eingabeband steht. Ist
der Keller am Ende leer, wird das Eingabewort akzeptiert, sonst nicht!
(s0, a3b3 , ┴) ├
4
Nichtderministischer Kellerautomat
Ein (nichtdeterministischer) Kellerautomat (PDA) K = (, S, Γ, δ, s0, ┴, F)
besteht aus
1. einer endlichen Menge  von Eingabesymbolen,
2. einer endlichem Menge S von Zuständen,
3. einer endlichen Menge Γ von Kellersymbolen,
4. der Zustandsübergangsrelation δ  ( S x (   {ε} ) x Γ x S x Γ* ),
5. dem Startzustand s0  S,
6. dem Keller-Bottom Symbol ┴
7. der Endzustandsmenge F  S
5
PDA für L = { anbn ; n ≥ 1}
K = (, S, Γ, δ, s0, ┴, F) ist wie folgt definiert:
 = {a, b}, S = {s0, s1, sf }, Γ = {A, ┴ }, F = { sf }
δ = { (s0, ε , ┴, sf , ε ),
(s0, a , ┴, s0 , A ┴),
(s0, a , A, s0 , AA)
(s0, b , A, s1 ,ε ),
(s1, b , A, s1 ,ε ),
(s1, ε , ┴, sf ,ε )}
6
Konfigurationsübergänge eines PDA
Eine Konfiguration k = (s, w, a)  S x * x Γ* enthält
• den aktuellen Zustand s,
• das noch zu verarbeitende Suffix w des Eingabewortes,
• den aktuellen Kellerinhalt α.
Konfigurationsübergänge sind gegeben durch die Relation ├, für die gilt:
(s, av, Aα) ├ (s‘, v, βα) gdw. (s, a, A, s‘, β)  δ ist für alle s, s‘  S, a    {ε},
α, β,  Γ*, A  Γ.
Die vom Kellerautomaten K = (, S, Γ, δ, s0, ┴, F) mit Endzustand erkannte
Sprache über  ist
LF(K) = { w  * ; (s0, w, ┴) ├* (sf, ε, γ ), sf  F, γ  Γ* }
7
Beispiel für einen deterministischen PDA
Ein Kellerautomat soll L2 = {wcsp(w) ; w  {a, b}* } erkennen, wobei sp(w) das Spiegelbild des
Wortes w bezeichnet.
K2 = ({a, b, c}, {s0, sc}, {A, B, ┴}, δ2, s0, ┴, {sc}) mit
δ2 = {((s0, c, ┴, sc, ε ),
(wenn Eingabe nur c)
(s0, a, ┴, s0, A ┴),
(erstes Zeichen a merken)
(s0, b, ┴, s0 , B ┴),
(erstes Zeichen b merken)
(s0, a, A, s0, AA),
(weitere a merken)
(s0, a, B, s0, AB),
(weitere a merken)
(s0, b, A, s0, BA),
(weitere b merken)
(s0, b, B, s0, BB),
(weitere b merken)
(s0, c, A, sc, A),
(c lesen, Keller bleibt)
(s0, c, B, sc, B),
(c lesen, Keller bleibt)
(sc, a, A, sc, ε),
(Spiegel-a lesen)
(sc, b, B, sc, ε ),
(Spiegel-b lesen)
(sc, ε, ┴, sc, ε)}
(Keller leer)
8
Konfigurationenfolge (1)
(s0, c, ┴, sc, ε ),
(s0, a, ┴, s0, A ┴),
(s0, b, ┴, s0 , B ┴),
(s0, a, A, s0, AA),
(s0, a, B, s0, AB),
(s0, b, A, s0, BA),
(s0, b, B, s0, BB),
(s0, c, A, sc, A),
(s0, c, B, sc, B),
(sc, a, A, sc, ε),
(sc, b, B, sc, ε ),
(sc, ε, ┴, sc, ε)
9
Beispiel für einen echt nichtdeterministischen PDA
Ein Kellerautomat soll L3 = {wsp(w) ; w  {a, b}* } erkennen, wobei sp(w) das Spiegelbild des Wortes w
bezeichnet.
K3 = ({a, b}, {s0, sc, sf}, {A, B, ┴}, δ3, s0, ┴, {sf}) mit
δ2 = {((s0, ε, ┴, sf, ε ),
(s0, a, ┴, s0, A ┴),
(s0, b, ┴, s0 , B ┴),
(w = ε wird akzeptiert)
(erstes Zeichen a merken)
(erstes Zeichen b merken)
(s0, a, B, s0, AB),
(a merken, wenn vorher b)
(s0, b, A, s0, BA),
(b merken, wenn vorher a)
(s0, a, A, s0, AA)
(a nach a merken, oder:
(s0, a, A, sc, ε)
(s0, b, B, sc, BB),
Spiegel-a lesen)
(b nach b merken, oder
(s0, b, B, sc, ε),
Spiegel-b lesen)
(sc, a, A, sc, ε),
(Spiegel-a lesen)
(sc, b, B, sc, ε ),
(Spiegel-b lesen)
(sc, ε, ┴, sc, ε)}
(Keller leer)
10
Konfigurationenfolge (2)
(s0, ε, ┴, sf, ε ),
(s0, a, ┴, s0, A ┴),
(s0, b, ┴, s0 , B ┴),
(s0, a, B, s0, AB),
(s0, b, A, s0, BA),
(s0, a, A, s0, AA)
(s0, a, A, sc, ε)
(s0, b, B, sc, BB),
(s0, b, B, sc, ε),
(sc, a, A, sc, ε),
(sc, b, B, sc, ε ),
(sc, ε, ┴, sc, ε),
11
Akzeptieren mit leerem Keller
Sei K = (, S, Γ, δ, s0, ┴, F) ein Kellerautomat. Die von K mit leerem Keller
akzeptierte Sprache über  ist:
Lε (K) = { w  * ; (s0, w, ┴) ├* (s, ε, ε ), s  S }
Satz: Die Klasse der von Kellerautomaten mit Endzustand akzeptierbaren
Sprachen stimmt überein mit der Klasse der von Kellerautomaten mit
leerem Keller akzeptierbaren Sprachen.
Bew. (1), Idee: Zu einem PDA A konstruiert man einen PDA A‘ mit
LF(A) = Lε (A‘) so, dass A‘ seinen Keller leert, wenn A in einen Endzustand
übergeht.
Bew. (2), Idee: Zu einem PDA A konstruiert man einen PDA A‘ mit
Lε (A) = LF(A‘) so, dass A‘ in einen Endzustand übergeht, wenn A seinen
Keller geleert hat.
12
Äquivalenz von cf Grammatiken und PDA(1)
Satz: Zu jeder cf Grammatik G = (V, , R, S) kann man einen PDA K
angeben, so dass L(G) = Lε(K).
Bew.: K wird so konstruiert, dass Linksableitungen von G simuliert werden:
Ist das aktuelle Eingabesymbol = Keller-Topsymol, so wird es gelesen bzw.
gelöscht.
Ist Keller-Topsymbol = A  V, so wird kein Eingabesymbol gelesen, und A
wird durch α ersetzt, falls A → α  R.
Keller Bottomsymbol ist S.
Bem.: Ein Zustand q reicht aus! Der PDA K wird auch Parser von G genannt.
13
Beispiel: PDA für eine cf Grammatik
Betrachte G = ({a, b}, {S}, { S →aSb | ε }, S) mit L(G) = {anbn ; n ≥ 0}. Der
Parser für G ist der PDA K = ({a, b}, {q}, {a, b, S}, δ, q, S, ) mit
δ = {(q, a, a, q, ε), (q, b, b, q, ε), (q, ε, S, q, aSb), (q, ε, S, q, ε)}.
Beispiel einer akzeptierenden Konfigurationenfolge für w = aaabbb:
14
Äquivalenz von cf Grammatiken und PDA(2)
Satz 2: Zu jedem PDA K kann man eine cf Grammatik G angeben mit
Lε(K) = L(G)
15

12-Kellerautomaten