Informatikmaterialien 
von Tino Hempel

Startseite | Informatik | Physik | Mathematik | Sonstiges |


Richard-Wossidlo-Gymnasium Ribnitz-Damgarten
Fachbereich Informatik


Turing-Maschine


Grenzen von Kellerautomaten

Der Kellerspeicher hat den entscheidenden Nachteil, dass beim Auskellern die gespeicherten Informationen verloren gehen. Somit ist ein Kellerautomat nicht in der Lage, die Sprache L = {anbncn | n > 0} zu erkennen, da nach dem Auskellern keine Informationen über die Anzahl der Zeichen mehr vorhanden ist.  

Turing-Maschine

Alan Turing (1912–1954) entwickelte ein abstrakte Maschine, die den Nachteil des Kellerautomaten nicht besitzt und sich beliebige Eingaben merken kann. 

1. Aufbau der TM

Die TM besitzt 

2. Arbeitsweise:

  1. Einlesen des Eingabezeichens

  2. Schreiboperation auf das Band, Bewegung des Lese-Schreibkopfes (links/rechts/keine) und Zustandsübergang in Abhängigkeit vom aktuellen Zustand und dem Eingabezeichen

  3. ggf. Wiederholung der Schritte 1 und 2

TM können sowohl deterministisch wie auch nichtdeterministisch arbeiten.

Die TM akzeptiert eine Eingabe, wenn sie im Endzustand stoppt. Es ist aber auch möglich, dass die TM nicht stoppt. In diesem Fall kann nicht gesagt werden, ob das Wort zur Sprache gehört oder nicht (1. Leistungsgrenze von Computern)

3. Definition

Eine TM M = (X, Z, Γ, δ, z0, $, E) wird durch folgende Angaben definiert:

  • X – Eingabealphabet

  • Z – endliche Zustandsmenge

  • Γ – Bandalphabet

  • δ – partielle Überführungsfunktion

  • z0 – Anfangszustand

  • $ – Bandvorbelegungszeichen

  • ZE – Menge der Endzustände.

Einfache Beispiele

Man entwickle eine TM M, die feststellt, ob ein Wort w {0, 1}* mit "1" beginnt. Dabei soll der Kopf der TM auf dem ersten Zeichen des Wortes stehen. Beim Prüfen wird das Wort nicht gelöscht.

Lösung:

M = (X, Z, Γ, δ, q0, $, ZE) mit
X = Γ = {0, 1, $}
Z = {q0, q1}
ZE = {q1}
δ: 

TM beginnend 1

Man entwickle eine TM M, die feststellt, ob ein Wort w {0, 1}* mit "1" beginnt und sich anschließend die "0" und "1" abwechseln. Dabei soll der Kopf der TM auf dem ersten Zeichen des Wortes stehen. Beim Prüfen wird das Wort nicht gelöscht.

Lösung:

M = (X, Z, Γ, δ, z0, *, E) mit
X = Γ = {0, 1, *}
Z = {a, 2, 3, e, f}
E = {e}
δ: 

TM



zur Startseite
© Tino Hempel 1997 - 2009
Im Web vertreten seit 1994.
Eine Internet-Seite aus dem Angebot von Tino Hempel.

Für alle Seiten gilt der 
Haftungsausschluss/Disclaimer.