Was noch fehlt, ist das Modell, mit dem das jetzt äquivalent ist zu
den Typ-0-Grammatiken auf der Seite der analysierenden
Sprachbeschreibung.
Ein Automatenmodell müssen wir haben.
Das Automatenmodell ist hier angegeben, das sind die Turing-Maschinen.
Zunächst mal sehen die genauso aus wie die englischen Automaten.
Wir haben eine Steuereinheit, die hat interne Zustände, S0 bis Sn,
kennen wir.
Wir haben ein Eingabeband mit einem Schreib-Lesekopf, da können wir
die Zeichen lesen.
Das Wesentliche ist aber, dass wir hier ein Doppelfeil haben in beide
Richtungen.
Wir können das Band hin und her bewegen, also nicht mehr nur in einer
Richtung.
Ein Zweiweg-Band und es ist ein Schreib- und Lesekopf.
Wir können auf einmal auf dem Band Zeichen ersetzen durch andere.
Wir können in dem Bereich, wo zunächst mal noch nichts steht, das ist
durch den Stern markiert, können wir irgendwelche Zeichen
reinschreiben.
Das heißt, wir haben jetzt die Möglichkeit, auf dem Band auch zu
arbeiten.
Nicht nur zu lesen, wir können auch schreiben.
Das sind die zwei wesentlichen Unterschiede gegenüber dem endlichen
Automaten.
Wir dürfen in zwei Wege unseren Schreib- und Lesekopf bewegen, nach
links und nach rechts.
Und wir dürfen schreiben auf das Band.
Vorher hatten wir als Erweiterung des endlichen Automaten den
Kellerautomaten.
Da war das so, dass wir ein extra Band hatten.
Das war ein extra Kellerband und wir durften hier etwas reinlegen und
auch wieder rausholen.
Da durften wir im Prinzip auch schreiben, aber eben nicht auf dem
Eingabeband, sondern auf einem Extraband.
Man kann jetzt eine Variante erzeugen von den Turing-Maschinen, bei
denen man etwas analog macht.
Wir lassen jetzt unser Eingabeband, so wie vorher, ein Weg.
Und nur ein Lesekopf, der von links nach rechts die Zeichen liest.
Aber wir erlauben hier ein Arbeitsband.
Eins oder auch mehrere Arbeitsbänder, das können also durchaus mehrere
sein.
Und auf diesen Arbeitsbändern dürfen wir beliebig rumvorwerken.
Dürfen also da Sachen raufschreiben, dürfen Sachen lesen, dürfen links
und rechts das Band oder den Lesekopf bewegen.
Das heißt, wir können das so machen, dass wir ein extra Arbeitsband
erzeugen.
Der Keller war auch ein extra Arbeitsband, aber mit einer sehr
eingeschränkten Art, ihn zu bedienen.
Bei der Turing-Maschine haben wir hier ein Arbeitsband, das keine
Einschränkungen hat.
Hier können wir jedes Zeichen, das wir einmal reingeschrieben haben,
wieder anschauen, indem wir einfach das Band vorwärts-rückwärts
bewegen.
Deswegen, wenn wir auf dieses Zeichen hier gehen wollen, müssen wir
nur den entsprechenden Lesekopf dahin bewegen und können uns das
Zeichen ansehen.
Also diese Kellereinschränkungen sind hier weg.
Man kann sogar zeigen, dass man mit zwei, wenn ich diese zwei
Kellerbänder habe, in denen ich also nur diese Möglichkeit habe, was
reinzuschreiben oder wieder was rauszuholen, dann kann ich sogar ein
beliebiges Arbeitsband simulieren.
Das heißt, ein Kellerautomat mit zwei Kellerbändern, der ist genauso
mächtig wie eine Turing-Maschine mit einem beliebigen Arbeitsband.
Also, das nur ganz kurz dazu.
Jetzt könnte man sich überlegen, wenn ich jetzt hier mehrere
Arbeitsbänder hätte, nicht nur einen Arbeitsband, sondern zwei, bringt
das noch irgendeine Erweiterung?
Tatsächlich ist es so, dass Sie jede Turing-Maschine mit K
-Arbeitsbändern simulieren können, durch genau diese hier, die ein
einziges Band hat, auf dem Sie lesen und schreiben dürfen.
Sie können das alles reinkodieren in die Zeichen, die Sie auf das Band
schreiben dürfen, solange das Alphabet, das Sie auf dem Band
verwenden, eine ähnliche Größe hat.
Also, da kann man sehr viel machen, was weit über die Inhalte dieser
Vorlesung hinausgeht.
Aber die Veränderungen nochmal, Zwei-Weg-Band und die Fähigkeit zu
schreiben.
Das müssen wir jetzt geeignet definieren.
Das ist das Modell hier oben nochmal angegeben, Zwei-Weg-Band,
beliebiger Schreiblesekopf.
Turing übrigens wird so genannt, dass das eine Turing-Maschine, weil
das Alan Turing war, ein Logiker, Mathematiker in den 30er Jahren des
vorigen Jahrhunderts, hat der gleichzeitig mit einer Reihe anderer
Wissenschaftler, mit Church und noch ein paar anderen, Hermes war auch
noch dabei, mehrere Leute, die sich damals intensiv mit der Frage
beschäftigt haben, was sind eigentlich berechenbare Funktionen?
Wie kann ich eigentlich charakterisieren, dass ich eine Funktion
berechnen kann?
Wir müssen sich vergegenwärtigen, das war die Zeit, als die Rechner
entstanden sind.
Mitte der 30er hat Konrad Zuse seinen Rechner gebaut, der erste
tatsächliche programmierbare Rechner.
Der kannte allerdings die Sachen von Turing gar nicht und von Church
und so weiter.
Aber das war damals einfach die Zeit, in der das entstehen musste.
Und Alan Turing hat sich ein einfaches Maschinenmodell gemacht und
damit ausdrücken wollen, alles das, was ich mit einem Bleistift auf
Papier schreiben kann.
Ich schreibe irgendwelche Zeichen auf Papier, habe ein endliches
Alphabet und das mache ich praktisch hier mit dieser Turing-Maschine.
Also eine Einbahn-Turing-Maschine ist beschrieben durch, wie üblich,
ein Tupel von verschiedenen Begriffen.
Wir haben wieder ein Eingabe-Alphabet, wir haben ein Band-Alphabet, da
hatten wir beim Kellerautomaten ein Keller-Alphabet, das nennt sich
jetzt hier einfach Band-Alphabet.
Wobei wir bei dem Band-Alphabet auf jeden Fall dieses Zeichen, was
hier oben angedeutet war, der Stern soll andeuten, das Feld ist leer.
Ich muss ja irgendwie feststellen können, ob ein Feld meines Bandes
leer ist oder nicht.
Ich markiere einfach ein Feld mit dem Stern und gehe davon aus, das
Band ist ursprünglich nur mit Sternen vollgeschrieben.
Dann weiß ich, wenn ich den Stern sehe, ist das Feld leer, ich kann da
irgendwas reinschreiben.
Ich kann also feststellen, habe ich da was reingeschrieben oder nicht.
Dieses Sternzeichen darf natürlich nicht in der Menge der
Eingabezeichen drin sein, über die ich jetzt irgendwelche Wörter auf
das Band zu Anfang schreibe.
Das Band-Alphabet enthält natürlich eine Eingabezeichen, die zunächst
mal eingegeben werden können und der Stern muss auch mindestens drin
sein, können auch zig verschiedene andere Zeichen noch dazukommen.
Ich habe eine Zustandsmenge, ich habe eine Zustandsübergangsfunktion,
genau wie vorher beim endlichen Automaten.
Ich habe jetzt einen Zustand und ein Zeichen, das ich gerade lese.
Das ist also hier unser Zustand aus der Zustandsmenge und ich lese
jetzt gerade irgendein Zeichen.
Das Zeichen ist ein Element aus dem Band-Alphabet, deswegen S kreuz B.
Wenn ich in einem Zustand ein Zeichen lese auf dem Band, dann
entscheide ich mich, wohin ich gehe, was ich für einen
Zustandsübergang mache.
Ich kann also einen neuen Zustand bekommen, ich kann etwas Neues
schreiben, kann also ein Zeichen durch ein anderes ersetzen oder es
auch stehen lassen und ich kann mich entscheiden, ob ich nach links,
nach rechts gehe oder auf diesem Platz bleibe.
Das sind die drei Möglichkeiten, die ich hier habe für die Bewegungen
und das ist praktisch genau das, was wir brauchen, um aus einem
endlichen Automaten eine Curing-Maschine zu machen.
Beliebiges Band-Alphabet und wir können eben etwas schreiben an die
Position, wo wir vorher etwas gelesen haben und wir können
entscheiden, wohin wir laufen.
Dann haben wir noch den Anfangszustand und wir haben eine
Endzustandsmenge.
Das heißt, das ist alles gleich geblieben.
Das Wesentliche andere ist die Beweglichkeit, Zweiwegband und die
Möglichkeit, etwas zu schreiben.
Schauen wir uns das an.
Wie schreibt man so eine Funktion auf?
Wenn ich das hier hinschreibe, eine partielle Funktion, wie schreibe
ich eine Funktion auf?
Ich kann mir für jeden möglichen Zustand, jeden möglichen Zeichen
aufschreiben, was da rauskommt.
Genau das mache ich, indem ich so eine Tafel ausfülle.
Sie erinnern sich an die Zustandstafeln bei den endlichen Automaten.
Hier nennen wir diese Zustandstafeln einfach Curing-Tafeln von der
Curing -Maschine.
Das heißt, für jeden Zustand S und für jedes Zeichen B, gebe ich an,
wie ist der Folgezustand, was schreibe ich rein und was mache ich.
Also hier wird der Zustand S' angenommen, es wird B' geschrieben und
der Kopf wird bewegt, so wie das X das andeutet, nach rechts, nach
links oder er bleibt stehen.
Das ist also einfach so eine Curing-Tafel.
Und dazu muss man auch wissen, dass das Band wirklich beliebig in
beide Richtungen geschoben werden kann.
Ich gehe davon aus, dass das Band nach links und rechts unbegrenzt
ist.
Beliebig langes Band.
Man könnte auch betrachten eine Variante, bei der das Band nur nach
rechts unendlich ist, dass ich also links irgendwo ein Ende habe, ist
aber prinzipiell nichts anderes.
Deswegen lasse ich diese Einschränkung weg, das würde uns nur
Schwierigkeiten machen.
Wir nehmen an, wir haben ein links und rechts unbegrenztes Band und zu
Anfang sind wir in irgendeiner Position, ab der ein Eingabewort steht.
Und diese Curing-Maschine, die hält an, falls das Delta für
irgendeinen Zustand und ein Eingabezeichen nicht definiert ist.
Also solange ich Übergänge habe, wird immer weiter etwas getan.
Erst wenn ich nicht weiterlaufen kann, hört die Maschine auf.
Und hier ist ein kurzes Beispiel, ein sehr einfacher Automat.
Was macht der?
Der macht mehr, als ein endlicher Automat könnte.
Der macht nämlich folgendes, er ist im Anfangszustand S0 und wenn er
eine 0 sieht, dann bleibt er in dem Zustand und ersetzt die 0 durch
einen Stern und geht nach rechts.
Wenn er eine 1 sieht, dann ersetzt er die 1 durch einen Stern und geht
nach rechts.
Und wenn er einen Stern sieht, dann geht er in den Zustand S1 und
bleibt einfach stehen.
Wenn er in S1 ist, macht er gar nichts mehr.
Da könnte ich auch sagen können, hier ist also leere Menge, leere
Menge, leere Menge.
Ich habe hier praktisch keinen Eintrag drin.
Das heißt, für S1 kann ich nicht weitermachen, er hört auf, wenn er in
S1 ist.
Das heißt, wenn auf dem Band ursprünglich irgendetwas drauf stand, wie
hier sowas, dann wird das sukzessive alles gelöscht und wenn er das
alles gelöscht hat, dann steht dann irgendwann eben nichts mehr auf
dem Band, dann ist er fertig.
Das ist einfach eine Löschmaschine.
Mit dieser Maschine können Sie beliebige Eingaben auf Ihrem Band
löschen.
Hat keinen großen Wert.
Wenn wir sagen, S1 ist im Endzustand, dann würde also jedes Wort
akzeptiert werden.
Sofern ich sage, wenn er anhält und im Endzustand ist, dann wird
akzeptiert.
Hier ist nochmal ein Beispiel angegeben, da wird eben gerade ein
Eintrag 01 gelöscht.
Das ist eine ganz einfache Löschmaschine.
Also hier werden einfach die Zeichen überschrieben durch den Stern.
So, jetzt müssen wir uns natürlich überlegen, ich möchte ja wieder
davon reden, dass ich mir die Maschine anschaue und jetzt in der Lage
bin festzulegen oder festzustellen, was wird in der Zukunft alles mit
dieser Maschine passieren.
Dazu müssen wir uns eine Konfiguration überlegen, das heißt wir müssen
uns anschauen, alle Informationen, die wichtig sind für das weitere
Verhalten unserer Turing-Maschine.
Die gehören in eine Konfiguration rein.
Das eine wird sicherlich der Zustand sein, also hier ist unser
aktueller Zustand S.
Der wird sicherlich eine Rolle spielen.
Dann wird sicherlich eine Rolle spielen, an welcher Position auf dem
Band wir gerade sind.
Ja, auch wichtig.
Und es wird eine Rolle spielen, was auf dem Band steht.
In diesem Fall aber nicht mehr nur das, was nach rechts noch steht,
sondern da das Band ein Zweiwegband steht, ist auch alles relevant,
was links davon steht.
Das Problem ist aber, dieses Band ist nach links und rechts
unbegrenzt.
Was schreibe ich denn da hin?
Ich muss doch eine ähnliche Beschreibung haben.
Die Konfiguration muss in einem ähnlichen Text hinschreibbar sein.
Das heißt, was ich mir anschaue, ist alles das, was relevant ist.
Relevant sind nicht die Zeichen, die leer sind, sondern die Zeichen,
die...
also nicht der Stern, sondern alles, was nicht gleich dem Stern ist.
Das heißt, ich schaue mir das hier an und sehe irgendwo, da ist
vielleicht noch irgendein Zeichen C.
Rechts daneben nur Sternzeichen.
Oder Sterne.
Und hier auch irgendwie Stern und da steht irgendein Zeichen A.
Und dann muss ich mir genau das, was hier steht, merken.
Das ist die relevante Bandinschrift.
Und wenn ich mir jetzt noch so merke, dass ich einmal den linken Teil
mir anschaue, das ist der linke Teil, das ist der rechte Teil ab
dieser Position, dann habe ich damit auch die aktuelle Position meines
Bandes.
Das heißt, ich muss mir nur merken den Zustand.
Einen linken Teil der Bandinschrift und einen rechten Teil der
Bandinschrift.
Und das erste Zeichen des rechten Teils der Bandinschrift ist gerade
das Zeichen, das ich gerade lese.
Dazu muss ich zunächst mal die Bandinschrift definieren.
Also, die beginnt mit dem Zeichen im linkesten Nicht-Leerfeld rechts
neben einem Leerfeld.
Das sollte dieses Zeichen sein.
Das linkeste Zeichen, das nicht leer ist, irgendwo wird das stehen.
Und dazwischen können beliebig viele Leerfelder stehen.
Irgendwo steht so ein Zeichen, von da geht es los.
Und rechts muss ich eben genauso das rechteste Nicht-Leerfeld links
neben einem Leerfeld mir anschauen.
Sofern sich dieses Leerfeld rechts vom Schreiblesekopf befindet,
könnte ja sein, dass hier alles schon leer ist und dass ich hier das
letzte Zeichen hätte.
Dann würden die Leerzeichen bis zur aktuellen Position des
Schreiblesekopfes noch mit zählen zur Bandinschrift.
Also, ich muss ja wissen, wo steht der Schreiblesekopf im Augenblick.
Und ich muss wissen, was steht auf dem Band.
Und das wird alles eben ausgedrückt auf diese Art und Weise.
Konfiguration ist also jetzt unser Band VW.
Das ist die Bandinschrift.
Links steht V.
Ab dem Lesekopf steht W.
Das ist die Bandinschrift.
Seht ihr jetzt V, die Bandinschrift links vom Schreiblesekopf.
W, die Bandinschrift ab Schreiblesekopf nach rechts.
Und S ist der aktuelle Zustand.
Das heißt, diese drei Komponenten beschreiben mir vollständig alles
das, was ich wissen muss, um das weitere Verhalten dieser Turing
-Maschine ableiten zu können und bestimmen zu können.
Sofern ich noch die Turing-Tafel kenne, also die Übergangsfunktion
kenne.
Das also zu der Konfiguration.
Dann muss ich überlegen, wie geht eine Konfiguration in eine andere
über.
Naja, das ist doch ganz klar.
Wenn ich eine Konfiguration habe, dann muss ich natürlich das genauso
machen wie vorher.
Allerdings jetzt etwas mit einer Fallunterscheidung.
Abhängig davon, welches Zeichen steht bei diesem Bewegungsteil.
Ob dort steht nicht bewegen, nach rechts gehen oder nach links gehen,
sieht die Folgekonfiguration etwas anders aus.
Wenn dort also steht, dass ich nichts bewege, sondern ich bleibe an
der Position stehen, dann wird das Zeichen B an der aktuellen Position
ersetzt durch das B-Strich hier oben.
Und ansonsten bleibt alles gleich.
Also V bleibt gleich, der Zustand geht in der Strich über,
entsprechend wie hier oben steht.
Und rechts bleibt das gleiche stehen, nur das Zeichen B wird durch B
-Strich ersetzt.
Wenn ich dort stehen habe, dass ich nach rechts gehen soll, dann heißt
das doch, ich bin auf meinem Band, da steht ein B, hier steht jetzt
irgendwas daneben, steht das Wort W daneben, da stand vorher der
Lesekopf, jetzt wird B ersetzt durch B-Strich und anschließend stehe
ich rechts daneben.
Das heißt, ich habe hier links neben meinem, hier stand das V, bin
jetzt anschließend an dieser Position, habe also das hier, den
Lesekopf am 1 nach rechts bewegt, da steht links neben dem Lesekopf V
B -Strich und bin im Zustand S-Strich und rechts daneben steht das W,
sofern W ungleich Lambda ist.
Könnte ja sein, dass B das letzte Zeichen war der Band in Schrift und
dann steht hier anschließend nicht Lambda, sondern dann steht dort
einfach Stern da drin.
Hätte doch Lambda hinschreiben.
Aber hier steht halt einfach Stern.
Das ist so die Regel.
Und wenn wir nach links gehen, haben wir genau ähnliche Dinge dort
stehen, wenn wir nach links gehen, dann müssen wir halt uns angucken,
was ist das letzte Zeichen links neben meinem Schreibt-Lesekopf.
Das wird anschließend das nächste Zeichen, das ich anschaue.
Rechts daneben steht das Zeichen, das ich gerade neu geschrieben habe
und ich bin entsprechend hier weitergelaufen in einem anderen Zustand.
Auch hier wieder die Unterscheidung für W ungleich Lambda oder W
gleich Lambda.
Habe ich hier halt verschiedene Dinge hinzuschreiben.
Das ist aber alles relativ klar.
Wenn das W gleich Lambda und B Strich ungleich Lambda ist, dann ist
das ja auch noch wieder richtig.
Aber wenn das B Strich gleich Stern ist, dann steht natürlich rechts
daneben nur noch das Zeichen A und rechts daneben ist nichts mehr.
Und dann habe ich das B praktisch rausgelöscht.
Dann war hier rechts daneben alles leer in dem Fall.
Und dann habe ich das B durch B Strich ersetzt.
B Strich ist das Sternzeichen, das heißt, ich habe anschließend auf
dem Lesekopf das A stehen und bin halt eins nach links gelaufen.
Das zu diesen drei Möglichkeiten, bisschen komplizierter als vorher,
aber eben einfach nur Übergangsrelation angewandt.
Das sind die Konfigurationsübergänge, die möglich sind.
Nicht weiter schwierig.
Dann habe ich die einfachen Übergänge.
Ich habe die beliebigen Übergänge, wie üblich transitiv reflexive
Fülle unserer Relation.
Wir können beliebig häufig solche Übergänge machen und sehen dann, was
wir Übergänge hier dort erzeugen können.
Und hier hätten wir also zum Beispiel ausgehend von einer
Anfangskonfiguration, bei der hier jetzt steht Lambda S0, 0, 1.
Also zunächst mal links das leere Wort.
S0 ist unser Anfangszustand.
Wir stehen auf dem Zeichen 0.
Sind also an dieser Position hier.
Dann gehen wir über in den Zustand S0.
Haben ein Stern gelesen, ein Stern geschrieben.
Das heißt, es bleibt links neben dem Schreibwesekopf immer noch ein
leeres Wort stehen.
Rechts daneben steht die 1.
Dann wird die 1 ersetzt.
Es steht hier ein Stern.
Und wir gehen dann in S1 über, das ist dieser Übergang.
Bleiben stehen und sind fertig.
Das ist jetzt eine Konfiguration, aus der es nicht weiter geht.
Wir sind sogar in einem Endzustand und könnten sagen, dieses Wort 0, 1
wird akzeptiert, wenn wir denn Wörter akzeptieren wollen.
Noch ein anderes Beispiel.
Ich kann auch ein bisschen kompliziertere Sachen machen, damit Sie
sehen, diese Turing-Maschinen haben etwas mit Berechnungen zu tun.
Ich kann sie verwenden, um zum Beispiel zu überprüfen, ob ein Wort zu
einer Sprache gehört oder nicht.
Ich kann sie aber auch verwenden, um zu einer Bandentschrift, einfach
eine neue Bandentschrift zu erzeugen.
Und ich sage, dass die Bandentschrift nach einer Folge von
Zustandsübergängen der Turing-Maschine, die dann entstanden ist, das
Ergebnis einer Berechnung ist.
Ich habe ja irgendwas getan.
Und jetzt will ich einfach aus einer Zahl, die anfangs auf dem Band
steht, 1 0 0 1 0, auf die möchte ich eine Zahl drauf addieren.
Oder eine 1 drauf addieren, die nächste Zahl erzeugen.
Das heißt, ich benutze jetzt meine Turing-Maschine, meinen Automaten,
als ein Berechnungswerkzeug.
So, was kommt denn dabei raus?
Wenn ich hier eine 1 addiere, habe ich anschließend 1 0 0 1 1.
Wenn ich das bei diesem Wort mache, 0 1 und da stehen rechts daneben
ganz viele 1, und ich addiere hier eine 1 dazu, dann bekomme ich
natürlich einen Übertrag.
Ich habe also eine 0, habe einen Übertrag 0 und so weiter.
Dann ist hier an der letzten Position, habe ich dann auf die 0 noch
eine 1 zu addieren, den Übertrag und komme mit einer 1 raus.
Habe also hier dann 1 und die ganzen Nullen dann rechts daneben
stehen.
Das heißt, es kann sein, wenn ich jetzt erstmal mein Wort mir
anschaue, fange ich an der ersten Position an, laufe ganz nach rechts.
Das ist einfach zu machen.
Rechts rüber laufen.
Vorher hatten wir eine Nach-Rechts-Lauf-Maschine gemacht, bei der wir
die Zeichen alle gelöscht haben.
Jetzt lassen wir die Zeichen stehen.
Das steht hier.
Nach rechts laufen bis zum ersten Stern.
Also, wenn wir eine 0 sehen, lassen wir die 0 stehen, gehen nach
rechts, bleiben im gleichen Zustand.
Wenn wir eine 1 sehen, lassen wir die 1 stehen, gehen nach rechts,
bleiben im gleichen Zustand.
Wenn wir einen Stern sehen, dann sind wir rechts neben dem Wort und
wollen jetzt nach links laufen.
Sind also anschließend über dem letzten Zeichen und haben uns das
gemerkt, indem wir in einen anderen Zustand gehen, in S1.
Also das Umkehren ist praktisch jetzt hier dieses von rechts auf links
umschalten und einen neuen Zustand gehen.
Jetzt müssen wir eine 1 addieren.
Eine 1 addieren zu dem Zeichen, das wir gerade sehen.
Wir sind rechts angekommen und haben gesehen, jetzt müssen wir eine 1
addieren.
Wenn wir also eine 0 sehen, wenn wir im Zustand S1 sind, sehen wir
eine 0.
Dann brauchen wir die 0 nur durch eine 1 zu ersetzen, gehen in den
Zustand S2.
Das wird unser Endzustand sein, aus dem wir nichts weiter machen
können.
Wir sind nämlich in diesem Fall fertig, der hier angedeutet ist.
Da ist einfach die 0 durch eine 1 ersetzt worden, wir brauchen nicht
weiter zu laufen.
Wenn aber wie an dieser Situation jetzt das Zeichen, das wir sehen,
eine 1 ist, dann wissen wir, wenn wir eine 1 drauf addieren, binär,
dann wird daraus eine 0.
Und wir haben die gleiche Aufgabe wie vorher, wir müssen eine 1
addieren zu der Position, das gerade links daneben steht.
Das heißt, wir gehen 1 nach links, haben die 1 durch eine 0 ersetzt
und schauen, was da für ein Zeichen ist.
Und wenn wir uns das hier anschauen, würden wir also hier sukzessive
immer weiter nach links laufen bis zu der Position, sehen dort die 0,
ersetzen die durch eine 1, gehen in den Zustand S2 über und sind dann
fertig.
Da brauche ich keinen Übergang mehr zu machen, S2 wird ein Endzustand.
Und wir können dann also zum Beispiel für dieses Wort hier 1011 uns
anschauen, wie wir hier durchlaufen.
Wir haben zunächst mal links nichts stehen, sind auf dem ersten
Zeichen der 1, lassen die 1 links liegen, sind auf der 0, lassen die 0
links liegen, lassen die 1 links liegen, lassen die noch eine 1 links
liegen, sind dann im Zustand S1 gelandet, von S0 auf S1 und sind 1
nach links gelaufen.
Das heißt, wir sind jetzt auf der letzten 1.
Die letzte 1 wird durch eine 0 ersetzt und wir gehen nach links, sind
wieder auf einer 1, die wird durch eine 0 ersetzt.
Wir sind dann aber auf einer 0, müssen jetzt zu der 0 noch eine 1
addieren, haben da eine 1 hingeschrieben, haben hier links daneben
noch eine 1 stehen, sind aber schon im Zustand S2, sind fertig und
haben damit auf das Wort 1011 eine 1 addiert und das Wort 1100
erzeugt.
Also mit dieser einfachen Maschine können wir auf eine Zahl eine 1
drauf addieren bzw.
sie um 1 erhöhen, auf eine binäre Zahl.
Nur, dass Sie sehen, was man mit solchen Turing-Maschinen machen kann.
Ein sehr einfaches Rechengerät.
Was uns eigentlich interessiert ist, wie sieht das aus mit dem
Akzeptierungsverhalten, da kamen wir ja eigentlich her.
Zu den Berechnungen kommen wir später noch.
Also, jetzt habe ich auf dem Band, auf meinem Band, meiner Turing
-Maschine irgendein Wort W stehen, links und rechts daneben stehen nur
Sterne und die Frage ist, wann kann ich sagen, dass das Wort
akzeptiert wird und es ist klar, wir haben eine bestimmte
Anfangskonfiguration, das ist immer diese Konfiguration und eine
Endkonfiguration wird irgendwann erreicht, wenn wir nicht weitermachen
können und das ist eine akzeptierende Endkonfiguration, wenn also das
S ein Endzustand ist.
Dann sagen wir, das Wort ist akzeptiert und es kann also im Extremfall
sein, dass wir anfangen mit Lambda S0W und wenn der Automat gar keine
Übergänge hat und das S0 ein Endzustand ist, dann wären wir schon
fertig.
Wir bräuchten gar nicht zu lesen.
Wir könnten Automaten bauen, eine Turing-Maschine, die ganz faul ist,
die einfach jedes Wort akzeptiert, indem sie Anfangszustand gleich zum
Endzustand machen, dann wird jedes Eingabewort akzeptiert.
Ein sehr langweiliger Automat, der guckt sich nicht mal an, was auf
dem Band steht.
Aber das wäre ein Automat, der im Prinzip jedes Wort akzeptiert.
Also das geht relativ einfach.
Das nochmal hier die Situation etwas allgemeiner.
Anfangs sind wir im S0 auf dem linkesten Zeichen unseres Wortes und
anschließend sind wir irgendwann irgendwo auf dem Band und da steht
irgendein V1, V2, das ist irgendein anderes Wort, das dazwischen
entstanden ist.
Wir sind in einem Endzustand und kommen aus diesem Endzustand nicht
mehr raus, weil es keinen Übergang gibt.
Dann wird das Wort, das zu Anfang drauf stand, akzeptiert.
Also das ist die Akzeptierung und damit haben wir sofort diese Regel.
Also ein Wort wird akzeptiert, wenn wir aus der Anfangskonfiguration
auf eine Endkonfiguration kommen können.
Wobei das Wort Endkonfiguration nur für diejenigen steht, bei denen
das S ein Endzustand ist.
Und damit haben wir dann auch die Sprache definiert.
Alle Wörter, die akzeptiert werden, sind in der von T akzeptierten
Sprache drin.
Wir haben damit die Sprache, die von Turing-Maschinen erkannt werden.
LTM.
Und jetzt muss es natürlich interessieren, welche Beziehung besteht
zwischen dieser Menge von Sprachen, die von Turing-Maschinen erkannt
werden können oder akzeptiert werden können und den Sprachen, die
durch Grammatiken erzeugt werden können.
Da kommen wir gleich drauf.
Hier nochmal kurz die ganzen Möglichkeiten, die es geben kann.
Es kann sein, dass die Turing-Maschine überhaupt gar nicht anhält.
Die rattert einfach immer weiter.
Kommt in irgendeine Schleife und wenn sie in der Schleife ist, dann
hält die nie an.
Die arbeitet immer weiter.
Dann ist sie halt, kann ich nie sagen, ob das Wort akzeptiert wird
oder nicht.
Wenn sie unendlich läuft, läuft sie unendlich.
Dann wird das Wort eben nicht akzeptiert.
Also wenn sie nie anhält, wird das Wort nicht akzeptiert.
Dann kann sie anhalten, aber nicht im Endzustand sein.
Also kein akzeptierender Zustand.
Das ist dann die Ablehnung.
Das Wort wird nicht akzeptiert.
Das Wort braucht natürlich, hatte ich schon gesagt, nicht vollständig
gelesen zu werden.
Und das Wort kann auch verändert werden.
Auch problemlos möglich.
Das heißt, auf die Art und Weise gibt es also viele Möglichkeiten zu
sagen, ein Wort wird akzeptiert oder nicht akzeptiert.
Das sind halt diese verschiedenen Situationen, mit denen man hier zu
tun hat.
Diese Sprache A auch N, B auch N, C auch N, hatten wir gesagt, wird
durch keinen Kellerautomaten akzeptiert.
Wir können eine Turingmaschine dafür bauen.
Überlegen wir uns mal, wie wir das machen.
Die Idee, also wie üblich unser Beispiel hier A, A, A, B, B, B, C, C,
C.
Das steht auf dem Band.
Jetzt wollen wir überprüfen mit einer Turingmaschine, ob diese Sprache
akzeptiert werden kann, ob dieses Wort akzeptiert werden kann.
Wie machen wir das?
Diese Turingmaschine geht zunächst mal zum linkesten A.
Das linkeste A, da steht es ja zu Anfang drauf.
Also das linkeste A, da sind wir zunächst mal.
Die Idee ist jetzt folgende.
Das will ich Ihnen einfach mal hier so darstellen.
Wir ersetzen das durch einen Null.
A wird einfach durch einen Null ersetzt.
Und dann machen wir folgendes, wir gehen nach rechts von hier aus und
suchen das erste B.
Und ersetzen das erste B durch eine Eins.
Und dann gehen wir nach rechts, suchen das erste C und ersetzen das C
durch eine Zwei.
Ich schreibe jetzt einfach die neuen Zeichen oben drüber, weil ich
hier nicht so viel durchstreichen will.
So, jetzt haben wir das also durch eine Zwei ersetzt.
Und jetzt machen wir das gleiche nochmal.
Das wird einfach wiederholt.
Dann geht der Scheinwerferkopf so lange nach links zurück, bis er auf
die erste Null trifft.
Also ich suche wieder das linkeste A.
Das linkeste A ist jetzt dieses hier.
Ersetzt das durch eine Null, da geht er zu B, ersetzt das durch eine
Eins.
C wird durch eine Zwei ersetzt.
Dann läuft er wieder nach links, bis zum linkesten A, ersetzt das A
durch eine Null.
Ersetzt das B durch eine Eins, ersetzt das C durch eine Zwei.
Geht nach links, sucht das linkeste A.
Findet er nicht.
Er kommt nämlich hier auf die erste Null.
Kommt an diese Position, hat da eine Null.
Geht nach rechts, da müsste es rechts daneben stehen.
Da steht aber eine Eins.
Also, wenn jetzt kein A mehr da ist, dann darf natürlich auch kein B
und kein C mehr vorhanden sein.
Das heißt, er hat jetzt kein A gefunden.
Jetzt geht er nach rechts und sucht nach einem B.
Findet er auch nicht.
Er findet nur Einsen.
Er geht nach rechts, sucht nach einem C.
Findet er auch nicht.
Findet nur Zweien.
Wenn er aber kein B und kein C mehr gefunden hat, nachdem er kein A
und kein B gefunden hatte, dann ist er ja praktisch in der Situation,
dass er weiß, ich habe auf eine Folge von As gleich viele Bs gehabt
und danach gleich viele Cs.
Das heißt, ich habe genau dieses Wort A hoch 3, B hoch 3, C hoch 3 auf
meinem Band.
Die Bedingungen sind erfüllt.
Ich kann dieses Wort akzeptieren.
Danach geht er also in den Endzustand und ist dann fertig.
Und das ist die ganze Idee, die man jetzt in eine Turing-Tafel
schreiben muss.
Also, link ist das A durch ein Null ersetzen, dann nach rechts laufen,
das erste B durch ein Eins ersetzen, nach rechts laufen, das erste C
durch ein Zwei ersetzen, nach links laufen, bis man ein Null findet,
das nächste Zeichen überprüfen, ob es ein A ist, das durch ein Null
ersetzen und so weiter.
Das steht jetzt alles auf der nächsten Folie drauf.
Hier haben wir das Eingabealphabet natürlich ABC.
Bandalphabet muss jetzt neben ABC auch noch Null, Eins und Zwei
enthalten und natürlich das Sternzeichen.
Und dann können wir jetzt die Tabelle aufbauen.
Von S0 aus wollen wir erstmal, wenn wir also ein A sehen, wollen wir
dieses erste A durch ein Null ersetzen und nach rechts laufen.
Jetzt wollen wir weiterlaufen, wenn wir im Zustand S1 sind.
Wir haben also jetzt das erste A ersetzt.
Jetzt kommt der Punkt, wir wollen nach rechts laufen bis zum nächsten
B.
Das heißt, über die folgenden A laufen wir hinweg, lassen das A immer
stehen.
Sobald wir ein B finden, ersetzen wir das B durch eine Eins.
Merken wir uns, dass wir ein B gefunden haben, gehen also in neuen
Zustand S2 und müssen jetzt entsprechend weiterlaufen über alle Bs
hinweg, bis wir ein C finden und jetzt dieses C durch eine Zwei
ersetzen.
Und dann gehen wir nach links.
Für ein A fehlt hier aber gar nichts drin.
Es soll ja auch kein A auftauchen.
Wenn jetzt ein A aufgetaucht wäre, sollten wir schön aufhören und
sagen, fertig, kein Endzustand.
Das ist kein akzeptables Wort.
Jetzt laufen wir also von dem S3 aus, also im Zustand S3 nach links,
über, ja, wir hatten eine Zwei geschrieben, links neben der Zwei
können eventuell andere Zweien gestanden haben.
Da wird irgendwo auch mal eine Eins gestanden haben.
Es kann dort ein B gestanden haben und ein A.
Auch mehrere As.
Solange wir also diese Zeichen sehen, laufen wir mal nach links, bis
wir eine Null finden.
Wenn wir die Null gefunden haben, wissen wir, aha, jetzt haben wir
diese Null, die ist vorher früher mal ein A gewesen, rechts daneben
sollte oder könnte noch ein A stehen.
Wir sind also in der gleichen Situation wie zu Beginn und gehen auf
die Position rechts neben dieser Null und sind im Zustand S0.
Im Zustand S0, wenn wir dort ein A sehen, gehen wir in S1, schreiben
eine Null und gehen nach rechts und so weiter.
Damit haben wir also genau diesen Zyklus, erstes A durch eine Null
ersetzen, nach rechts laufen, B durch eine Eins ersetzen, nach rechts
laufen, C durch eine Zwei ersetzen, nach links laufen bis zur nächsten
Null.
Genau durch diese Übergänge erledigt.
Jetzt fehlt noch der Rest.
Wir müssen jetzt weiter dafür sorgen, das ist klar, wenn in S0 ein A
gefunden wird, beginnt die Prozedur von neuem und jetzt müssen wir
aufpassen, wenn wir in S0 ein A gefunden haben, eine Null dort
hingeschrieben haben, wir haben die Null gesehen, das haben wir jetzt
hier, da kommt gleich noch was dazu.
Wenn wir dort in dem Zustand S0 ein A sehen, das ist klar, dann gehen
wir in Zustand S1, haben dann Null geschrieben und gehen nach rechts.
Wenn wir aber in dem Zustand S0 rechts neben der Null eine Eins sehen,
dann gehen wir in einen neuen Zustand S4 und gehen nach rechts, laufen
über alle Einsen hinweg.
Im S4 müssen wir noch mehr machen, wir müssen nämlich bei S4 schauen,
solange wir hier Einsen stehen haben, ist alles gut, wir gehen nach
rechts.
Solange dort nur Zweien stehen, ist alles gut, wir gehen nach rechts.
Wenn dort eine Null auftauchen würde, kann gar nicht auftauchen, haben
wir nicht hingeschrieben, aber wenn dort ein A, B oder C auftauchen
würde, insbesondere ein B oder C, wäre es natürlich fatal, aber da
haben wir keinen Übergang.
So, wir bleiben also schön in unserem S4 und laufen nach rechts.
Und wenn wir in dem S1 sind und wir sehen, wir hatten das A durch eine
Null ersetzt, gehen nach rechts, genau, wenn da eine Eins steht, gehen
wir weiter nach rechts, wenn da eine Zwei steht, gehen wir nach
rechts, das war alles vorher schon da, das ist alles kein Problem und
wenn wir jetzt durchgelaufen waren über alle Einsen und Zweien und
sehen, ob wir, wir sehen es sind keine A's, B's und C's mehr
aufgetaucht, wir sehen das Leerzeichen, sind also rechts neben dem
eingegebenen Wort, dann gehen wir in einen Zustand S5 über, von dem
aus wir nichts mehr machen können und sind fertig.
Das heißt, S5 hat keine Übergänge und wir sind, sobald wir den S5
haben, fertig, wir haben überprüft, ob gleich viele A's, B's und C's
vorkommen, ob die in der richtigen Reihenfolge sind und sind damit
dann fertig, haben das Wort akzeptiert.
Das ist eine einfache Maschine, einfache Turing-Maschine, mit der wir
das Wort A3, B3, C3 beziehungsweise jede beliebiges Wort A auch in B
auch in C auch in N akzeptieren können und damit die Sprache A auch in
B auch in C auch in N allgemein.
Das ist hier nochmal die Tabelle.
Wenn wir uns jetzt anschauen, um also das Wort ABC zu akzeptieren, das
ist also relativ einfach, nur ABC, da würden wir also einmal von S0
aus das A durch eine 0 ersetzen, würden das B sehen, das B durch eine
1 ersetzen, das C sehen, das C durch eine 2 ersetzen und nach links
gehend auf die 1 suchen dann hier, also sehen hier die 1, gehen weiter
zurück, finden die 0 und wenn wir die 0 sehen, müssen wir nach rechts
gehen, sind in S0, sind auf der 1, bei S0 und 1, S0, 1, da gehen wir
in Zustand S4 über, lassen die 1 links liegen, sehen die 2, lassen die
2 links liegen, sehen den Stern, gehen nach S5 und bleiben stehen, wir
gehen sogar hier nochmal 1 nach links, so habe ich gesagt, wir gehen 1
nach links, bleiben also auf dem letzten Zeichen unseres Wortes
stehen, auf dem letzten 2 in dem Fall und haben damit das Wort
akzeptiert.
Das ist ganz einfach, der Automat ist also relativ leicht zu
konstruieren und hier haben wir das Problem jetzt beseitigt, dass wir
beim Kellerautomaten hatten, bei dem wir sagten, wir können zwar
überprüfen, ob gleich viele NBs folgen, aber haben dann die
Möglichkeiten des Kellers schon voll ausgeschöpft, können nicht mehr
feststellen, ob auch noch genügend Cs folgen.
Mit diesem Arbeitsband können wir das machen, indem wir halt ein
bisschen drauf herumarbeiten.
Also wir können in der Turingmaschine den Lesekopf beliebig nach links
oder rechts bewegen, wir können natürlich über Zeichen rüberlaufen,
brauchen die gar nicht aktiv zu bearbeiten, wobei wir natürlich für
jedes Zeichen wir irgendetwas tun, also wenn wir jetzt sagen, kann
Zeichen übergehen, heißt das, das Zeichen kann nochmal genauso wieder
hingeschrieben werden, das sehen wir ja zum Beispiel hier, wenn wir
eine 1 lesen und eine 1 hinschreiben und es können natürlich auch
Zeichen verändert werden, das haben wir hier aktiv ausgenutzt.
Also das zu der Turingmaschine.
Damit haben wir das nächste Maschinenmodell entdeckt.
Es kommt noch das nächste Modell dazu, wie immer Automaten können
deterministisch oder nicht deterministisch sein.
Bei den Turingmaschinen können wir auch nicht deterministische
Turingmaschinen definieren, bei denen dann diese Übergänge nicht auf
eine Folgezustand Zeichen, das wir schreiben und Bewegungsrichtung
gehen, sondern wir haben jetzt Mengen von möglichen Übergängen.
Genau wie vorher und genau wie vorher, ein Wort wird akzeptiert, wenn
es in der Menge möglicher Konfigurationsfolgen eine
Konfigurationsfolge gibt, die zu einer Endkonfiguration führt.
Also das ist hier unsere Ausgangskonfiguration C0 und dann gibt es
halt viele Möglichkeiten von dort wieder auf C1, C2, C3 und so weiter
hier wieder zu verzweigen.
Wenn wir irgendeinen Pfad finden, der zu einer Endkonfiguration CE
führt, dann wird das Wort akzeptiert.
Da können beliebig viele andere Folgen dabei sein, bei denen wir nicht
auf eine Endkonfiguration kommen.
Das ist genau das gleiche wie bei den nicht deterministischen
endlichen Automaten oder nicht deterministischen Kellerautomaten.
Also dann haben wir hier auch wieder die von einer solchen nicht
deterministischen Turingmaschine akzeptierten Sprachen einfach
definiert.
Es muss also eine akzeptierende Folge von Konfigurationen geben.
Das ist genau identisch gemacht zu dem, was wir vorher auch gemacht
haben und jetzt können wir damit uns fragen, ist das eine zusätzliche
Mächtigkeit, wenn wir Nicht-Determinismus erlauben.
Bei den Kellerautomaten haben wir gesehen, da bekommen wir eine echte
Erweiterung dadurch, dass wir einen Nicht-Determinismus drin haben.
Wir hatten ja diese Sprache der Palindrome gesehen, die wir nicht
durch einen deterministischen Kellerautomaten akzeptieren können, aber
durch einen nicht deterministischen Kellerautomaten.
Hier steht jetzt ein Satz, bei den Turingmaschinen spielt es keine
Rolle, ob wir sie deterministisch oder nicht deterministisch
betrachten, zumindest in Bezug auf die Mächtigkeit der Sprachen, die
wir damit erzeugen können oder akzeptieren können.
Das heißt, hier haben wir Gleichheit in Bezug auf die Anzahl der
Sprachen oder die Klasse der Sprachen, die akzeptierbar sind durch
Determinismus oder Nicht-Determinismus mit Turingmaschinen.
Die Idee sieht wie folgt aus, ich habe meine Anfangskonfiguration und
jetzt will ich gerne mit einem deterministischen Turingmaschine das
nachbilden, was die nicht deterministische Turingmaschine gemacht hat.
Die nicht deterministische Turingmaschine, hatte ich ja gesagt, die
hat irgendeinen Pfad, der irgendwann auf eine Endkonfiguration führt.
Um jetzt mit einer deterministischen Turingmaschine das nachzubilden,
was die nicht deterministische macht, gehe ich einfach wie folgt vor.
Das ist meine Anfangskonfiguration.
Jetzt baue ich mir eine deterministische Turingmaschine, die einfach
auf ihr Band als nächstes folgendes schreibt.
Schreibt hier hin, Konf 1 und so weiter bis Konf K.
Das heißt, diese deterministische Turingmaschine schreibt einfach alle
Konfigurationen, die mit der nicht deterministischen Turingmaschine
möglich sind, nacheinander auf das Band.
Ich kann ja einfach die Konfiguration auf das Band schreiben, auf dem
Band habe ich beliebig Platz.
Unbegrenzt.
Und dann ersetze ich einfach das, was dort stand, Konf 1 bis Konf K,
durch alle Konfigurationen, die ich dann entsprechend wieder hier
erzeugen könnte.
Das sind auch nur endlich viele.
Für jede Konfiguration gibt es eine beschränkte Möglichkeit von
Nachfolgekonfigurationen.
Die schreibe ich mir alle der Reihe nach auf das Band.
Ich muss natürlich dann die anderen Sachen vorbilden.
Ich kann auch alles ganz rechts daneben schreiben.
Ich habe ja beliebig Platz.
Schreibt mir daneben einfach dann die nächste Ebene hin.
Und dann schreibe ich die nächste Ebene dahin.
Und die nächste Ebene.
Und irgendwann bin ich in einer Ebene, bei der diese Konfiguration mit
dabei ist.
Das heißt, wenn ich einfach rechts neben mein aktuelles Bandinschrift
immer die nächsten Konfigurationen hinschreibe, die ich mit meiner
nichtdeterministischen Turingmaschine hätte erzeugen können, komme ich
irgendwann zu einer Bandinschrift, die gerade diese akzeptierende
Konfiguration enthält.
Das heißt, wenn ich mit einer nichtdeterministischen Turingmaschine
eine akzeptierende Konfigurationenfolge habe, einen solchen Pfad, dann
werde ich diese akzeptierende Konfiguration erreichen, nach einem zwar
langen, aber endlichen Prozess.
Das heißt, ich kann deterministisch das nachbilden, was hier
nichtdeterministisch durch die nichtdeterministische Turingmaschine
gemacht wurde.
Der Aufwand wird allerdings sehr hoch.
Und zwar, können Sie sich das sofort überlegen, wenn ich jetzt alle
Ebenen so eines Baumes hier nachbilden muss, das geht natürlich
exponentiell in die Zeit.
Das heißt, wenn ich vorher meinetwegen lineare Zeit hatte, wenn die
Pfadlänge hier irgendwie Pfadlänge n, habe ich eine Arbeitszeit, um
alle diese Ebenen nacheinander zu erzeugen von mindestens 2 hoch n.
Wenn ich noch mehr, wenn ich also nur 2, also Verzweigungsgrad von 2
hätte, wäre das 2 hoch n Größenordnung.
Wenn ich einen größeren Verzweigungsgrad habe, wäre es noch deutlich
mehr.
Da wäre das halt Verzweigungsgrad hoch n.
Sehr, sehr viele Konfigurationen müsste ich mir rausschreiben.
Das heißt, ich hätte dann einen exponentiellen Zeitunterschied.
Aber ich kann es nachbilden deterministisch.
Das heißt, dieser Satz hier ist richtig.
Ich kann alles, was nichtdeterministisch möglich war, deterministisch
simulieren.
Deswegen, andersherum ist sowieso kein Problem.
Alles, was deterministisch gemacht werden kann, ist ja insbesondere
Spezialfall von nichtdeterministisch.
Also das ist diese Richtung hier einfach.
Diese Richtung haben wir uns gerade überlegt.
Damit ist dieser Satz also sehr einfach bewiesen.
Also schichtweise Simulationen erreicht auch die nichtdeterministische
Tugendmaschine diese Endkonfiguration.
Und damit haben wir das erreicht, aber eben mit exponentiell höherer
Laufzeit.
Und das werden wir später noch brauchen, wenn es um
Komplexitätsbetrachtung geht.
Das nächste ist, dass wir natürlich zu jedem endlichen Automaten eine
äquivalente Tugendmaschine haben, wenn nur eine spezielle
Tugendmaschine.
Jeder Kellerautomat ist nur eine spezielle Tugendmaschine mit gewissen
Einschränkungen für das Band.
Also habe ich alle Sprachen, die von endlichen Automaten oder
Kellerautomaten akzeptiert werden, die sind auch durch Tugendmaschinen
akzeptierbar.
Und das andere, was wichtig ist, es ist tatsächlich die Menge der Typ
Null Sprachen, gerade die Menge der Tugendmaschinen erzeugbaren
Sprachen.
Ich muss einfach jetzt nur Folgendes machen.
So geht es nicht, das wäre zu schnell.
Im Prinzip ist die Idee genauso, wie wir die beim Kellerautomaten für
Gottesfreie Grammatiken gemacht haben.
Wir simulieren einfach die Ableitungen auf dem Band.
Wir simulieren einfach die Ableitung eines Wortes, indem wir von dem
Wort aus wie nach links laufen, rückwärts.
Wir lassen das nicht deterministisch machen, brauchen ja nur
entsprechende rechte Seiten von Regeln zu suchen und können die dann
entsprechend rückwärts einsetzen und haben dann die Ableitung
rückwärts simuliert.
Das steht hier genau da, wir suchen ein Teilwort Psi-I, einer Regel
Psi -I auf Psi-I, ersetzen das Teilwort Psi-I durch Phi-I, machen das
nicht deterministisch und haben dann für jedes Wort aus L von G
mindestens eine akzeptierende Konfigurationenfolge und haben damit
gezeigt, dass wir jede Typ 0 Sprache auch durch eine Tugendmaschine
erzeugen können.
Und in einer anderen Richtung wird das etwas komplizierter, da müssen
wir die Übergangsfunktion der Tugendmaschine durch Regeln der
Grammatik simulieren.
Das zeige ich Ihnen jetzt nicht mehr, aber damit haben wir eben
gezeigt, dass L0 gleich LTM ist und wir haben damit für jede Klasse
gezeigt, dass es da ein äquivalentes Maschinenmodell gibt und ein
Grammatikmodell.
Bis auf Kontextsensitiv, das kommt nächstes Mal.
Jetzt kommen wir also wieder auf diese Folie zurück.
Eine Tugendmaschine mit linearer Bandbeschränkung.
Ich hatte gerade eben erzählt, diese Tugendmaschinen sind beliebig
groß bezogen auf die Länge ihres Eingabebandes.
Und jetzt sage ich eine Tugendmaschine mit linearer Bandbeschränkung.
Also, wir haben hier unser Band und sagen auf einmal, ich betrachte
nur eine gewisse Länge dieses Bandes und mehr habe ich nicht zur
Verfügung.
Das ist ja eine gravierende Einschränkung, da kann ich ja sowas wie
vorher dieses Nichtdeterministische simulieren, durch Deterministismus
kann ich ja damit gar nicht machen, aber das ist auch ein anderes
Problem.
Wir schauen uns jetzt an, eine Tugendmaschine, bei der nur ein
beschränkter Teil des Bandes benutzt werden darf.
Linear in der Länge des Eingabewortes.
Und man modelliert das so, dass man irgendwo ein Begrenzungssymbol
darauf schreibt und man geht davon aus, dass man links nicht über das
Anfangszeichen hinausgehen darf, also nur von dem ersten Symbol des
eingegebenen Wortes an, bis zu diesem Symbol Dollarzeichen.
Das ist der zur Verfügung stehende Platz, das heißt unser Wort, das
wir bearbeiten, zu Anfang steht irgendwo hier drauf, vielleicht ist da
noch ein bisschen mehr Platz und dann geht es darum, was können wir
mit dem Inhalt machen.
Also, man nennt dann eine solche Tugendmaschine einen linear
beschränkten Automat, der also ein linear beschränktes Eingabe- und
Arbeitsband hat.
Diese Eigenschaften des linear beschränkten Automaten liegen zwischen
den Tugendmaschinen und den Kellerautomaten.
Man kann sich aber Folgendes vorstellen.
Ich hatte Ihnen, als ich Ihnen etwas erzählt hatte über
kontextsensitive Sprachen und Grammatiken, hatte ich gesagt, bei den
kontextsensitiven Sprachen oder Grammatiken ist es so, dass wir ja,
sofern wir irgendwie sehen wollen, ist ein Wort in der Sprache, da
hatten wir gesagt, wir gucken uns einfach alle Wörter ab, die wir
ableiten können, aus unserem Startsymbol und natürlich ist das nicht
nur eine einfache Folge, sondern es sind viele Folgen und irgendwann
hat man hier irgendein Wort WN und ich schaue mir einfach alle Wörter
an, bis zu der Länge meines Wortes W.
Ich habe also ein Wort W, über das ich feststellen will, liegt das in
der Sprache oder nicht und dann gucke ich mir einfach alle Wörter an
bis zur Länge W.
Und das Ganze kann ich sehr gut machen, weil ich ja weiß, bei
kontextsensitiven Grammatiken, da habe ich niemals rechts kürzere
Wörter als links.
Das heißt, die Länge der Wörter, die ist nicht fallend.
Wenn das so ist, dann heißt das, wenn ich rückwärts gehe, wenn ich
also von dem Wort WN hier anfange oder von dem Wort W anfange und mich
jetzt nach hinten bewege, wieder in Richtung auf den Anfang zu der
Ableitung, dann werden die Wörter, die ich erzeugen müsste, niemals
länger.
Einfach gedacht, könnte ich also einfach mein Wort W, das steht ja zu
Anfang auf dem Bann, jetzt könnte ich ja einfach nicht deterministisch
alle möglichen Ersetzungen, wenn ich also irgendwelche Regeln habe, V
kann auf C abgeleitet werden, die einfach rückwärts durchführen.
Ich suche mir irgendeine rechte Seite, die in meiner Grammatik
auftaucht.
Ich darf die durch eine linke Seite ersetzen auf dem Rückwärtsweg.
Wenn das Wort in der Sprache ist, gibt es eine solche Folge von
Rückwärtsersetzungen, die zum Startsymbol irgendwann führt.
Und wir wissen, auf dem Weg dahin wird mein Wort, das auf dem Bann
steht, niemals länger werden.
Aber das heißt doch, wenn ich ein Wort einer kontextsensitiven Sprache
hier drauf stehen habe, dann kann ich ja genau auf der Fläche oder auf
dem Platz, den ich für die Eingabe des Wortes brauchte, all das
nachbilden, was ich brauche, um rückwärts zu gehen von dem Wort W
wieder zurück, ob ich zu dem Wort S oder zu dem Startsymbol S kommen
kann.
Das heißt, mir reicht der Platz aus, den ich habe, um tatsächlich zu
überprüfen, ob das Wort aus der Sprache ist oder nicht.
Mir reicht sogar genau die Länge des Wortes.
Und damit sehen wir eigentlich sofort ein, da ich auf dem Arbeitsband
genau rückwärts die Reduktion seines Wortes bis hin zum Startsymbol
simulieren kann und das Wort niemals länger wird, reicht auf jeden
Fall eine Turing-Maschine mit linearer Bandbeschränkung aus, um alle
Wörter einer kontextsensitiven Sprache zu erkennen.
Das heißt, diese Maschinen sind offensichtlich geeignet als
Automatenmodell für die kontextsensitiven Sprachen.
Und das steht jetzt hier auch genau drin.
Zu jeder Typ-1-Grammatik gibt es einen linearbeschränkten Automaten T
mit L von T gleich L von G und umgekehrt.
Das heißt, die Menge der kontextsensitiven Sprachen ist gleich der
Menge der Sprachen, die durch linearbeschränkte Automaten erzeugt
werden.
Die eine Richtung habe ich gerade eben erklärt, diese Richtung.
Die andere Richtung ist nicht ganz so einfach, denn linearbeschränkter
Automat heißt ja mehr als nur genau das Wort oder der Platz für dieses
Wort steht zur Verfügung.
Bei linearbeschränktem Automat darf ich sogar einen linearbeschränkten
Anteil nehmen.
Ich darf also auch den doppelten, dreifachen oder fünffachen Platz
nehmen für ein Wort, aber es muss linearbeschränkt bleiben.
Das heißt, ich darf sogar noch mehr.
Und selbst wenn ich also nicht nur genau die Fläche oder den Platz zur
Verfügung habe für das Wort, das zu Anfang auf dem Band steht, für
meine ganzen Zwischenberechnungen, selbst dann kann ich das durch eine
kontextsensitive Grammatik nachbilden.
Und das, was ich Ihnen gerade eben sagte, war ja auch so, das war sehr
nicht deterministisch.
Und man kann eben auch gucken, geht das alles deterministisch?
Das ist noch eine andere Frage, auf die ich jetzt nicht weiter
eingehen will.
Also, das ist die Menge aller Sprachen, die durch nicht
deterministische linearbeschränkte Automaten erkannt werden können.
So hatte ich das gerade eben erklärt.
Ich glaube, diese eine Richtung war deutlich, die andere Richtung, die
habe ich jetzt nicht genauer erläutert.
Wir haben auf jeden Fall damit für alle Sprachklassen der Chomsky
-Hierarchie äquivalente Beschreibungen durch Automaten.
Das heißt, wir haben sowohl erzeugende Beschreibungen, das waren die
Grammatiken, wir haben analysierende Beschreibungen, das sind die
Automaten und für eine Sprachklasse, nämlich die Typ-3-Sprachen, haben
wir auch noch die operationelle Charakterisierung durch die regulären
Ausdrücke.
Das ist also unsere Charakterisierung dieser Sprachen.
Und, achso, hier ist nochmal kurz angegeben, wie man das genau machen
kann.
Das habe ich Ihnen ja schon erläutert, deswegen kann ich über diese
Folie sehr schnell weitergehen.
Das ist genau der Algorithmus.
Wir reduzieren einfach so lange unser Wort auf dem aktuellen Band, bis
wir tatsächlich irgendwann die Band in Schrift S wieder haben.
Rechts daneben natürlich dieses Symbol Dollar.
Das war die Begrenzung für unsere Länge des Bandes und damit sind wir
also in der Lage zu zeigen, wie man aus kontextsensitiven Grammatiken
linear beschränkte Automaten macht.
Das hatte ich Ihnen schon erläutert.
Wir haben damit jetzt zusammenfassend Folgendes gesehen.
Sehr vieles, steht ja alles Mögliche schon mal drin.
Das Einfachste war hier unten die Charakterisierung der Typ-3-Sprachen
durch diese drei verschiedenen Methoden.
Wir haben gesehen, dass es hier bei den Kontextfreien eine wichtige
Teilklasse gibt, die LRK-Grammatiken bzw.
deterministischen Kellerautomaten, mit denen wir darüber zunächst
charakterisiert haben.
Die LRK-Grammatik habe ich ja nur ganz kurz angedeutet.
Und das Wesentliche war, dass wir bis hierhin in dem Bereich einen
linearen Erkennungsaufwand haben.
Wenn wir rübergehen, haben wir hier noch mal immerhin was
Polynomielles und dann sind wir im exponentiellen Bereich.
Und was dann darüber hinaus passiert bei allgemeinen Grammatiken, das
ist hier noch mal offengelassen worden.
Wir haben andere Charakterisierungen gefunden.
Wir haben die Pumping-Lemmata uns überlegt zur Struktur der Sprache
oder zur Struktur der Wörter.
Wir wissen, dass wir eben bei, wenn wir also das Pumping-Lemma für die
regulären Sprachen uns anschauen, da hatten wir gesagt, da gibt es
immer eine Pumpstelle in solchen Wörtern.
Wenn wir also eine Sprache haben, bei der wir über solche Pumpstellen,
eine einfache Pumpstelle, immer Wörter erzeugen, die nicht in der
Sprache sind, dann ist es keine L3-Sprache.
Ähnlich war es mit dem Pumping-Lemma für kontextfreie Sprachen.
Da hatten wir aufgrund der Baumstruktur zwei Pumpstellen gefunden und
hatten gesehen, dass wir eben damit auch Sprachen charakterisieren
können, die nicht in L2 sind, sondern in L1 oder oben drüber.
Und wir haben die Automatencharakterisierung, also wir haben einiges
rausgefunden inzwischen.
Wir haben spezielle Sprachen immer gefunden, die genau die
Unterscheidung herstellen zwischen den verschiedenen Bereichen.
Auch in B hoch N die Sprache, die in L2 und nicht in L3 liegt.
Die Sprache der Palindrome, die halt nicht deterministisch erkannt
werden kann von Kellerautomaten, aber nicht deterministisch.
Wir hatten auch in B und C gesehen als Sprache, die in L1 ist, also
kontextsensitiv, aber eben nicht kontextfrei.
Und jetzt müssen wir sehen, was noch alles folgt.
Wir hatten einige wesentliche Fragen gestellt zu Anfang, in Bezug auf
die Ausdrucksfähigkeit.
Und da haben wir eigentlich die wesentlichen Antworten schon gefunden.
Nämlich, dass Typ 3 nicht reicht, dass Typ 2 reicht, aber dass wir
eben dort die deterministischen Sprachen nehmen müssen.
Die deterministischen kontextfreien Sprachen wegen des
Erkennungsaufwands.
Und alles, was wir ausdrücken müssen, die ganzen Strukturen, die
auftreten in Sprachen, sind in den Typ-2-Sprachen darstellbar, in den
kontextfreien Sprachen.
Ich habe nicht alle möglichen Features angeguckt oder durchdiskutiert.
Ich habe im Wesentlichen diese Klammerstrukturen genommen und habe
dann halt gezeigt, dass sobald man solche Dreifachzählungen hat, wie A
-Hochen, B-Hochen, C-Hochen, dass man dann nicht mehr mit
kontextfreien auskommt.
Das taucht aber so in den Programmiersprachen eigentlich nicht auf.
Also, das war klar, dass die kontextsensitiven Grammatiken auch nicht
infrage kommen wegen des exponentiellen Erkennungsaufwands.
Es wäre Wahnsinn, wenn man große Programme mit einem solchen Aufwand
überprüfen müsste auf ihre syntaktische Korrektheit.