Ein PDA ist ein Kellerautomat. Aus einer kontextfreien Grammatik kann man problemlos einen PDA erstellen. Dabei kommt man mit einem einzigen Zustand aus.
Ein Beispiel aus einer Grammatik:
S -> AX | BY | a
Um aus der Grammatik den PDA zu bilden geht man die Liste von oben nach unten durch und setzt sie in eine PDA-Zeile ein. Normalerweise hat man ja noch mehr zu übersetzen als nur das S, da A, X, Y und B auch noch zugeordnet werden müssen. Als Beispiel deckt das S aber jeden Fall ab.
Die Syntax:
(Zustand, Kellersymbol, Eingabe, Folgekellersymbol, Folgezustand)
Zuallererst wird ein Einstieg benötigt:
(q0, #, ?, S, q0)
Nun können die Zeilen der Grammatik angehängt werden, hier die S-Zeile von oben:
(q0, S, ?, AX, q0)
(q0, S, ?, BY, q0)
(q0, S, a, ?, q0)
An der Übersetzung kann man schon das ganze Schema ablesen. Die beiden q0 bleiben immer gleich. S ist das S von vor dem Pfeil.
An die dritte Stelle, die Eingabe, kommt das ?, wenn das betrachtete Zeichen noch weiter aufgelöst werden kann, dann kommt das Zeichen als Folgekellersymbol selbst in die vierte (so beim AX und beim BY gemacht).
Genau andersrum funktioniert es bei dem a: das kommt direkt in die Eingabe. Das ? füllt dann die vierte Stelle, ein echtes Folgekellersymbol gibt es in dem Fall ja nicht.
Diesem Schema folgend geht man nun die ganze Grammatik durch. Der Einstieg muss natürlich nur einmal gesetzt werden, ganz am Anfang.
Zusatz: Die so gebildeten Transitionen sind nur ein Teil des PDAs. Die Zustandsmenge Q und die akzeptierende Zustandsmenge A beinhalten aber nur {q0} - andere Zustände werden ja nicht angelegt. Das Kelleralphabet besteht aus den Zeichen vor den Pfeilen, hier also dem S.