Theorie - Kontextfreie Sprachen und Kellerautomaten

Von der kontextfreien Grammatik zum Kellerautomaten

Kellerautomaten sind in der Lage, Ableitungen mit einer kontextfreien Grammatik zu simulieren. Wir verdeutlichen diese Simulation anhand eines Beispiels.

Gegeben sei eine Grammatik G für die Sprache L_ab = {aⁿbⁿ | n = 1, 2, 3, ...} der Klammerausdrücke:

S -> aSb
S -> λ

Zur Grammatik G lässt sich der Kellerautomat K_G konstruieren:

Beachte, dass alle Produktionen der Grammatik in den Zustandsübergängen des Kellerautomaten kodiert sind. Der Kellerauromat ist so konstruiert, dass jede Ableitung mit Produktionen der Grammatik G mit Hilfe von Zustandsübergängen des Kellerautomaten simuliert werden kann. Wir verdeutlichen dies anhand der folgenden Ableitung des Worts aabb:

   S 
-> aSb
-> aaSbb
-> aabb

Diese Ableitung lässt sich mit dem Kellerautomaten wie folgt nachbilden:

Zustand; Kellerinhalt   Eingabewort