Nichtdeterministische Kellerautomaten (NKA)

Wiki-Quelltext dieser Seite.

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

;Die von <math>M</math> akzeptierte Sprache <math>L(M)</math>
Auf das Eingabeband von <math>M</math> wird das zu analysierende Wort <math>w</math> geschrieben. Der Automat befindet sich im Anfangszustand <math>q_0</math> und im Keller steht nichts weiter als das Vorbelegungszeichen <math>k_0</math>. 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. <math>M</math> akzeptiert genau die Wörter über dem Eingabealphabet, die den Automat nach vollständigem Einlesen des Wortes in einen Endzustand <math>q_e\in E</math> stoppen lassen. Der Kellerinhalt am Ende spielt keine Rolle.

Das Eingabewort wird im Prolog-Programm als Liste repräsentiert.
<code id="4a98fd6db361d">
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).
</code>

;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.
<code id="4a98fd6db41d6">
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,[#]).
</code>

Wir fragen, ob das Wort <math>rentner</math> zu der von dem Beispielautomaten akzeptierten Sprache gehört:
<run id="4a98fd6db4d8c">
accept([r,e,n,t,n,e,r]).
</run>

Fehlt hingegen das letzte <math>r</math>, so wird das Wort nicht akzeptiert:
<run id="4a98fd6db594d">
accept([r,e,n,t,n,e]).
</run>

===Übungsaufgaben===

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