Theoretische Informatik

Chomsky-Hierarchie der String-Turingmaschinen

 aufwärts

Eine String-Turing­maschine arbeitet ähnlich wie die klassische Turing­maschine. Statt des Arbeits­bandes verwendet sie jedoch einen Arbeits­string, in dem sie auch Zeichen einfügen und löschen kann. Links- und Rechts­bewegungen sowie Einfüge- und Lösch-Aktionen der String-Turing­maschine werden als Cursor-Aktionen bezeichnet.

Wir verwenden String-Turing­maschinen zur Erkennung von Sprachen. Indem die zulässigen Cursor-Aktionen der String-Turing­maschine geeignet einge­schränkt werden, lassen sich genau die Sprach­klassen der Chomsky-Hierarchie erkennen. Es ergibt sich so eine Chomsky-Hierarchie der String-Turing­maschinen (Bild 1).

 

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

Typ-i-String-Turingmaschinen

Die Cursor-Aktionen, die der String-Turing­maschine grund­sätzlich zur Verfügung stehen, sind Einfügen (I – insert), Rechts­bewegung (R), Links­bewegung (L) und Löschen (D – delete). Im Folgenden werden String-Turing­maschinen angegeben, deren Cursor-Aktionen nach und nach einge­schränkt werden; diese werden als Typ-i-String-Turing­maschinen bezeichnet, und es wird der Zusammenhang mit den Typ-i-Sprachen und den klassischen Automaten­typen Turing­maschine, Stackautomat und endlicher Automat hergestellt.

Typ-0-String-Turing­maschine

Die Typ-0-Sprachen werden genau von den klassischen Turing­maschinen erkannt. Eine String-Turing­maschine ohne Ein­schränkungen der Menge der möglichen Cursor-Aktionen { I, R, L, D } ist äquivalent zur klassischen Turing­maschine. Wie diese erkennt sie genau die Typ-0-Sprachen und wird daher als Typ-0-String-Turing­maschine bezeichnet.

Definition:  Eine String-Turing­maschine ist vom Typ 0, wenn für die Übergangs­relation d gilt

d  enthalten in  Z  ×  A  ×  A0  ×  Z         mit   A0  =  A vereinigt { I, R, L, D }

Die Äquivalenz von klassischer Standard-Turing­maschine und String-Turing­maschine lässt sich dadurch zeigen, dass sich Maschinen der einen Art durch Maschinen der anderen Art simulieren lassen und umgekehrt.

Die String-Turing­maschine kann eine Standard-Turing­maschine simulieren. Hierzu führt sie alle Aktionen der Standard-Turing­maschine genauso aus, nur wenn sie nach einer Rechts­bewegung auf die Ende­markierung & trifft, geht sie um ein Feld nach links und führt eine Einfüge-Aktion aus. Dadurch kann die String-Turing­maschine das Arbeitsband nach rechts so weit ausdehnen, wie es erforderlich ist.

Umgekehrt kann eine Standard-Turing­maschine die String-Turing­maschine simulieren. Eine Einfüge-Aktion führt sie dadurch aus, dass sie alle Zeichen, die auf dem Arbeitsband rechts von der Einfüge­position stehen, um ein Feld nach rechts verschiebt. Eine Lösch-Aktion führt sie dadurch aus, dass sie alle Zeichen, die auf dem Arbeitsband rechts von der Lösch­position stehen, um ein Feld nach links verschiebt und danach ein Feld nach links geht.

Typ-1-String-Turing­maschine

Die Typ-1-Sprachen oder kontext­sensitiven Sprachen werden genau von den nicht­deterministischen linear beschränkten Turing­maschinen erkannt. Eine Turing­maschine ist linear beschränkt, wenn sie den Bereich des Arbeits­bandes, auf dem das Eingabewort steht, nicht verlässt. Für eine String-Turing­maschine ergibt sich diese Beschränkung, wenn die Übergangs­relation d keine Einfüge-Aktion zulässt.

Definition:  Eine String-Turing­maschine ist vom Typ 1, wenn für die Übergangs­relation d gilt

d  enthalten in  Z  ×  A  ×  A1  ×  Z         mit   A1  =  A vereinigt { R, L, D }

 

Typ-2-String-Turing­maschine

Die Typ-2-Sprachen oder kontext­freien Sprachen werden genau von den nicht­deterministischen Stack­automaten erkannt. Eine String-Turing­maschine, deren Übergangs­relation d keine Einfüge-Aktionen und keine Links­bewegungen zulässt, sondern nur Rechts­bewegungen und Lösch-Aktionen, verhält sich ähnlich wie ein Stackautomat. Der Stack wird durch linken Teil des Arbeits­strings bis zur Cursor-Position dargestellt. Ein Zugriff auf diesen Teil ist nur durch eine Lösch-Aktion, also durch Lesen und anschließendes Löschen des Zeichens an der Cursor-Position möglich; dies entspricht der pop-Operation beim Stack. Eine push-Operation ergibt sich dadurch, dass ein Zeichen des Arbeits­strings gelesen und durch ein Stack-Zeichen über­schrieben wird.

Definition:  Eine String-Turing­maschine ist vom Typ 2, wenn für die Übergangs­relation d gilt

d  enthalten in  Z  ×  A  ×  A2  ×  Z         mit   A2  =  A vereinigt { R, D }

Der Beweis, dass die nicht­deterministischen Typ-2-String-Turing­maschinen genau die Typ-2-Sprachen erkennen, findet sich unter Typ-2-String-Turing­maschine.

 

Typ-3-String-Turing­maschine

Die Typ-3-Sprachen oder regulären Sprachen werden von den endlichen Automaten erkannt. Ein endlicher Automat lässt sich durch eine String-Turing­maschine nachbilden, deren Übergangs­relation d keine Einfüge-Aktionen, keine Links- und keine Rechts­bewegungen, sondern nur Lösch-Aktionen zulässt.

Definition:  Eine String-Turing­maschine ist vom Typ 3, wenn für die Übergangs­relation d gilt

d  enthalten in  Z  ×  A  ×  A3  ×  Z         mit   A3  =   { D }

Da der Cursor nach einer Lösch-Aktion auf das vorher­gehende Zeichen zeigt, wird das Eingabewort in diesem Fall von rechts nach links abgearbeitet. Zu Beginn zeigt der Cursor auf das rechte Begrenzungs­zeichen &. Die Typ-3-String-Turing­maschine erkennt somit das Spiegelbild derjenigen regulären Sprache, die ein endlicher Automat bei Abarbeitung von links nach rechts erkennt. Das Spiegelbild einer regulären Sprache ist aber regulär.

Simulationen

Mit folgenden Simulationen lässt sich die Arbeitsweise bestimmter String-Turing­maschinen ver­anschaulichen.

Die folgende String-Turing­maschine erkennt die Sprache L = { anbncn  |  n Element natürliche Zahlen }. Die Maschine löscht das erste a, geht über weitere a's weiter nach rechts, löscht das erste b, geht über weitere b's weiter nach rechts, löscht das erste c, und geht über weitere c's bis zum rechten Begrenzungs­zeichen &. Danach geht sie wieder an den Anfang und beginnt von vorne.

Arbeitsstring

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

saa's'
 0 $R1
 1 aD2
 2 $R3
 3 aR3
 3 bD4
 4 $R5
 4 aR5
 5 bR5
 5 cD6
 6 bR7
 7 cR7
 7 &L8
 6 $R9
 8 cL8
 8 bL8
 8 aL8
 8 $R1
 9 &D5
 5 $D5

 

Die folgende String-Turing­maschine erkennt die Sprache L  =  a | a(a|b)*a. Da es sich um eine Typ-3-String-Turing­maschine handelt, zeigt der Cursor zu Beginn auf das rechte Begrenzungs­zeichen &.

Arbeitsstring

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

saa's'
 0 &D1
 1 aD2
 2 $D3
 2 aD2
 2 bD4
 4 aD2
 4 bD4

Aufgaben

Aufgabe 1:  Entwerfen Sie eine nicht­deterministische Typ-2-String-Turing­maschine zur Erkennung der Sprache L = { wwR  |  w Element {a, b}+wR ist das Spiegelbild von w }.

Arbeitsstring

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

saa's'
 0 $R0
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      

       

Aufgabe 2:  Entwerfen Sie eine deterministische Typ-1-String-Turing­maschine zur Erkennung der Sprache L = { a2n  |  n Element natürliche Zahlen0 } über dem Alphabet A = {a}.

Arbeitsstring

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

saa's'
 0 $R0
      
      
      
      
      
      
      
      
      
      
      
      
      

       

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:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 05.09.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