Nichtdeterministischer / deterministischer Stackautomat

Es gibt Sprachen, die von einem nichtdeterministischen Stackautomaten erkannt werden, aber von keinem deterministischen Stackautomaten.

Ein Beispiel für eine solche Sprache ist die Sprache

L  =  { ww^R  |  w ∈ {a, b}*,   w^R ist das Spiegelbild von w }

also die Menge aller Wörter, die sich in w und w rückwärts gelesen zerlegen lassen.

Ein solches Wort ist beispielsweise abba, mit w = ab und w^R = ba.

Der folgende nichtdeterministische Stackautomat N  = (Z, E, H, d, q, F) erkennt die Sprache aller Wörter der Form ww^R über dem Alphabet {a, b}.

Eingabeband

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Stack

Eingabewort

   

 

s	e	h	h'	s'
0	ε	ε	$	1
1	a	ε	a	1
1	b	ε	b	1
1	ε	ε	ε	2
2	a	a	ε	2
2	b	b	ε	2
2	ε	$	ε	3*

Wenn du den Stackautomaten simulierst, legst du als Erstes das Stack-Ende-Zeichen $ auf den Stack.

Dann legst du zunächst alle gelesenen Zeichen von w auf den Stack und anschließend entfernst du diese korrespondierend zu den gelesenen spiegelbildlichen Zeichen von w^R wieder vom Stack.

An der Grenze zwischen w und w^R schaltest du von "Ablegen auf dem Stack" zu "Entfernen vom Stack" um, indem du den Zustandsübergang 1 ε ε ε 2 vollführst (gelbes Feld in der Übergangsrelation anklicken).

Als Mensch siehst du zwar durch scharfes Hinsehen, wo diese Stelle ist, also die Mitte des Eingabewortes – ein Stackautomat jedoch kann dies nicht sehen, er kann dies nur nichtdeterministisch sozusagen raten. Hier ist wirklich Nichtdeterminismus gefragt.

Es gibt keinen deterministischen Stackautomaten, der die Sprache L erkennt, denn ein deterministischer Stackautomat weiß nicht, wo w endet und w^R beginnt.