Theoretische Informatik

String-Turingmaschine

 aufwärts

Wir betrachten im Folgenden ein sehr einfaches abstraktes Modell einer Maschine zur Manipulation von Zeichen­ketten (Strings). Diese Maschine ist eine Variante der Turing­maschine, sie wird daher als String-Turing­maschine bezeichnet [Lan 10].

Idee

Das Maschinen­modell der String-Turing­maschine ist in Bild 1 dargestellt. Die Maschine hat ein Steuerwerk, in dem sich das Programm befindet. Sie kann auf die einzelnen Zeichen einer Zeichenkette, des Arbeits­strings, zugreifen; dabei kann sie das jeweilige Zeichen lesen und durch ein anderes Zeichen über­schreiben. Die Position des Zugriffs auf den Arbeits­string wird als die Cursor-Position bezeichnet.

Ferner kann die Maschine die Cursor-Position jeweils um eine Position nach links oder rechts bewegen, an der Cursor-Position ein Leerzeichen einfügen oder das Zeichen an der Cursor-Position löschen. Diese Aktionen werden als Cursor-Aktionen bezeichnet. Es gibt somit die Cursor-Aktionen Links (L), Rechts (R), Einfügen (I – insert) und Löschen (D – delete).

Zu Beginn der Verarbeitung besteht der Arbeits­string aus dem Eingabewort x zuzüglich einer Anfangs­markierung $ und einer Ende­markierung &.

String-Turingmaschine mit Eingabewort
Bild 1: String-Turingmaschine mit Eingabewort x = x0 ... x5

Das Interessante an diesem Konzept besteht darin, dass String-Turing­maschinen, deren zulässige Cursor-Aktionen geeignet einge­schränkt werden, genau die Sprach­klassen der Chomsky-Hierarchie erkennen (Bild 2). Beispiels­weise erkennen String-Turing­maschinen, die lediglich die Cursor-Aktionen R und D verwenden, genau die Typ-2-Sprachen oder kontext­freien Sprachen.

 

SprachklasseCursor-Aktionen
  Typ 0I, L, R, D  
  Typ 1L, R, D  
  Typ 2R, D  
  Typ 3D  
Bild 2: Zulässige Cursor-Aktionen von String-Turingmaschinen

Einfüge- und Löschaktion

Die Einfüge-Aktion I bewirkt, dass an der Cursor-Position das Leerzeichen Leerzeichen in den Arbeits­string eingefügt wird. Das zuvor dort befindliche Zeichen und alle Zeichen links davon rücken um eine Position nach links (Bild 3a). Die Lösch-Aktion D bewirkt, dass alle Zeichen links von der Cursor-Position um eine Position nach rechts rücken. Das zuvor an der Cursor-Position befindliche Zeichen wird dabei über­schrieben (Bild 3b).

Einfügen eines Leerzeichens Löschen eines Zeichens
(a) (b)
Bild 3: (a) Einfügen und (b) Löschen eines Zeichens

Formale Definition

Formal lässt sich die String-Turing­maschine wie folgt darstellen:

Definition:  Eine nicht­deterministische String-Turing­maschine ist ein 6-Tupel

M  =  (Z, E, A, d, q, p).

Hierbei ist

Z eine endliche, nichtleere Menge von Zuständen des Steuerwerks,
E das Eingabe­alphabet,
A das Arbeits­alphabet,  wobei E enthalten in A,
d die Übergangs­relation   d enthalten in Z × A × A' × Z,  hierbei ist A' = A vereinigt {L, R, I, D},
q Element Z    der Startzustand,
p Element {$, &}    das Zeichen an der Anfangs­position des Cursors

Im Arbeits­alphabet A sind die Begrenzungs­zeichen $ und & sowie das Leerzeichen Leerzeichen enthalten; diese kommen nicht im Eingabe­alphabet vor. Die Zeichen L, R, I, D für die Cursor-Aktionen kommen nicht als Alphabet­zeichen vor.

Arbeitsweise

Zu Beginn besteht der Arbeits­string aus dem Eingabewort, ein­geschlossen von den Begrenzungs­zeichen $ und &. Je nach dem, ob das Eingabewort von links nach rechts oder von rechts nach links abgearbeitet werden soll, steht der Cursor zu Beginn auf der Anfangs­markierung $ oder der Ende­markierung &.

Die Elemente der Übergangs­relation d sind 4-Tupel der Form (s, a, a', s'). Diese stellen mögliche Zustands­übergänge der String-Turing­maschine dar, mit folgender Bedeutung: Wenn die String-Turing­maschine im Zustand s ist und das Zeichen a an der Cursor-Position liest, so kann sie das Zeichen a mit dem Zeichen a' über­schreiben und in den Folgezustand s' übergehen. Wenn jedoch das Zeichen a' eines der Symbole L, R, I oder D ist, dann schreibt die String-Turing­maschine nicht, sondern bewegt den Cursor nach links (L) oder nach rechts (R) oder fügt ein Leerzeichen an der Cursor-Position ein (I) oder löscht das Zeichen an der Cursor-Position (D).

Es kann mehrere mögliche Zustands­übergänge in einem Zustand s mit gelesenem Zeichen a geben; in diesem Fall verhält sich die String-Turing­maschine nicht­deterministisch.

Erkennung von Sprachen

Definition:  Sei M eine String-Turing­maschine mit Eingabe­alphabet E.

Die String-Turing­maschine M erkennt ein Eingabewort x Element E, wenn es eine Folge von Zustands­übergängen gibt, durch die das Wort x einschließ­lich der beiden Begrenzungs­zeichen vollständig gelöscht wird.

Die von M erkannte Sprache L(M) ist die Menge aller Wörter x Element E, die von M erkannt werden:

L(M)   =   { x Element E  |  M erkennt x }

Beispiel:  Sei L die Sprache aller korrekten Klammer­strukturen, wobei a für eine öffnende und b für eine schließende Klammer steht. Beispiels­weise gehört das Wort aabbab zu L, jedoch abbaab nicht.

Die folgende String-Turing­maschine M = (Z, E, A, d, q, p) erkennt die Sprache L. Zustands­menge ist Z = {0, 1, 2, 3}, Eingabe­alphabet E = {a, b}, Arbeits­alphabet A = {a, b, $, & Leerzeichen}; der Anfangs­zustand ist q = 0, zu Anfang zeigt der Cursor auf das Zeichen p = $, und die Übergangs­relation d ist wie folgt definiert:

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

 

Bild 4 zeigt als Beispiel die Start­situation der String-Turing­maschine mit dem Eingabewort aabb. Die String-Turing­maschine startet im Zustand 0 und bewegt den Cursor solange nach rechts, bis sie auf das erste b trifft. Sie löscht dieses und geht in den Zustand 1 über. Im Zustand 1 erwartet die String-Turing­maschine ein zugehöriges a; sie löscht dieses ebenfalls und geht wieder in den Zustand 0. Damit hat sie ein inneres Klammerpaar gelöscht und beginnt von vorne. Stößt die String-Turing­maschine im Zustand 0 irgendwann auf die Ende­markierung &, so löscht sie diese und geht in den Zustand 2 über. Im Zustand 2 erwartet sie die Anfangs­markierung $. Sie löscht diese ebenfalls und geht in den Zustand 3 über.

Bild 4: Startsituation mit Eingabewort aabb
Bild 4: Startsituation mit Eingabewort aabb

Wenn das Eingabewort x in der Sprache L enthalten ist, so gelingt es der String-Turing­maschine M, durch eine Folge der beschriebenen Zustands­übergänge das Wort x einschließ­lich der Begrenzungs­zeichen $ und & zu löschen. Wenn dagegen das Eingabewort x nicht in der Sprache L enthalten ist, so gelingt es der String-Turing­maschine nicht, das Wort x einschließ­lich der Begrenzungs­zeichen $ und & zu löschen. Sie gerät dann irgendwann in einen Zustand, von dem aus mit dem Zeichen an der Cursor-Position kein Zustands­übergang möglich ist, dabei aber das Wort noch nicht vollständig gelöscht ist.

Besteht beispiels­weise das Eingabewort nur aus einem a, so bewegt die String-Turing­maschine den Cursor solange nach rechts, bis sie auf die Ende­markierung & trifft. Sie löscht diese und geht in den Zustand 2 über. Im Zustand 2 trifft sie nun aber auf das a. Sie kann keinen Zustands­übergang mehr ausführen, hat aber das Eingabewort nicht gelöscht. Somit erkennt sie das Wort a nicht.

Diese String-Turing­maschine kann hier simuliert werden:

Arbeitsstring

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

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


 

Die String-Turing­maschine aus diesem Beispiel verwendet nur zwei der vier möglichen Cursor-Aktionen L, R, I, D, nämlich R und D. Dies ist kein Zufall, denn die Sprache L der korrekten Klammer­strukturen aus dem Beispiel ist eine kontextfreie Sprache, und jede kontextfreie Sprache lässt sich, wie wir noch sehen werden, durch eine String-Turing­maschine erkennen, die nur die Cursor-Aktionen R und D benutzt.

String-Turingmaschine als Reduktionsmaschine

Gegeben sei eine Grammatik G. Dann lässt sich eine String-Turing­maschine konstruieren, die in der Lage ist, Reduktionen auszuführen, d.h. in ihrem Arbeits­string jeweils die rechte Seite einer Produktion der Grammatik durch die zugehörige linke Seite zu ersetzen.

Die String-Turing­maschine erkennt dann ein Wort x Element L(G), indem sie es durch Anwendung der Produktionen von G auf das Startsymbol S reduziert und anschließend den ver­bleibenden String $S& löscht.

Für ein Wort x nicht Element L(G) gibt es in G keine Reduktions­folge auf das Startsymbol; daher gelingt es der String-Turing­maschine nicht, ein solches Eingabewort x vollständig zu löschen, sie erkennt es somit nicht.

Beispiel:  Gegeben sei die Grammatik G mit folgenden Produktionen:

Sgeht über nachaSb  |  ab
abgeht über nachba

Die Grammatik G erzeugt die Sprache aller nichtleeren Wörter über {a, b}, die gleich viele a's wie b's enthalten:

L(G)   =   { w Element {a, b}+  |  |w|a = |w|b }

Eine ent­sprechende String-Turing­maschine M, die L(G) erkennt, ist im Folgenden angegeben. Zunächst hat M Zustands­übergänge, die es ihr ermöglichen, die Cursor-Position in ihrem String nach rechts und nach links zu bewegen:

saa's'
0$R0
0aR0
0bR0
0SR0
0&L0
0aL0
0bL0
0SL0

Die String-Turing­maschine arbeitet nicht­deterministisch; sie hat die Wahl, die Cursor-Position nach links oder nach rechts zu bewegen, wenn sie beispiels­weise im Zustand 0 das Zeichen a liest.

Ferner hat die String-Turing­maschine M Zustands­übergänge, die es ihr ermöglichen, die Produktionen der Grammatik G anzuwenden.

So hat sie beispiels­weise die Möglichkeit, wenn sie das Zeichen a liest, die Produktion abgeht über nachba anzuwenden, indem sie deren rechte Seite ba durch die linke Seite ab ersetzt:

saa's'
0ab1
1bL2
2ba0

Außerdem hat sie die Möglichkeit, wenn sie das Zeichen b liest, die Produktion Sgeht über nachab oder die Produktion Sgeht über nachaSb anzuwenden, indem sie die jeweilige rechte Seite durch die linke Seite S ersetzt:

saa's'
0bD3
3aS0
3SD4
4aS0

Schließlich hat M noch Zustands­übergänge, die es ihr ermöglichen, zum Schluss den String $S& zu löschen:

saa's'
0&D5
5SD6
6$D7

 

Diese vier Tabellen zusammen­genommen bilden die Übergangs­relation der String-Turing­maschine.

Arbeitsstring

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

saa's'
 0 $R0
 0 aR0
 0 bR0
 0 SR0
 0 &L0
 0 aL0
 0 bL0
 0 SL0
 0 ab1
 1 bL2
 2 ba0
 0 bD3
 3 aS0
 3 SD4
 4 aS0
 0 &D5
 5 SD6
 6 $D7

 

Zu betonen ist in diesem Zusammenhang noch einmal die Tatsache, dass die String-Turing­maschine nicht­deterministisch arbeitet. Sie erkennt das Eingabewort nur dann, wenn sie jeweils die richtigen Zustands­übergänge wählt. Dies ist kenn­zeichnend für die nicht­deterministischen Arbeitsweise: Es ist gefordert, dass es eine Folge von Zustands­übergängen gibt, die zum gewünschten Ergebnis führt, nicht jedoch, dass jede Folge von möglichen Zustands­übergängen zum gewünschten Ergebnis führt.

Im übrigen ist auch die Ableitung eines Wortes mithilfe der Produktionen einer Grammatik im allgemeinen ein nicht­deterministischer Vorgang. Sobald nämlich eine Produktion mehrere Alternativen hat, besteht ebenfalls eine Wahl­möglichkeit und es muss die richtige Wahl getroffen werden, um das Wort erfolgreich abzuleiten. In der Grammatik G aus dem obigen Beispiel lässt sich z.B. das Wort aabb nur dann aus dem Startsymbol S ableiten, wenn als erster Ableitungs­schritt Sgeht über nachaSb gewählt wird (und nicht der ebenfalls mögliche Ableitungs­schritt Sgeht über nachab).

Zusammenfassung

Mithilfe der Produktionen einer Grammatik G = (V, T, P, S) lassen sich Wörter ableiten. Die Menge der Wörter über T, die sich mithilfe der Produktionen von G aus dem Startsymbol S ableiten lassen, ist die von G erzeugte Sprache L(G). Umgekehrt lassen sich alle Wörter aus L(G) durch umgekehrtes Durchlaufen ihrer Ableitungs­folge auf das Startsymbol S reduzieren. Ein Wort über T, das nicht zu L(G) gehört, lässt sich dagegen nicht auf S reduzieren (denn sonst ließe es sich auch aus S ableiten).

Das Konzept der String-Turing­maschine ist dazu geeignet, die Reduktion von Wörtern auf das Startsymbol maschinell nachzubilden. Das Interessante an diesem Konzept wird auf den folgenden Seiten deutlich. Wenn die Menge {L, R, I, D} der Cursor-Aktionen geeignet einge­schränkt wird, ergeben sich nämlich Typ-i-String-Turing­maschinen, die genau die Sprachen der ent­sprechenden Sprachklasse der Chomsky-Hierarchie erkennen. Werden beispiels­weise die Cursor-Aktionen auf {R, D} einge­schränkt, ergeben sich Typ-2-String-Turing­maschinen, die genau die kontext­freien Sprachen erkennen.

Literatur

[Lan 10]H.W. Lang: A Characterization of the Chomsky Hierarchy by String Turing Machines. In: H.R. Arabnia, G.A. Gravvanis, A.M.G. Solo (Hrsg.): Proceedings of the 2010 International Conference on Foundations of Computer Science, CSREA Press, 109-114 (2010)

 

Weiter mit:   [Chomsky-Hierarchie der String-Turingmaschinen]   oder   up

 

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


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