Logo des digitalen Schulbuchs inf-schule.de. Schriftzug in Zustandsübergangsdiagramm eines endlichen Automaten.

KIDS

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 Lab = {anbn | n = 1, 2, 3, ...} der Klammerausdrücke:

S -> aSb
S -> λ

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

Kellerautomat

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
X

Fehler melden

X

Suche