Deterministische und nichtdeterministische Kellerautomaten

Deterministische vs. nichtdeterministische Kellerautomaten

Ein deterministischer Kellerautomat entsteht aus einem nichtdeterministischen Kellerautomaten indem folgende zusätzliche Bedingungen an den Kellerautomaten gestellt werden:

1)   Der Kellerautomat darf für jedes (aktueller Zustand, aktuelle Eingabe, aktuelles oberstes Kellerelement)-Tripel keine oder nur eine Übergangsmöglichkeit besitzen.

2)   Für das (aktueller Zustand, leeres Wort, aktuelles oberstes Kellerelement)-Tripel darf es kein anderes Tripel mit selbem Zustand und selbem oberstem Kellerelement geben, dass nicht das leere Wort als aktuelle Eingabe einliest. Das würde ja bedeuten, dass der Kellerautomat raten müsste, ob er was einliest oder einfach nichts einliest – was genau die Eigenschaft eines nichtdeterministischen Kellerautomatens ist.