Theoretische Informatik

Satz:  Die nichtdeterministischen String-Turingmaschinen vom Typ 2 erkennen genau die kontextfreien Sprachen.

Satz:  Sei L eine kontextfreie Sprache. Dann gibt es eine nichtdeterministische String-Turingmaschine vom Typ 2, die L erkennt.

Beweis:  Sei L eine kontextfreie Sprache. Dann gibt es eine kontextfreie Grammatik G ohne Epsilon-Produktionen, die L erzeugt. Als Ausnahme ist die Epsilon-Produktion Sε erlaubt, wenn das leere Wort ε in der Sprache L vorkommt. Wir konstruieren aus G eine Typ-2-String-Turingmaschine, die ein beliebiges Eingabewort aus L(G) durch Anwendung der Produktionen von G auf das Startsymbol S reduziert und anschließend das Startsymbol und die beiden Begrenzungszeichen $ und & löscht.

Konstruktion

Das Eingabealphabet E der String-Turingmaschine ist gleich der Menge der Terminalzeichen T der Grammatik. Das Arbeitsalphabet A der String-Turingmaschine besteht aus aus allen Zeichen der Grammatik, also Variablen und Terminalzeichen, sowie den Begrenzungszeichen $ und &; diese dürfen nicht in der Grammatik vorkommen. Die Zustandsmenge Z der String-Turingmaschine besteht zunächst nur aus den Zuständen {0, 1, 2, 3}; der Zustand 0 ist der Startzustand. Im Verlauf der folgenden Konstruktion kommen neue Zustände hinzu.

1. Für jede Produktion X → u₀ ... u_k-1 der Grammatik G werden folgende Tupel in die Übergangsrelation der String-Turingmaschine aufgenommen:

   s	a	a'	s'
   0	uk-1	D	sk-1
   sk-1	uk-2	D	sk-2
   s1	u0	X	0

   Hierbei sind s₁, ..., s_k-1 neue Zustände, die speziell für diese Produktion zur Zustandsmenge hinzugenommen werden.

   Mithilfe dieser Zustandsübergänge reduziert die String-Turingmaschine die rechte Seite u₀ ... u_k-1 der Produktion auf die linke Seite X.

2. Für jedes Zeichen a der Grammatik, sowohl für Variablen als auch für Terminalzeichen, sowie für a = $ wird ein Tupel

   s	a	a'	s'
   0	a	R	0

   in die Übergangsrelation der String-Turingmaschine aufgenommen. Hierdurch ist es der String-Turingmaschine möglich, sich in ihrem Arbeitsstring nach rechts zu bewegen.

3. Schließlich werden noch die Tupel

   0	&	D	1
   1	S	D	2
   2	$	D	3

   hinzugefügt, um das Startsymbol S der Grammatik einschließlich der beiden Begrenzungszeichen $ und & zu löschen.

4. Wenn die Produktion Sε in G enthalten ist, wird zusätzlich noch das Tupel

   s	a	a'	s'
   1	$	D	3

   hinzugefügt, um ein leeres Eingabewort einschließlich der beiden Begrenzungszeichen $ und & löschen zu können.

 

Arbeitsweise der String-Turingmaschine

Die String-Turingmaschine startet im Zustand 0 und geht in ihrem Arbeitsstring jeweils entweder nach rechts oder wendet eine Produktion an, indem sie die Zustandsübergänge aus Schritt 1 der Konstruktion ausführt. Sie tut dies nichtdeterministisch, d.h. wenn das Eingabewort in der Sprache L vorkommt, wählt sie immer die jeweils richtigen Zustandsübergänge, die am Ende zum Erkennen des Eingabewortes führen.

 

Gleichheit der Sprachen

Wenn ein Wort x sich durch Anwendung der Produktionen der Grammatik G auf das Startsymbol S reduzieren lässt, so ist die konstruierte String-Turingmaschine in der Lage, diese Reduktion nachzubilden und x zu erkennen.

Wenn umgekehrt ein Wort x von der String-Turingmaschine erkannt wird, so entsprechen Folgen von Zustandsübergängen, die aus Schritt 1 der Konstruktion stammen, jeweils Reduktionsschritten der Grammatik (diese Folgen von Zustandsübergängen können nur im Zusammenhang ausgeführt werden, da sie über die neu eingeführten Zustände laufen). Der gesamten Folge von Zustandsübergängen, die zur Erkennung des Wortes x führt, entspricht also eine Reduktionsfolge der Grammatik. Somit gehört x zu L(G).

Beispiel:  Das Konstruktionsverfahren wird auf die folgende Grammatik angewendet:

Die Grammatik erzeugt die Sprache L = { aⁿbⁿ  |  n ∈ ℕ }. Durch Anwendung des Konstruktionsverfahrens ergibt sich aus dieser Grammatik die folgende Übergangsrelation einer Typ-2-String-Turingmaschine:

Die ersten Tupel der Übergangsrelation entsprechen den Anwendungen der Produktionen aus Schritt 1 der Konstruktion; beispielsweise entsprechen die ersten beiden Tupel der Anwendung der Produktion SAb, indem im Arbeitsstring b gelöscht wird und A durch S überschrieben wird. Es folgen die Tupel mit der Cursor-Aktion R aus Schritt 2 der Konstruktion und zum Schluss die Tupel aus Schritt 3.

Satz:  Sei M eine nichtdeterministische String-Turingmaschine vom Typ 2 und sei L(M) die Sprache, die von M erkannt wird. Dann ist L(M) kontextfrei, also vom Typ 2.

Beweis:  Wir konstruieren aus der nichtdeterministischen Typ-2-String-Turingmaschine M einen nichtdeterministischen Stackautomaten N in der Weise, dass L(N) = L(M) gilt. Von der Sprache L(N) wissen wir, dass sie kontextfrei ist, denn die nichtdeterministischen Stackautomaten erkennen genau die kontextfreien Sprachen.

Konstruktion

Die Zustandsmenge Z' des Stackautomaten ist zunächst gleich Z, der Zustandsmenge der String-Turingmaschine; im Verlauf der Konstruktion kommen aber noch weitere Zustände hinzu. Eingabe- und Stackalphabet des Stackautomaten sind gleich dem Arbeitsalphabet der String-Turingmaschine. Die Tupel der Übergangsrelation d der String-Turingmaschine werden wie folgt in entsprechende Tupel der Übergangsrelation d' des Stackautomaten umgeformt.

1. Ein Tupel der Form (s, a, R, t) der Übergangsrelation d der String-Turingmaschine bedeutet, dass die String-Turingmaschine ein Zeichen a liest, die Cursor-Aktion R ausführt und einen Zustandsübergang von s nach t vollführt. Der entsprechende Stackautomat simuliert dies in folgender Weise. Er prüft, ob das Zeichen a als oberstes Zeichen auf dem Stack liegt, ohne es dort zu entfernen. Anschließend liest er das Zeichen b, auf das der Cursor nach der Cursor-Aktion R zeigt, und speichert es auf dem Stack (push). Außerdem vollführt er den Zustandsübergang von s nach t. Hierzu werden mehrere Tupel der Übergangsrelation des Stackautomaten benötigt:

   Für jedes Tupel

   (s, a, R, t) ∈ d

   wird ein Tupel

   (s, ε, a, a, s') ∈ d'

   erzeugt, wobei s' ein neuer Zustand in der Zustandsmenge Z' des Stackautomaten ist. D.h. der Stackautomat prüft hierdurch, ob das gelesene Zeichen a auf dem Stack vorhanden ist und vollführt einen Zustandsübergang von s zunächst in einen Zwischenzustand s'.

   Weiterhin werden für alle Tupel (t, b, b', t') ∈ d Tupel

   (s', b, ε, b, t) ∈ d'

   erzeugt, die das Zeichen b lesen und auf dem Stack speichern sowie den Zustandsübergang von s nach t abschließen.

    

2. Ein Tupel der Form (s, a, D, t) der Übergangsrelation d der Stackautomat bedeutet, dass das Zeichen a an der Cursorposition gelöscht wird; anschließend zeigt der Cursor auf das vorhergehende Zeichen. Das entsprechende Tupel des Stackautomaten ist ein Entfernen des obersten Stackzeichens, sofern dieses das Zeichen a ist (pop).

   Für jedes Tupel

   (s, a, D, t) ∈ d

   wird ein Tupel

   (s, ε, a, ε, t) ∈ d'

   erzeugt.

    

3. Ein Tupel der Form (s, a, a', t) der Übergangsrelation d der String-Turingmaschine bedeutet, dass das Zeichen a an der Cursorposition durch das Zeichen a' überschrieben wird. Das entsprechende Tupel des Stackautomaten ist ein Überschreiben des obersten Stackzeichens (pop gefolgt von push).

   Für jedes Tupel

   (s, a, a', t) ∈ d

   wird ein Tupel

   (s, ε, a, a', t) ∈ d'

   erzeugt.

    

4. Schließlich wird noch ein Tupel

   (q', $, ε, $, q) ∈ d'

   erzeugt. Hierdurch wird die Anfangsmarkierung $ gelesen und als unterstes Zeichen auf dem Stack gespeichert. Der Zustand q' ist der neue Startzustand des Stackautomaten; der Zustand q ist der ursprüngliche Startzustand der String-Turingmaschine.

Die Zustandsmenge Z' des Stackautomaten besteht also aus allen Zuständen von Z, der Zustandsmenge der String-Turingmaschine, sowie dem neuen Anfangszustand q' sowie weiteren neuen Zuständen s', die in der Konstruktion in Schritt 1 eingeführt werden. Damit ist die Konstruktion abgeschlossen.

 

Gleichheit der erkannten Sprachen

Es bleibt zu zeigen, dass jedes Wort x, das von einer String-Turingmaschine M erkannt wird, auch von dem aus M konstruierten Stackautomaten N erkannt wird, und dass jedes Wort, das von N erkannt wird, auch von M erkannt wird.

1. Sei also x ein Wort, das von der String-Turingmaschine M erkannt wird. Dann gibt es eine Folge von Zustandsübergängen der Übergangsrelation d, durch die das Wort $x& auf das leere Wort reduziert wird. Zu diesen Zustandsübergängen gibt es entsprechende, durch die Konstruktion erzeugte Zustandsübergänge der Übergangsrelation d' des Stackautomaten N. Diese bilden eine Folge von Zustandsübergängen, durch die der Stackautomat das Wort $x& per leerem Stack erkennt.
2. Sei nun x ein Wort, das vom Stackautomaten N erkannt wird. Dann gibt es eine Folge von Zustandsübergängen der Übergangsrelation d' des Stackautomaten, durch die der Stackautomat das Wort x per leerem Stack erkennt. Zu diesen Zustandsübergängen gibt es entsprechende Zustandsübergänge der Übergangsrelation d der String-Turingmaschine. Gegebenenfalls wird aus zwei Zustandsübergängen, die über einen der neu eingeführten Zwischenzustände s' laufen, nur ein entsprechender Zustandsübergang der String-Turingmaschine. Durch die Folge dieser Zustandsübergänge reduziert die String-Turingmaschine das Wort x auf das leere Wort und erkennt es somit.

Genaugenommen erkennt der konstruierte Stackautomat nicht die Sprache L, die von der String-Turingmaschine erkannt wird, sondern die Sprache $L&, denn die Begrenzungszeichen werden vom Stackautomaten mitverarbeitet. Wenn aber $L& kontextfrei ist, so ist auch L kontextfrei (aus der kontextfreien Grammatik für $L& werden einfach die Zeichen $ und & gestrichen; die resultierende Grammatik ist immer noch kontextfrei).

Beispiel:  Die folgende Typ-2-String-Turingmaschine erkennt die Sprache der korrekten Klammerstrukturen, wobei a einer öffnenden und b einer schließenden Klammer entspricht.

 

Mithilfe des Konstruktionsverfahrens ergibt sich hieraus folgender Stackautomat.

Die erste Zeile der Übergangsrelation des Stackautomaten speichert die Anfangsmarkierung $ auf dem Stack. Die folgenden Zustandsübergänge, die über die Zwischenzustände 4 bzw. 5 führen, entsprechen den beiden Tupeln mit der Cursor-Aktion R der String-Turingmaschine. Die restlichen Tupel entsprechen den Tupeln mit der Cursor-Aktion D.