Der Kellerautomat als Parser kontextfreier Sprachen


Die Arbeitsweise des Kellerautomaten


Beispiel eines Kellerautomaten


Grenzen des Kellerautomaten

 

Startseite 
Die Leistungsfähigkeit Endlicher Automaten hat Grenzen:
Es fehlt ein Gedächtnis, um sich beliebig tief geschachtelte Klammern zu merken. Sprachen mit derartigen Klammerstrukturen sind kontextfrei und können demnach mit Akzeptoren nicht erkannt werden.

Beispiel: Die kontextfreie Grammatik über dem Alphabet
  { ( , ) , P }   mit den Produktionsregeln

S --> S S | ( S ) | ( P )

erzeugt zum Beispiel folgende Worte:      (P),  ((P)(P)),   (((P)(P)(P))(P))    .


Aufgabe des Kellerautomaten ist es nun, die Anzahl der öffnenden und schließenden Klammern zu vergleichen. Dazu braucht er ein Gedächtnis.   Als Gedächtnis dient dem Automat ein Kellerspeicher oder Stapel (stack).