Nichtdeterministische Kellerautomaten (NKA)

Aus ProgrammingWiki

Definition

Ein NKA ist ein 7-Tupel M = (Q,\Sigma,\Gamma,\delta,q_0,k_0,E), mit
Q ... endliche Menge von Zuständen,
\Sigma ... Eingabealphabet,
\Gamma ... Stackalphabet,
\delta ... partielle Überführungsfunktion, Q\times(\Sigma\cup\{\varepsilon\})\times\Gamma\mapsto\wp{(Q\times\Gamma^*)}
q_0 ... Anfangszustand (q_0\in Q),
k_0 ... Stackvorbelegungszeichen (k_0\in\Gamma \text{ und } k_0 \not\in\Sigma),
E ... endliche Menge von Endzuständen (E\subseteq Q)

Die von M akzeptierte Sprache L(M)

Auf das Eingabeband von M wird das zu analysierende Wort w geschrieben. Der Automat befindet sich im Anfangszustand q_0 und im Keller steht nichts weiter als das Vorbelegungszeichen k_0. 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. M akzeptiert genau die Wörter über dem Eingabealphabet, die den Automat nach vollständigem Einlesen des Wortes in einen Endzustand q_e\in E 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 rentner zu der von dem Beispielautomaten akzeptierten Sprache gehört:

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

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

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

Übungsaufgaben

Entwickeln Sie einen NKA für die Sprache L(M)=\{w\mid w=a^nb^n, n>0\}.

Nichtdeterministische Kellerautomaten (NKA)

Übungsaufgaben

Suche