Theoretische Informatik

Typ-2-String-Turingmaschine

 aufwärts

Der Chomsky-Hierarchie der Sprachen entsprechend gibt es eine Chomsky-Hierarchie der String-Turing­maschinen. Wir betrachten String-Turing­maschinen vom Typ 2, d.h. String-Turing­maschinen, die lediglich die Cursor-Aktionen R (Rechts­bewegung) und D (Löschen – delete) benutzen.

Satz:  Die nicht­deterministischen String-Turing­maschinen vom Typ 2 erkennen genau die kontext­freien Sprachen.

Wir beweisen diesen Satz in zwei Abschnitten, indem wir die beiden Richtungen dieses Satzes jeweils für sich zeigen. Zunächst zeigen wir, dass jede kontextfreie Sprache, also Typ-2-Sprache, von einer Typ-2-String-Turing­maschine erkannt wird, und danach, dass jede Sprache, die von einer Typ-2-String-Turing­maschine erkannt wird, kontextfrei ist.

Typ-2-Sprachen werden von Typ-2-String-Turingmaschinen erkannt

Satz:  Sei L eine kontextfreie Sprache. Dann gibt es eine nicht­deterministische String-Turing­maschine 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 Sgeht über nachε erlaubt, wenn das leere Wort ε in der Sprache L vorkommt. Wir konstruieren aus G eine Typ-2-String-Turing­maschine, 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 Begrenzungs­zeichen $ und & löscht.

Konstruktion

Das Eingabe­alphabet E der String-Turing­maschine ist gleich der Menge der Terminal­zeichen T der Grammatik. Das Arbeits­alphabet A der String-Turing­maschine besteht aus aus allen Zeichen der Grammatik, also Variablen und Terminal­zeichen, sowie den Begrenzungs­zeichen $ und &; diese dürfen nicht in der Grammatik vorkommen. Die Zustands­menge Z der String-Turing­maschine 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 Pfeil nach rechts u0 ... uk-1 der Grammatik G werden folgende Tupel in die Übergangs­relation der String-Turing­maschine aufgenommen:
    saa's'
    0uk-1Dsk-1
    sk-1uk-2Dsk-2
     drei Punkte übereinander 
    s1u0X0

    Hierbei sind s1, ..., sk-1 neue Zustände, die speziell für diese Produktion zur Zustands­menge hinzu­genommen werden.

    Mithilfe dieser Zustands­übergänge reduziert die String-Turing­maschine die rechte Seite u0 ... uk-1 der Produktion auf die linke Seite X.

  2. Für jedes Zeichen a der Grammatik, sowohl für Variablen als auch für Terminal­zeichen, sowie für a = $ wird ein Tupel
    saa's'
    0aR0

    in die Übergangs­relation der String-Turing­maschine aufgenommen. Hierdurch ist es der String-Turing­maschine möglich, sich in ihrem Arbeits­string nach rechts zu bewegen.

  3. Schließlich werden noch die Tupel
    0&D1
    1SD2
    2$D3

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

  4. Wenn die Produktion Sgeht über nachε in G enthalten ist, wird zusätzlich noch das Tupel
    saa's'
    1$D3

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

 

Arbeitsweise der String-Turing­maschine

Die String-Turing­maschine startet im Zustand 0 und geht in ihrem Arbeits­string 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 nicht­deterministisch, 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 Eingabe­wortes 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-Turing­maschine in der Lage, diese Reduktion nachzubilden und x zu erkennen.

Wenn umgekehrt ein Wort x von der String-Turing­maschine erkannt wird, so entsprechen Folgen von Zustands­übergängen, die aus Schritt 1 der Konstruktion stammen, jeweils Reduktions­schritten 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 Reduktions­folge der Grammatik. Somit gehört x zu L(G).

Beispiel:  Das Konstruktionsverfahren wird auf die folgende Grammatik angewendet:

Sgeht über nachAb
Sgeht über nachASb
Ageht über nacha

Die Grammatik erzeugt die Sprache L = { anbn  |  n Element natürliche Zahlen }. Durch Anwendung des Konstruktionsverfahrens ergibt sich aus dieser Grammatik die folgende Übergangs­relation einer Typ-2-String-Turing­maschine:

Arbeitsstring

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

saa's'
 0 bD5
 5 AS0
 0 bD6
 6 SD7
 7 AS0
 0 aA0
 0 bR0
 0 AR0
 0 SR0
 0 aR0
 0 $R0
 0 &D1
 1 SD2
 2 $D3

Die ersten Tupel der Übergangs­relation entsprechen den Anwendungen der Produktionen aus Schritt 1 der Konstruktion; beispiels­weise entsprechen die ersten beiden Tupel der Anwendung der Produktion Sgeht über nachAb, indem im Arbeits­string b gelöscht wird und A durch S über­schrieben wird. Es folgen die Tupel mit der Cursor-Aktion R aus Schritt 2 der Konstruktion und zum Schluss die Tupel aus Schritt 3.

Sprachen, die von Typ-2-String-Turingmaschinen erkannt werden, sind kontextfrei

Satz:  Sei M eine nicht­deterministische String-Turing­maschine 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 nicht­deterministischen Typ-2-String-Turing­maschine M einen nicht­deterministischen Stack­automaten N in der Weise, dass L(N) = L(M) gilt. Von der Sprache L(N) wissen wir, dass sie kontextfrei ist, denn die nicht­deterministischen Stack­automaten erkennen genau die kontext­freien Sprachen.

Konstruktion

Die Zustands­menge Z' des Stack­automaten ist zunächst gleich Z, der Zustands­menge der String-Turing­maschine; im Verlauf der Konstruktion kommen aber noch weitere Zustände hinzu. Eingabe- und Stack­alphabet des Stack­automaten sind gleich dem Arbeits­alphabet der String-Turing­maschine. Die Tupel der Übergangs­relation d der String-Turing­maschine werden wie folgt in ent­sprechende Tupel der Übergangs­relation d' des Stack­automaten umgeformt.

  1. Ein Tupel der Form (s, a, R, t) der Übergangs­relation d der String-Turing­maschine bedeutet, dass die String-Turing­maschine ein Zeichen a liest, die Cursor-Aktion R ausführt und einen Zustands­übergang von s nach t vollführt. Der ent­sprechende 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 Übergangs­relation des Stack­automaten benötigt:

    Für jedes Tupel

    (s, a, R, tElement d

    wird ein Tupel

    (s, ε, a, a, s'Element d'

    erzeugt, wobei s' ein neuer Zustand in der Zustands­menge Z' des Stack­automaten 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 Zwischen­zustand s'.

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

    (s', b, ε, b, tElement 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 Übergangs­relation d der Stackautomat bedeutet, dass das Zeichen a an der Cursor­position gelöscht wird; anschließend zeigt der Cursor auf das vorher­gehende Zeichen. Das ent­sprechende Tupel des Stack­automaten ist ein Entfernen des obersten Stack­zeichens, sofern dieses das Zeichen a ist (pop).

    Für jedes Tupel

    (s, a, D, tElement d

    wird ein Tupel

    (s, ε, a, ε, tElement d'

    erzeugt.

     

  3. Ein Tupel der Form (s, a, a', t) der Übergangs­relation d der String-Turing­maschine bedeutet, dass das Zeichen a an der Cursor­position durch das Zeichen a' über­schrieben wird. Das ent­sprechende Tupel des Stack­automaten ist ein Über­schreiben des obersten Stack­zeichens (pop gefolgt von push).

    Für jedes Tupel

    (s, a, a', tElement d

    wird ein Tupel

    (s, ε, a, a', tElement d'

    erzeugt.

     

  4. Schließlich wird noch ein Tupel

    (q', $, ε, $, qElement d'

    erzeugt. Hierdurch wird die Anfangs­markierung $ gelesen und als unterstes Zeichen auf dem Stack gespeichert. Der Zustand q' ist der neue Startzustand des Stack­automaten; der Zustand q ist der ursprüng­liche Startzustand der String-Turing­maschine.

Die Zustands­menge Z' des Stack­automaten besteht also aus allen Zuständen von Z, der Zustands­menge der String-Turing­maschine, sowie dem neuen Anfangs­zustand q' sowie weiteren neuen Zuständen s', die in der Konstruktion in Schritt 1 eingeführt werden. Damit ist die Konstruktion abge­schlossen.

 

Gleichheit der erkannten Sprachen

Es bleibt zu zeigen, dass jedes Wort x, das von einer String-Turing­maschine M erkannt wird, auch von dem aus M konstruierten Stack­automaten 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-Turing­maschine M erkannt wird. Dann gibt es eine Folge von Zustands­übergängen der Übergangs­relation d, durch die das Wort $x& auf das leere Wort reduziert wird. Zu diesen Zustands­übergängen gibt es ent­sprechende, durch die Konstruktion erzeugte Zustands­übergänge der Übergangs­relation d' des Stack­automaten 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 Stack­automaten N erkannt wird. Dann gibt es eine Folge von Zustands­übergängen der Übergangs­relation d' des Stack­automaten, durch die der Stackautomat das Wort x per leerem Stack erkennt. Zu diesen Zustands­übergängen gibt es ent­sprechende Zustands­übergänge der Übergangs­relation d der String-Turing­maschine. Gegebenen­falls wird aus zwei Zustands­übergängen, die über einen der neu eingeführten Zwischen­zustände s' laufen, nur ein ent­sprechender Zustands­übergang der String-Turing­maschine. Durch die Folge dieser Zustands­übergänge reduziert die String-Turing­maschine das Wort x auf das leere Wort und erkennt es somit.

Genau­genommen erkennt der konstruierte Stackautomat nicht die Sprache L, die von der String-Turing­maschine erkannt wird, sondern die Sprache $L&, denn die Begrenzungs­zeichen werden vom Stack­automaten mit­verarbeitet. Wenn aber $L& kontextfrei ist, so ist auch L kontextfrei (aus der kontext­freien Grammatik für $L& werden einfach die Zeichen $ und & gestrichen; die resultierende Grammatik ist immer noch kontextfrei).

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

Arbeitsstring

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

saa's'
 0 $R0
 0 aR0
 0 bD1
 0 &D2
 1 aD0
 2 $D3


 

Mithilfe des Konstruktionsverfahrens ergibt sich hieraus folgender Stackautomat.

Eingabeband

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil
 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil
Stack

Eingabewort

   

 

sehh's'
 -1 $ε$0
 0 ε$$4
 4 $ε$0
 4 aεa0
 4 bεb0
 4 &ε&0
 0 εaa5
 5 $ε$0
 5 aεa0
 5 bεb0
 5 &ε&0
 0 εbε1
 0 ε&ε2
 1 εaε0
 2 ε$ε3

Die erste Zeile der Übergangs­relation des Stack­automaten speichert die Anfangs­markierung $ auf dem Stack. Die folgenden Zustands­übergänge, die über die Zwischen­zustände 4 bzw. 5 führen, entsprechen den beiden Tupeln mit der Cursor-Aktion R der String-Turing­maschine. Die restlichen Tupel entsprechen den Tupeln mit der Cursor-Aktion D.

Zusammenfassung

Wir haben gezeigt, dass jede kontextfreie Sprache von einer nicht­deterministischen Typ-2-String-Turing­maschine erkannt wird und umgekehrt, dass jede Sprache, die von einer nicht­deterministischen Typ-2-String-Turing­maschine erkannt wird, kontextfrei ist. Damit ist gezeigt, dass die nicht­deterministischen Typ-2-String-Turing­maschinen genau die kontext­freien Sprachen erkennen.

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 25.08.2011   Updated: 10.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik