Nichtdeterministische Kellerautomaten (NKA)

Aus ProgrammingWiki

Definition

Ein NKA ist ein 7-Tupel , mit
... endliche Menge von Zuständen,
... Eingabealphabet,
... Stackalphabet,
... partielle Überführungsfunktion,
... Anfangszustand ,
... Stackvorbelegungszeichen ,
... endliche Menge von Endzuständen

Die von akzeptierte Sprache

Auf das Eingabeband von wird das zu analysierende Wort geschrieben. Der Automat befindet sich im Anfangszustand und im Keller steht nichts weiter als das Vorbelegungszeichen . In jedem Schritt wird das oberste Kellerzeichen verbrauchend gelesen und ein Kellerwort auf den Stapel geschrieben. Spontane Übergänge, bei denen kein Eingabezeichen verbraucht wird, stellen einen Sonderfall dar. akzeptiert genau die Wörter über dem Eingabealphabet, die den Automat nach vollständigem Einlesen des Wortes in einen Endzustand stoppen lassen. Der Kellerinhalt am Ende spielt keine Rolle.

Das Eingabewort wird im Prolog-Programm als Liste repräsentiert.

accept(Xs) :- initial(Q), accept(Xs,Q,[#]). % # ist das Kellervorbelegungszeichen accept([X|Xs],Q,S) :- delta(Q,X,S,Q1,S1), accept(Xs,Q1,S1). accept([],Q,S) :- final(Q).

Beispiel

Wir betrachten die Sprache der Palindrome über irgendeinem Alphabet. Im Gegensatz zu den Festlegungen der theoretischen Informatik, wird dieses Alphabet in der folgenden Prolog-Beschreibung dieses NKA nicht angegeben. Das spart Schreibaufwand, da mehrere Regeln durch Parametrisierung zusammengefasst werden.

accept(Xs) :- length(Xs,0). % Das leere Wort ist ein Palindrom. accept(Xs) :- length(Xs,1). % Jedes Wort der Länge 1 ist ein Palindrom. initial(q1). final(q3). delta(q1,X,S,q1,[X|S]). % Kellern delta(q1,X,S,q2,S). % Wechsel zu Entkellern, ungerade Wortlänge, beliebiges Zeichen in der Mitte delta(q1,X,S,q2,[X|S]). % Wechsel zu Entkellern, gerade Wortlänge delta(q2,X,[X|S],q2,S). % Entkellern delta(q2,X,[X,#],q3,[#]).

Wir fragen, ob das Wort zu der von dem Beispielautomaten akzeptierten Sprache gehört:

accept([r,e,n,t,n,e,r]).

ausführen

Fehlt hingegen das letzte , so wird das Wort nicht akzeptiert:

accept([r,e,n,t,n,e]).

ausführen

Übungsaufgaben

1. Entwickeln Sie einen NKA für die Sprache .