Theoretische Informatik

Definition:  Ein nicht­deterministischer Stackautomat ¹) ist ein Tupel

N  =  (Z, E, H, d, q, F).

Hierbei ist

Z		eine endliche, nichtleere Menge von Zuständen,
E		das Eingabe­alphabet, ferner sei E? = E  {ε},
H		das Stack­alphabet, ferner sei H? = H  {ε},
d		die Übergangs­relation   d    Z E? H? H? Z,
q  Z		der Startzustand,
F  Z		die Menge der Endzustände.

Definition:  Sei N ein Stackautomat.

Der Stackautomat erkennt das Wort w durch Endzustand, wenn es eine Folge von Zustands­übergängen gibt, die das Eingabewort w vollständig abarbeitet und einen Endzustand erreicht.

Der Stackautomat erkennt die Sprache L durch Endzustand, wenn er jedes Wort w  L durch Endzustand erkennt und jedes Wort w  L verwirft.

Der Stackautomat erkennt das Wort w durch leeren Stack, wenn es eine Folge von Zustands­übergängen gibt, die das Eingabewort w vollständig abarbeitet und einen leeren Stack hinterlässt.

Der Stackautomat erkennt die Sprache L durch leeren Stack, wenn er jedes Wort w  L durch leeren Stack erkennt und jedes Wort w  L verwirft.

Beispiel:  Der folgende Stackautomat N  = (Z, E, H, d, q, F) erkennt die Sprache { aⁿbⁿ  |  n  ₀ } durch leeren Stack.

Z  =		{0, 1}
E  =		{a, b}
H  =		{a}
q  =		0
F  =
d :

Der Stackautomat legt solange jedes gelesene a auf den Stack, bis er das erste b liest. Für jedes gelesene b entfernt er anschließend ein a vom Stack.

Der Stackautomat ist sogar deterministisch.

Satz:  Ein nicht­deterministischer Stackautomat, der eine Sprache L durch Endzustand erkennt, kann in einen nicht­deterministischen Stackautomaten, der dieselbe Sprache L durch leeren Stack erkennt, umgeformt werden und umgekehrt.

Beweis:  

Leerer Stack    Endzustand

Ein Stackautomat, der eine Sprache L durch leeren Stack erkennt, wird folgendermaßen in einen Stackautomaten umgeformt, der die Sprache L durch Endzustand erkennt.

Zu Beginn wird zunächst ein spezielles neues Stackzeichen $ als Begrenzungszeichen auf den Stack gelegt. Ein Wort w  L wird dann nicht durch leeren Stack erkannt, sondern dadurch, dass nur noch das Zeichen $ im Stack steht. Mit diesem Zeichen wird vom jeweiligen Zustand s, in dem sich der Stackautomat dann befindet, ein Zustands­übergang in einen neuen Endzustand f durchgeführt.

Es kommt also zunächst das Tupel

zur Übergangs­relation hinzu. Hierbei ist q' der neue Startzustand des Stackautomaten, q der bisherige Startzustand.

Für jeden Zustand s  Z kommen ferner die Tupel

zur Übergangs­relation hinzu. Hierbei ist f ein neuer Zustand, der Endzustand, d.h. es gilt F = {f}.

Beispiel:

Der Stackautomat aus dem vorigen Beispiel wird folgendermaßen umgeformt; die neuen Zustands­übergänge sind hellgelb hinterlegt:

Hierbei ist -1 der neue Startzustand q' und 2 ist der neu eingeführte Endzustand f.

Endzustand    leerer Stack

Umgekehrt kann ein Stackautomat, der eine Sprache L durch Erreichen eines Endzustands erkennt, in einen Stackautomaten umgeformt werden, der dieselbe Sprache L durch leeren Stack erkennt.

Zu Beginn wird ebenfalls wieder ein neues Stackzeichen $ als Begrenzungszeichen auf den Stack gelegt. Hierdurch ist gewährleistet, dass der ursprüngliche Stackautomat keinen leeren Stack hinterlässt.

Es kommt also zunächst das Tupel

zur Übergangs­relation hinzu. Hierbei ist s₀' der neue Startzustand des Stackautomaten, q der bisherige Startzustand.

Es werden dann von jedem Endzustand aus Zustands­übergänge hinzugefügt, die den Stack leeren. Es kommen also Tupel der Form

für alle Endzustände f  F und alle Stackzeichen h  H (einschließlich des neuen Zeichens $) zur Übergangs­relation hinzu. Hierbei ist t ein neuer Zustand.

Aufgabe 1:  Sei A = {a, b} ein Alphabet und sei L  A* mit

L  =  { w  |  n_a(w) = n_b(w) }

die Sprache aller Wörter, die gleichviele a's und b's enthalten.

Geben Sie einen Stackautomaten an, der L durch leeren Stack erkennt.

Aufgabe 2:  Geben Sie je einen Stackautomaten an, der die Sprache  a*  aⁿbⁿ  erkennt, und zwar

1. durch Erreichen eines Endzustands,
2. durch leeren Stack.