Informatikmaterialien |
Startseite
| Informatik | Physik
| Mathematik | Sonstiges
| |
Richard-Wossidlo-Gymnasium Ribnitz-Damgarten |
---|
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.
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
ein unendlich langes Eingabeband mit Zellen für jedes Zeichen,
eine endliche Menge von Zuständen
Lese-Schreib-Kopf auf dem Band
2. Arbeitsweise:
Einlesen des Eingabezeichens
Schreiboperation auf das Band, Bewegung des Lese-Schreibkopfes (links/rechts/keine) und Zustandsübergang in Abhängigkeit vom aktuellen Zustand und dem Eingabezeichen
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.
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}
δ:
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}
δ:
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. |