Direkt zum Inhalt

Lexikon der Mathematik: nichtdeterministischer Kellerautomat

(nondeterministic pushdown automaton, NPDA), Kellerautomat mit nichtdeterministischer Überführungsrelation.

Zu einem Zustand und einem Eingabezeichen können mehrere Folgekonfigurationen, bestehend aus neuem Zustand und verändertem Kellerinhalt zur Verfügung stehen. Eine Eingabe wird durch einen nichtdeterministischen Kellerautomaten akzeptiert, falls es in jedem Zustand möglich ist, eine der zur Verfügung stehenden Folgekonfigurationen so auszuwählen, daß der Automat sich nach beendeter Eingabe in einer Akzeptierungskonfiguration befindet (üblicherweise also in einem Akzeptierungszustand, evtl. mit einem leeren Kellerspeicher).

Zu einer Sprache gibt es genau dann einen akzeptierenden nichtdeterministischen Kellerautomat, wenn sie eine kontextfreie Grammatik besitzt.

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.