Wir haben uns jetzt zu tun mit Kellerautomaten und
Kontextreihensprachen.
Was sind Kellerautomaten?
Hier kleiner Scherz zu Beginn.
Sonstige Möbel adäquatisch, Kellerautomat, gut erhaltener
Kellerautomat, günstig abzugeben oder gut erhaltener Kellerautomat,
Farbe hellblau, günstig abzugeben, ohne Altersbeschränkung, ideal für
die junge Familie.
Also, Sie werden sehen, wofür man Kellerautomaten verwenden kann.
Nicht unbedingt für die junge Familie, sondern für ein bisschen andere
Dinge.
Also, worum geht es bei Kellerautomaten?
Wir hatten gesehen, die Beschränkungen der ähnlichen Automaten liegen
darin, dass wir nur eine beschränkte Anzahl von Zuständen zur
Verfügung haben.
Das heißt, wir können nicht beliebig zählen, das war das Problem bei
unserer Sprache, auch in B hoch N, wir können nicht beliebig zählen,
wie viele Elemente da sind.
Also, wenn wir zum Beispiel A hoch 3, B hoch 3 eingegeben haben oder
eingeben, dann wissen wir nicht, wie viele A's kommen.
Wir wollen in der Lage sein, also für beliebiges N, A hoch N, B hoch N
zu akzeptieren.
Das geht nicht mit endlichen Automaten.
Wie kann man es dann hinkriegen?
Wir sagen jetzt, wir bauen einfach einen Speicher dazu.
Das andere ist also völlig dasselbe wie vorher.
Wir haben interne Zustände, wir haben eine Eingabebahn, das sich an
den Lesekopf vorbei bewegt, jedes Zeichen wird gelesen und dann haben
wir hier so etwas, was aussieht wie ein Loch im Keller.
Also, das heißt, wir haben hier irgend so einen Keller, hier nochmal
vergrößert angegeben und was wollen wir damit machen?
Wenn wir also ein Zeichen lesen, also zum Beispiel A hoch 3, B hoch 3,
dann wollen wir, ich schreibe das nochmal etwas anders hin, A, A, A,
B, B, B, so dieses Wort, wenn wir das lesen, dann wollen wir einfach
folgendes machen, so kann man diesen Keller verwenden, wir lesen das
erste A, wir wollen es merken, dass wir ein A gelesen haben.
Wir schreiben einfach das A hier unten rein, in den Keller.
Und dann lesen wir das nächste Zeichen auf dem Eingabeband und sehen,
dass es wieder ein A, legen das auch einfach rein in den Keller.
Dann haben wir wieder ein A.
Dann lesen wir noch ein A, sehen, aha, wir müssen, wir lesen ein A,
wir gehen hier runter und sehen dort ein, legen nochmal ein A dort
rein.
Dann kommt als nächstes Zeichen auf dem Eingabeband ein B.
Das ist eine neue Situation, da wird man dann den Zustand ändern, neue
Situation, wir lesen ein B.
Jetzt wissen wir, wenn das Wort akzeptiert werden soll, als ein Wort A
hoch N, B hoch N, dann müssen wir zählen, ob jetzt genauso viele Bs
kommen wie As.
Wenn nochmal ein A kommt, ist sowieso verkehrt, aber wenn also das
drin ist, dann müssen genauso viele Bs kommen wie vorher As.
Die einfachste Art und Weise ist, für dieses B, das wir hier sehen,
einfach zu sagen, naja, wir löschen einfach dieses A daraus, das
oberste.
Und dann gehen wir weiter, lesen das nächste B und wissen, wir haben
jetzt schon ein A gelöscht, wir sehen wieder ein B, wir löschen das
nächste A.
Und dann machen wir weiter, gleiche Situation, noch ein B, wir löschen
das nächste A und dann sind wir rechts daneben, sehen gar nichts mehr
und hätten einen leeren Keller.
Wir müssten das erkennen können, deswegen schreibt man hier in der
Regel noch ein sogenanntes Kellerstartzeichen rein und das ist das
Kellersymbol.
Wir sehen dann, wir haben hier ein Zeichen K0, ein
Anfangskellerzeichen, das uns praktisch nur erklärt, wir sind am Ende
des Kellers angekommen, da ist nichts mehr drin, was wir vorher
reingeschrieben haben.
Und wenn wir auch nichts mehr auf dem Band zu lesen haben, können wir
sagen, aha, wir sind fertig, wir können in den Endzustand gehen, wir
haben das Wort erkannt.
Also, was haben wir hier gemacht?
Wir sind einmal rauf gegangen, haben was reingeschrieben in den Keller
und sind dann sukzessive wieder runtergelaufen, haben das, was wir
reingeschrieben hatten, sukzessive angeschaut und wieder rausgelöscht.
Hier sieht man sofort ganz klar, auf die Art und Weise wird man in der
Lage sein, für beliebige Anzahl von A's festzustellen, ob genauso
viele B's hinterher kommen.
Wenn auf dem Weg dahin zwischendurch mal irgendwo jetzt ein A gekommen
wäre, nach einem B oder wir hier noch ein B hätten, dann hätten wir
einfach eine andere Situation, als die, die ich beschrieben habe.
Und alle anderen Situationen, als die, die ich beschrieben habe,
müssten zu einer Sackgasse führen, wir müssten das Wort ablehnen.
Also, das ist die Idee eines Kellerautomaten.
Ein Speicher, in den ich Informationen reinlegen kann.
Ich kann mir also etwas merken, was ich schon gesehen habe und kann
natürlich zusätzlich mir interne Zustände merken.
Ich kann mir also merken, dass ich erst dabei war, A's zu lesen und
danach habe ich eine neue Situation.
Ich muss überprüfen, ob jetzt genauso viele B's kommen.
Das ist ein anderer Zustand.
Und ein Endzustand ist auch noch etwas anderes, was ich anders mir
merken müsste.
Also, wir werden wohl drei Zustände brauchen für den Automaten und
dann müssen wir in der Lage sein, auf diesen Keller geeignet
zuzugreifen.
Also, das ist ein Kellerautomat.
Damit habe ich eigentlich einen Kellerautomat vollständig definiert.
Natürlich nicht.
Ich habe ihn nur verbal beschrieben, ein bisschen ein kleines Beispiel
gemacht.
Das müssen wir jetzt genauer uns angucken.
Außerdem etwas, was wir sehen, ist, dass wir hier ein sogenanntes LIFO
-Prinzip haben, ein Last-In-First-Out-Prinzip.
Das heißt, wir können immer auf das zugreifen, was wir von oben sehen
können.
Wenn sie in eine Grube etwas reinwerfen, können sie immer oben rauf
gucken und sehen, was als letztes reingegangen ist.
Dann können sie das rausnehmen oder noch mehr reinwerfen.
Aber sie sehen immer nur die oberste Information.
Also immer nur das, was oben drauf liegt und nichts, was unten drunter
ist.
Das ist das Kellerprinzip Last-In-First-Out.
Das, was sie als erstes reingeschrieben haben, wird als letztes wieder
angeguckt.
Klassisches Prinzip.
Das ist also das Benutzungsprinzip für einen Keller.
Wenn sie ein First-In-First-Out-Prinzip hätten, dann wäre es kein
Keller, sondern eine Warteschlange.
Dann würden sie einfach die Sachen durchreichen.
Das ist ein anderes Prinzip.
Hier haben wir Last-In-First-Out.
Nochmal hier dieses Bild.
Jetzt kommen wir zu noch ein paar Erklärungen.
Zustandsübergänge.
Was machen wir hier eigentlich?
In jeder Situation schauen wir uns an den aktuellen Zustand.
Also irgendein Zustand S, in dem das Ding gerade ist.
Wir schauen uns an die aktuelle Eingabe, hier oben unter dem, wo der
Schreiblesekopf gerade rauf guckt und wir schauen uns an das oberste
Kellerzeichen.
Das ist die Information, die wir brauchen, um zu entscheiden, was ist
der nächste Zustand und was wollen wir machen auf dem Kellerband?
Wollen wir dieses Zeichen hier löschen?
Wollen wir was reinschreiben?
Was machen wir eigentlich?
Diese Operationen auf dem Keller werden manchmal auch bezeichnet als
Operationen Push und Pop.
Wenn ich also eine Datenstruktur habe, bei der ich Push- und Pop
-Operationen machen kann, dann ist es ein Keller oder ein Push-Down
-Stack.
Manchmal nennt man ja Push-Down-Stack oder Push-Down-Autometer.
Sind auch Keller.
Das ist die englische Bezeichnung für Kellerautomat.
Da sagt man nicht Basement-Autometer, sondern man sagt dann, das ist
ein Push-Down-Autometer.
So, Push heißt, ich schreibe etwas rein.
Wenn ich also hier meinen Keller habe, hier ist der aktuelle Zustand,
dann wird dort V oben drauf geschrieben.
Nicht genau, sondern es wird folgendes gemacht.
Wir ersetzen das aktuelle Symbol K, das oberste Kellersymbol, durch V,
lassen das K aber stehen.
Wir löschen das K nicht weg, sondern schreiben das V obendrauf.
Das heißt, dass der vorherige oberste Kellersymbol bleibt drin und
obendrauf wird also jetzt hier das V geschrieben.
Und wenn wir sagen, wir wollen jetzt gerne das oberste Kellersymbol
rausholen, dann können wir Lambda schreiben.
Und wenn wir Lambda schreiben, also Push-Lambda sagen, dann heißt das,
es wird, wir sagen nicht Push-Lambda, Entschuldigung, sondern wir
sagen dann Pop.
Denn Push-Lambda würde bedeuten, wir würden das K, wir würden Lambda-K
schreiben, wir würden das K stehen lassen.
Bei Pop wird das oberste Kellersymbol gelöscht.
Da verschwindet das.
Insofern ist das einmal Schreiben von VK, also Ersetzen des obersten
Symbols K durch das Wort VK oder beim Pop ist einfach das Löschen
dieses Zeichen.
Das sind die beiden wesentlichen Operationen.
Sie können immer durch Datenstruktur plus Operationen einen bestimmten
Datentyp charakterisieren und das ist hier der Keller.
Schreibwesekopf ist also immer auf dem obersten Kellerzeichen und
formal können wir das jetzt wie folgt definieren.
Wir haben also die gleichen Komponenten zunächst noch wie beim
endlichen Automaten.
Wir haben ein Eingabealphabet, wir haben eine Zustandsmenge mit einem
Anfangszustand, das kennen Sie alles.
Hier kommen die neuen Dinge, ein Kelleralphabet.
Das müssen nicht notwendigerweise die gleichen Zeichen sein, die wir
auf dem Eingabewand stehen haben.
Es könnte irgendwas anderes sein.
Und wir brauchen ein unterstes Kellersymbol, das uns einfach erlaubt,
festzustellen, wann wir den Keller vollständig geleert haben.
Ja, also zu Anfang haben wir dieses Zeichen K0 im Keller stehen und
sobald wir das Zeichen K0 sehen, wissen wir, der Keller ist leer.
Dazu brauchen wir eine endliche Menge von Endzuständen, also nicht
leere endliche Menge von Endzuständen.
Auch das kennen Sie aus den endlichen Automaten.
Und die Überführungsfunktion sieht jetzt ein bisschen komplizierter
aus, nicht mehr einfach nur von Delta von S kreuz E nach S, sondern
jetzt haben wir eben diese drei Komponenten, die wir anschauen müssen.
Den Zustand, das Zeichen über dem Eingabekopf hier, dem
Schreiblesekopf und das Zeichen auf dem Keller.
Und Sie sehen jetzt hier noch etwas, dass hier noch das Lambda dabei
steht, darauf gehe ich gleich ein, warum das da steht.
Und das, was wir erzeugen wollen oder was wir wissen wollen, ist, wie
gehe ich über in eine neue Konfiguration im Prinzip, was mache ich auf
dem Kellerautomaten?
Ich erzeuge einen neuen Zustand und schreibe irgendetwas in den Keller
hinein.
Das war genau das, was wir vorher gesagt hatten.
So, wir kommen gleich auf dieses, warum wir hier oben das Lambda
brauchen.
Wir haben ja eine gewisse Bedingung, insbesondere steht hier oben ja
eine partielle Überführungsfunktion.
Das heißt, diese Funktion muss nicht notwendigerweise vollständig
definiert sein.
Ich habe also nicht für jeden Zustand und jedes Eingabesymbol einen
Übergang.
Es kann sein, dass einige fehlen.
Da muss ich mir überlegen, ist das überhaupt realistisch, ist das
sinnvoll?
Es soll ein deterministischer Kellerautomat sein.
Und ich habe hier auch die Möglichkeit, für das leere Wort unter dem
Schreiblesekopf einen Übergang zu machen.
Was heißt denn, das leere Wort wird gelesen?
Das heißt, ich lese gar nicht.
Ich entscheide mich, das Zeichen, das hier gerade steht, nicht zu
lesen.
Also wenn Delta von S Lambda K definiert wäre, dann bedeutet das, ich
darf in einem Zustand S und im obersten Kellerzeichen K etwas tun,
ohne das Zeichen unter dem Schreiblesekopf zu berücksichtigen.
Das wird ausgedrückt dadurch, dass man sagt, ich habe durchaus
Übergänge für Zustand und oberstes Kellerzeichen mit der Eingabe
Lambda, also leeres Wort.
Ich darf die Eingabe ignorieren in gewissen Zuständen in Kombination
mit gewissen obersten Kellerzeichen.
Und was hier steht in der Bedingung ist, dass wann immer Delta von SEK
definiert ist, wenn ich also in einem Zustand für eine gewisse Eingabe
E unter dem Schreiblesekopf und ein oberstes Kellersymbol einen
Übergang definiert habe, dann darf ich dieses Eingabezeichen E nicht
einfach ignorieren.
Dann muss Delta von S Lambda K undefiniert sein.
Ansonsten, wenn das definiert wäre, hätte ich ja die Auswahl
dazwischen, das Zeichen E zu berücksichtigen oder nicht.
Und dann hätte ich einen Nicht-Determinismus in den Übergängen.
Diesen Nicht-Determinismus möchte ich nicht haben.
Das soll ein deterministischer Kellerautomat sein.
Es soll also in jedem, jeder Situation eindeutig klar sein, was als
nächstes gemacht werden soll.
Also in einem Zustand mit einer gewissen Eingabe und einem obersten
Kellerzeichen muss klar sein, was passiert.
Entweder ist der Übergang definiert direkt mit neuem Zustand und
Aktion auf dem Keller oder ich habe den nicht definiert für dieses
Zeichen, habe aber einen Übergang mit dem leeren Wort und dann kann
ich also ein bisschen intern was tun.
Da kann ich also hier im Prinzip eine Weile, vielleicht sogar eine
Weile, mir einfach intern hier ein paar Sachen überlegen, auf dem
Keller arbeiten und dann gucke ich irgendwann wieder auf dem
Eingabeband nach, entsprechend der Art, wie hier meine
Übergangsfunktion definiert ist.
Also, man braucht diese Bedingung, damit ich immer ein
deterministisches Verhalten habe für einen deterministischen
Kellerautomat.
Ich muss aber auch es ermöglichen, dass ich intern etwas tun kann,
ohne etwas auf dem Band zu lesen und dafür brauche ich also diese
Übergänge mit dem leeren Wort, wie gesagt, nur dann, also wenn das
Delta S Lambda K definiert ist, dann ist natürlich das Delta S E K
nicht definiert, das ist die einfache, das ist die gleiche Aussage,
die hier steht, nur andersherum geschrieben.
Kontraposition davon ist ja gerade damit auch klar.
Also, falls das definiert ist, ignoriert der Kellerautomat für Zustand
S in Kellerzeichen K das Eingabeband und verändert den Kellerzustand.
Das hatte ich Ihnen jetzt schon deutlich gesagt, werden wir gleich
Beispiele sehen, wie man das einsetzt.
Und ohne die Bedingung wäre der Automat nicht deterministisch, auch
das ist klar.
So ein Kellerautomat ist also entsprechend der Notation von vorher,
ein Automat ohne Ausgabe, der hat zwar einen Endzustand, kann also,
wir werden damit Aussagen hinbekommen über das Akzeptieren von
Sprachen, aber das ist auch alles.
Wie kann der also wirklich arbeiten, das habe ich jetzt schon deutlich
gemacht.
Zu Beginn ist wie üblich immer die Anfangssituation da, die wir
brauchen.
Der Automat ist auf dem linkesten Zeichen im Eingabeband, schaut sich
also das Wort W an, über das wir jetzt wissen wollen, ob es akzeptiert
wird oder nicht, beziehungsweise ob wir beim Start im Anfangszustand,
bei Eingabe dieses Wortes W, irgendwann durch eine Folge von
Zustandsübergängen und Arbeiten auf dem Keller, irgendwann in eine
Situation kommen, bei der wir sagen können, jetzt können wir
entscheiden, ob wir das Wort akzeptieren oder nicht.
Also wir müssen dann in irgendeinen Endzustand kommen.
Also, was macht der, wenn das nicht definiert ist, das Delta, weder
für SEK noch für SLK, dann hält der Automat einfach an.
Der weiß ja nicht, was er tun soll.
Also das war eine parzelle Funktion.
Es könnte sein, dass für bestimmte Situationen einfach der Automat
nicht definiert ist, dann hält er an und wir sind fertig und wissen,
das Wort wird nicht akzeptiert.
Ansonsten, wenn das Delta für SEK definiert ist, dann ist der neue
Zustand S' und es wird das K ersetzt durch V.
Also das linkeste Zeichen von V wird das neue oberste Kellerzeichen
und der Lesekorb wird um eine Position nach rechts bewegt.
Ich hatte vorher gesagt, bei dem Push wird das V obendrauf geschrieben
und das K bleibt stehen.
Hier sage ich, das K wird ersetzt durch das V.
Ich habe das hier etwas anders implementiert, als ich das vorher
gesagt habe.
Das ist im Prinzip das Äquivalent.
Also die Push-Operation geht da ein bisschen anders vor.
Ich sage, wir machen das so, dass wir das K ersetzen durch das V.
Und das linkeste Zeichen von diesem V ist anschließend das oberste
Kellerzeichen.
Also wenn wir auf dem Keller vorher hier drauf hatten irgendwas mit K
und wir schreiben jetzt A, B dort rein, dann haben wir anschließend
hier das, was da vorher war, immer noch stehen und oben drüber steht
jetzt B und A.
Das heißt, das linkeste Zeichen dieses Zeichen A ist das neue oberste
Kellersymbol.
Das Zeichen K ist verschwunden und das, was unten drunter war, ist
erhalten geblieben.
So, das ist also die Art, wie wir hier diesen Zustandsübergang
definieren.
So arbeitet der Kellerautomat, wenn er ein Zeichen liest.
Wenn er kein Zeichen liest, wenn also Delta S Lambda K definiert ist,
dann ist so auf dem Keller die Operation genauso, aber die Position
des Lesekopfes bleibt unverändert.
Das Zeichen ist noch nicht verarbeitet worden.
Das also zu dieser Definition der Arbeitsweise des Automaten und wir
können dann sagen, dass ein Wort akzeptiert wird, wenn der Lesekopf
irgendwann rechts neben dem Wort steht, das wir lesen wollten, haben
also alle Zeichen tatsächlich angeguckt und darauf reagiert und der
Automat soll im Endzustand sein.
In einem Endzustand.
Es gibt in der Literatur auch andere Definitionen für das
Akzeptierungsverhalten von Kellerautomaten.
Ein Akzeptierungsverhalten mit leerem Keller brauchen wir hier nicht.
Wir machen das mit dieser Definition.
Die beiden sind äquivalent.
Diese Überlegungen will ich Ihnen ersparen.
Es reicht eine Art anzugeben, das ist hier die naheliegendste
Erweiterung des endlichen Automaten.
Deswegen machen wir das hier so.
Und dann haben wir, wir haben endlichen Automaten uns ja auch
angeschaut.
Wir brauchen im Prinzip Konfigurationen.
Warum brauchen wir Konfigurationen?
Um in jeder Situation die Informationen zur Verfügung zu haben, die es
uns erlaubt, das weitere Verhalten des Automaten vollständig zu
beschreiben.
Um das weitere Verhalten des Automaten vollständig zu beschreiben,
brauchen wir den Zustand des Automaten.
Wir brauchen das, was noch auf dem Band bearbeitet werden muss.
Und wir müssen wissen, ja nicht nur das, was hier oben steht, nicht
nur das oberste Kellerzeichen, sondern für die Konfiguration, um sagen
zu können, was wird im weiteren Verlauf der Abarbeitung unseres Wortes
noch passieren, brauchen wir den gesamten Kellerinhalt.
Den müssen wir uns in der Konfiguration merken.
Also die Konfiguration besteht aus dem Zustand, dem zu verarbeitenden
Restwort und dem aktuellen Kellerinhalt, der dort reingeschrieben
wurde.
Mit dieser Information können wir unter Kenntnis der Übergangsfunktion
des Automaten genau sagen, was der noch im weiteren Verlauf machen
wird, ob er tatsächlich das ursprünglich eingegebene Wort akzeptiert
oder nicht.
Wir haben dann für Konfigurationen auch Übergänge.
Wir können also von einer Konfiguration in eine andere übergehen und
dann müssen wir jetzt unterscheiden, die beiden Situationen, ob wir
einen Übergang machen mit Lesen und Verarbeiten des einen Zeichens
oder ob wir einen Übergang machen mit leerem Wort.
Wenn wir einen Übergang machen mit Lesen des Zeichens, ist es klar,
wir haben erst dieses Zeichen E dort stehen, rechts daneben noch
irgendwas anderes, ein Wort W und anschließend ist das Zeichen weg,
weil wir das bereits gelesen haben bzw.
der Schreiblesekopf ist eins weitergegangen und wir haben einen neuen
Zustand, S-Strich, der hier in der Definition von Delta angegeben ist
und es ist das K, das oberste Kellerzeichen K, ersetzt worden durch V
-Strich.
Das heißt, wir haben anschließend V-Strich-V auf unserem Keller
stehen.
Also immer das erste Zeichen des Wortes, was dort steht, ist das
oberste Kellerzeichen, also das linkeste Zeichen dieses Wortes.
Das war erst K und ist anschließend das linkeste Zeichen von V-Strich.
Und wenn wir nichts lesen, nur das leere Wort, berücksichtigen, also
das Zeichen ignorieren, weil wir eine solche Definition haben für den
Übergang, dann bleibt halt das Wort auf dem Band unverändert stehen,
aber der Keller ändert sich und der Zustand ändert sich.
Naheliegend, das so zu machen.
Das sind die Konfigurationen und die Konfigurationsübergänge.
Wir können das Ganze wieder reflexiv-transitiv erweitern, können also
beliebige Folgen von Übergängen machen und haben dann also diese
Übergangsrelation mit dem Stern dran, beliebig häufige Übergänge.
Und wir werden dann sagen können, dass wir ein Wort akzeptieren, wenn
wir von der Startkonfiguration des Automaten, bei der wir im
Anfangszustand S0 starten, das Wort W auf dem Band stehen haben und im
Keller das Zeichen K0, beziehungsweise nur das Zeichen K0 haben, das
heißt im Prinzip einen leeren Keller.
Wir haben noch nichts reingeschrieben.
Wenn wir dann durch eine Folge von Konfigurationsübergängen auf eine
Konfiguration kommen, bei der wir in einem Endzustand sind, S aus F,
auf dem Band nichts mehr steht, was wir verarbeiten müssen und
irgendwas im Keller steht, also V ist hier völlig beliebig, kann
irgendwas stehen.
Das Wesentliche ist, wir sind in einem Endzustand und auf dem Band
steht nichts mehr, was wir noch verarbeiten müssten.
Dann ist das Wort akzeptiert.
Das sind also diese Definitionen und jetzt müssen wir sehen, was man
daraus für Sprachen bekommt.
Es ist klar, dass es dann die Menge aller Wörter, die akzeptiert
werden.
Nun müssen wir diese Sprachen charakterisieren.
Und es wird Zeit, dass ich Ihnen ein Beispiel gebe, wo wir uns das
anschauen, wie man einen solchen Automaten definiert.
Und das einfache Beispiel ist natürlich das, was ich vorher schon mal
angedeutet habe.
Wir hatten ja eine Sprache, die uns zunächst mal interessiert hat.
Diese Sprache A auch N, B auch N.
Und lassen Sie mich einfach hier zur Einfachheit halber A, A, B, B
nehmen.
Was würden wir mit dem Wort machen?
Wir fangen an, wir werden sukzessive den Automaten definieren.
Wir fangen an in einer Konfiguration.
Nein, nicht eine Konfiguration, das ist keine Konfiguration, das sind
Übergänge.
Das soll die Definition von Delta werden.
Ich habe hier die Situation S0, das ist der Anfangszustand, A ist das
Zeichen, das ich lese und ich habe im Keller als oberstes Zeichen das
K0.
In der Situation, wenn wir sagen, okay, wir können im Prinzip in dem
Anfangszustand bleiben und wir schreiben das A auf diesen Keller rauf.
Das heißt, wir ersetzen K0 durch AK0.
Ja, wir wollen das K0 nicht löschen, dann könnten wir später nicht
erkennen, dass der Keller leer ist, sondern wir müssen das K0 da
stehen bleiben lassen.
Das heißt, wir hätten jetzt genau die Situation, dass wir hier unten
K0 stehen haben und schreiben jetzt das A oben drüber.
Danach könnte es sein, dass wir immer noch im Zustand S0 sind, wir
lesen ein A, im Keller ist das oberste Zeichen ein A.
In der Situation sagen wir, bleiben wir in dem Zustand S0 und ersetzen
dieses eine A durch AA.
Ich ersetze das eine A durch AA.
Und danach könnte es sein, dass wieder ein A kommt, könnte aber auch
sein, dass ein B kommt, was hier in diesem Beispiel auch der Fall ist.
Wir sind im Zustand S0, lesen ein B und haben auf dem Keller oben ein
A stehen.
Dann gehen wir in einen neuen Zustand über S1.
Wir hatten vorher also hier S0, jetzt gehen wir über auf S1 und
löschen das Zeichen aus dem Keller.
Das heißt, wir löschen dieses A, ich streiche es einfach durch.
Eigentlich müsste es verschwinden, aber durchgestrichen soll heißen,
es ist nicht mehr da.
Jetzt haben wir also das gelöscht, das wäre der Übergang.
Jetzt müssen wir uns natürlich merken, dass wir dabei sind zu löschen.
Wenn jetzt noch ein B kommt und es ist immer noch ein A zu sehen,
machen wir das gleiche, löschen also auch dieses A.
Und wenn jetzt die andere Situation kommt, die hier ja auch
tatsächlich in dem Beispiel passieren würde, wir sind rechts daneben,
wir lesen gar nichts mehr.
Beziehungsweise wir sagen, wenn wir im Zustand S1 sind und wir haben
auf dem Keller das oberste Kellerzeichen, das K0, dann dürfen wir die
Eingabe ignorieren.
Eingabe ignorieren heißt, wir haben einen Übergang mit Lambda.
Wenn wir also im Zustand S1 den Keller völlig geleert haben, dann
ignorieren wir die Eingabe und gehen in den Zustand S2 und lassen das
Kellerzeichen dort stehen.
S2 soll ein Endzustand sein.
Und damit sind wir fertig.
Damit hätten wir das Wort A²B² sicherlich erfolgreich akzeptiert oder
bearbeitet.
Sie können sich sofort überlegen, dass man alle solchen Wörter auch in
B hoch N auf die Art und Weise akzeptieren könnte, indem man eben
öfter mal diese Zustandsübergänge macht, also im Prinzip vor allen
Dingen diesen Zustandsübergang und danach halt einmal den Übergang von
S0 auf S1 und dann sehr häufig diese Zustandsübergänge, wo man die A´s
löscht, weil man B´s gelesen hat und am Ende noch einmal den Übergang
von S1 mit Kellerzeichen K0 auf S2 und K0.
So, wenn man jetzt ein anderes Wort auf dem Band stehen hätte, könnte
man nicht in den Endzustand kommen.
Das müsste man zeigen, kann man sich leicht überlegen, wenn wir also
nach einem B ein A lesen würden, dafür ist die Funktion gar nicht
definiert, der Übergang.
Wir haben keine Situation für S1A und irgendwas auf dem Keller stehen.
Das heißt, das wäre ein nicht vorhandener Übergang, der Automat würde
stehen bleiben.
Wenn wir noch nicht fertig wären, wenn hier noch ein B stehen würde an
der Stelle, hätten wir trotzdem die Situation, dass wir im Zustand S1
sind und das Zeichen K0 sehen, würden also diesen Übergang machen,
würden auf S2 kommen und wären in einem Endzustand, für den wir keinen
einzigen Übergang definiert haben.
Das heißt, von S2 aus können wir nicht weitermachen, der Automat hält
an, bricht ab, hat auf dem Eingabeband immer noch etwas stehen,
nämlich noch ein B, ist also nicht fertig, kann das Wort nicht
akzeptieren.
Sie können sich alle Situationen durchspielen, das ist hier also ein
sehr einfacher Automat, der einfach den Keller nutzt, um zu zählen,
wie viele A's da sind.
Um dann festzustellen, ob auch genauso viele B's dann vorkommen
anschließend.
Also insofern kann man hier etwas machen, hier ist nochmal das Gleiche
angegeben für A hoch 3, B hoch 3, das glaube ich kann ich sehr schnell
überspringen, das geht wirklich ganz einfach, das sind hier die
Übergänge.
Wir lesen die drei A's, wir lesen die drei B's, haben anschließend S1,
K0 und können dann im letzten Schritt übergehen auf S2, sind im
Endzustand und sind fertig.
Das ist also genau das, was ich Ihnen gerade eben so nebenbei
dargestellt habe.
Also das ist ein einfacher Kellerautomat.
Übergangsfunktion ist hier definiert, durch diese Tabelle, die ich
Ihnen hier angegeben habe und wir brauchen also nicht mehr als diese
fünf verschiedenen Übergänge, damit sind wir fertig.
So, ganz allgemein ist es natürlich so, dass der Automat alle Worte
der Form A hoch N, B hoch N akzeptiert.
Warum sind wir so an A hoch N, B hoch N interessiert?
Ich hatte Ihnen schon mal gesagt, das geht um Klammerstrukturen.
Wir werden also gleich darauf nochmal eingehen.
Ich kann also alle diese Wörter akzeptieren, alle anderen Wörter
werden nicht zum Akzeptieren führen, damit haben wir diese Sprache
akzeptiert.
Wir können wissen also jetzt, dieser Automat kann mehr als die
endlichen Automaten.
Andererseits weiß ich, dass jeder das, was ein endlicher Automat kann,
ja, was ein endlicher Automat machen kann, das kann ich natürlich auch
mit einem Kellerautomat machen.
Warum?
Weil ja ein Kellerautomat insbesondere alle Fähigkeiten eines
endlichen Automaten hat.
Der hat eine Zustandstabelle, der hat Eingaben, hat einen
Schreiblesekopf.
Wenn ich also den Keller einfach ignoriere, habe ich ja genau das
Verhalten eines endlichen Automaten.
Also ich kann jeden endlichen Automaten als Kellerautomaten auffassen,
der das Band ignoriert, dieses Kellerband.
Und damit habe ich sofort die Aussage dieses Satzes.
Hier möchte jemand eine Frage stellen, die sich hier irgendwie wieder
borstig zeigt.
Darf man hoch 3 schreiben bei der Eingabe der Übergänge?
Bei der Eingabe der Übergänge?
Schauen wir mal, was Sie wohl gemeint haben.
Hier auf der vorigen Folie noch eine Frage.
Was ist das denn?
Ich habe die doch schon beantwortet.
Jetzt ist sie weg.
Warum darf man das schreiben?
Das ist ja einfach eine abkürzende Schreibweise.
Also hier steht jetzt B hoch N.
Wenn ich in B hoch N explizit hinschreiben soll, habe ich ein Problem.
Dann muss ich erst mal sagen, was N ist.
Ich will es aber allgemein hinschreiben.
Auf der Folie davor, also auf der Folie 8, da war das ja...
Das will ich jetzt nicht.
Was ist hier heute los mit meinem Rechner?
Also, wenn ich hier auf die Folie 8 gehe, da stand dieses B hoch 3.
Das sind hier Konfigurationsübergänge.
Bei der Konfiguration steht hier jeweils ein Wort.
Also, da steht erst A hoch 3, B hoch 3, dann steht hier A hoch 2, B
hoch 3 und so weiter.
Das ist einfach eine abkürzende Schreibweise dafür, dass dort steht,
erst A, A, A, B, B, B, dann steht da A, A, B, B, B, dann steht da A,
B, B, B, B, B, B, B, genau.
Dann steht hier B, B, B, dann steht hier B, B, dann steht da B, nichts
mehr.
Also, das ist eine einfache abkürzende Schreibweise.
Natürlich steht auf dem Band nicht B hoch 3 in Zeichen hingeschrieben.
Aber ich glaube, das ist soweit deutlich.
Gehen wir nochmal weiter hier zu diesem Satz, den habe ich Ihnen
gerade eben erläutert.
Der Beweis ist trivial.
Also sind die endlichen Sprachen, die von endlichen Automaten
akzeptiert werden, alle auch Sprachen, die von Kellerautomaten
akzeptiert werden können.
Wir haben also eine Inklusion dieser Menge und das auch ein echtes
Enthalten sein, weil halt die Sprache A hoch N, B hoch N keine Sprache
war, die von endlichen Automaten akzeptiert werden kann.
Also ist sie insbesondere eine Sprache, die halt außerhalb liegt.
Und jetzt schauen wir uns nochmal an, dass wir endlich mal eine
vernünftige Darstellung haben der Konstrukte, die uns eigentlich
interessieren.
Ich hatte immer gesagt, A hoch N, B hoch N entspricht den
Schachtelungen von Klammern.
So ganz stimmt das ja nicht.
Was ist denn eine wirkliche Schachtelung von Klammern?
Also ein sogenannter wohlgeformter Klammerausdruck.
Was ist denn das?
Also das hier ist ja einfach.
Das ist eine wohlgeformte Klammer.
Ja, das hier ist auch einfach.
Wohlgeformte Klammer.
Aber wenn ich jetzt daneben nochmal sowas schreibe, das ist doch auch
eine wohlgeformte Klammer.
Aber wenn ich sowas hinschreibe, das sicherlich nicht wohlgeformt,
dann mache ich zuerst eine schließende Klammer und dann eine öffnende
Klammer.
Das darf man natürlich nicht.
Man kann nur etwas schließen, wenn es vorher aufgemacht wurde.
Und deswegen ist hier die erste Bedingung da.
Die Anzahl der öffnenden Klammern in W ist gleich der Anzahl der
schließenden Klammern in W.
Das ist eine Bedingung.
Jede Klammer, die geöffnet wird, muss auch irgendwann geschlossen
werden.
Das stimmt auch hier, dass wir für das Wort hier auch erfüllt.
Aber die zweite Bedingung gilt dann nicht mehr.
Für jede Zerlegung W gleich UV.
Das ist unser Wort W.
Jetzt mache ich eine Zerlegung in U und V.
Ein Anfangsstück schaue ich mir an und ich zähle einfach die Klammern,
die öffnenden und schließenden Klammern in diesem Anfangsstück.
Dann darf die Anzahl der schließenden Klammern in diesem Anfangsstück
nicht größer sein als die Anzahl der öffnenden Klammern.
Das ist bei diesem Beispiel nicht der Fall.
Da habe ich eine schließende Klammer, eine mehr als öffnende Klammern
und danach eine schließende Klammer.
Quatsch, danach eine öffnende Klammer.
Also erst eine schließende, dann eine öffnende.
Das wäre ein Verstoß gegen diese Bedingung.
Mit diesen beiden Bedingungen kann ich wohlgeformte Klammerausdrücke
definieren.
Das sind also beliebige Klammerschachtelungen, wie wir sie zum
Beispiel in arithmetischen Ausdrücken haben.
Also wenn Sie hier irgendetwas hinschreiben.
A plus B mal 17 plus 23 und so weiter mal A plus C.
So was wäre ein Klammerausdruck, wie er auftreten kann in
arithmetischen Ausdrücken.
Solche Ausdrücke haben Sie in Programmiersprachen.
Selbstverständlich tauchen die dort auf.
Und damit müssen Sie solche Ausdrücke vernünftig bearbeiten können und
vernünftig bearbeiten entsprechend dieser Klammerstruktur.
Und wir können das halt dann mit solchen wohlgeformten
Klammerausdrücken beschreiben.
Das ist etwas komplexer als die einfache Sprache A hoch N, B hoch N.
Aber hier sind nochmal Beispiele angegeben für wohlgeformte
Klammerausdrücke und welche, die keine sind.
Also dass das hier welche sind, sieht man sofort.
Hier haben wir Folgen von solchen Klammern nacheinander.
Hier ist immer für jedes Anfangsstück die Anzahl der schließenden
Klammern kleiner gleich der Anzahl der öffnenden Klammern.
Und in diesem Beispiel gilt das nicht.
Da haben wir eine öffnende, eine schließende, dann kommt eine
schließende, dann eine öffnende.
Das ist also verkehrt.
Die schließende kommt hier vor.
Und wenn wir uns dieses Anfangsstück anschauen, hätten wir also zwei
schließende und eine öffnende.
Das ist ein Verstoß gegen Regel 2.
So.
Und jetzt müssen wir uns überlegen, wie können wir solche etwas
allgemeineren Sprachen akzeptieren.
Zum Beispiel die Sprache aller wohlgeformten Klammerausdrücke.
Dann müssen wir entsprechend den Automaten konstruieren.
Schauen wir uns das an.
Das ist eine ganz einfache Abwandlung der vorherigen Angabe.
Wenn wir ein Klammerauf haben, dann merken wir uns das.
Wir merken uns, dass wir ein Klammerauf gesehen haben, gehen in einen
neuen Zustand und ersetzen das K0 durch K0.
Wir hätten da auch AK0 schreiben können.
Ist völlig egal.
Ich habe jetzt das gleiche Alphabet genommen.
Also nicht ganz das gleiche.
Ich habe hier K0 und Klammerauf.
Ich brauche die Klammerzu nicht auf dem Keller.
Ich hätte auch irgendein anderes Zeichen nehmen können.
Muss man nur merken, ich habe eine öffnende Klammer gelesen.
Wenn ich in diesem Zustand S1 bin und eine öffnende Klammer lese und
schon eine öffnende Klammer auf dem Keller habe, dann schreibe ich die
Klammer auch dort mit rauf.
Ich ersetze Klammerauf durch Klammerauf, Klammerauf.
Entspricht genau dem, was wir vorher gemacht haben mit A auch N, B
auch N.
Jetzt sind wir im Zustand S1 und haben eine schließende Klammer.
Auf dem Keller ist eine öffnende Klammer.
Dann bleiben wir hier in diesem Zustand.
Hier bleiben wir in dem Zustand.
Bei A auch N, B auch N hatten wir eine neue Situation angeschaut.
Und löschen einfach diese öffnende Klammer, weil wir eine schließende
gesehen haben.
Das heißt, eine öffnende Klammer wird rausgelöscht.
Und wenn danach wieder eine öffnende Klammer kommt, eine öffnende
unter das Kanon da, ne, das kann nicht sein, öffnende S1.
Wenn also alles rausgelöscht war, wenn wir mit dieser Operation hier
eine öffnende Klammer gelöscht haben und anschließend sind wir im
Zustand S1 und haben also hier in unserem Keller wieder das K0
erreicht.
Haben also alles, was hier oben drüber war, bereits gelöscht.
Dann gehen wir in den Zustand S0 und lassen den Keller wie er war.
Das heißt, wir ignorieren das, was auf dem Band steht und gehen zurück
nach S0 und machen dann weiter.
So, das war anders bei der A auch N, B auch N.
Da hatten wir einen Übergang gemacht, wenn wir das erste B gelesen
haben und hatten dann, wenn wir das erste Mal auf den leeren Keller
kamen, da hatten wir gesagt, dann gehen wir in einen Endzustand über.
Sie sehen aber, der Endzustand ist hier gleichzeitig der
Anfangszustand.
Also etwas anders.
Warum?
Es kann ja sein, dass wir zum Beispiel sowas gelesen haben und jetzt
kommt nochmal eine solche Folge.
Wenn wir nur das Wort betrachten, das hätten wir bereits akzeptieren
können.
Ein wohlgeformter Klammerausdruck.
Dahinter kommt noch ein wohlgeformter Klammerausdruck und beides
zusammen ist auch ein wohlgeformter Klammerausdruck.
Das heißt, ich habe hier im Prinzip die gleiche Situation wie vorher.
Ich habe hier ein ausgeglichenes Konto von öffnenden und schließenden
Klammern.
Und sobald ich ein ausgeglichenes Konto habe, wenn also die Anzahl der
öffnenden gleich der Anzahl der schließenden Klammern gewesen ist,
habe ich die gleiche Situation wie zu Beginn.
Dann gehe ich wieder in den Zustand S0 und wenn jetzt im Zustand S0
eine schließende Klammer kommen würde, wüsste ich nicht, was ich tun
soll, weil dafür kein Übergang definiert ist.
Das heißt, wenn dieses Zählen von öffnenden und schließenden Klammern
dazu führt, dass ich auf einmal eine schließende Klammer zu viel habe,
da habe ich dafür gar keinen Übergang.
Der Automat bleibt stehen, hat nicht alle Zeichen bearbeitet und das
Wort wird abgelehnt.
Also dieser Automat ist sehr einfach und wir können eben damit jetzt
wohlgeformte Klammerausdrücke tatsächlich erzeugen.
Beziehungsweise nicht erzeugen, sondern wir können die analysieren und
feststellen, das ist ein wohlgeformter Klammerausdruck und können
sagen, dann wird er akzeptiert oder wenn er nicht wohlgeformt ist,
wird er abgelehnt.
Wenn wir also hier diese Folge von Zeichen haben, zweimal Klammer auf
Klammer zu hintereinander, dann sieht man eben hier gerade die
Übergänge.
Wir würden also das erste öffnende lesen, würden das in den Keller
schreiben, würden dann die schließende Klammer lesen, würden das
Zeichen hier, oder würden Lambda schreiben, das heißt wir würden
dieses Zeichen dort rauslöschen und hätten anschließend diese
Situation, dass wir in der Konfiguration, wo sind wir denn hier, wir
haben das gelesen, wir sind in dieser Situation, sind im Zustand,
genau, sind im Zustand, wir haben diese beiden Zeichen auf dem Band
noch stehen, sind in der Situation S1, K0, machen einen Lambda
-Übergang, gehen auf S0, das bleibt noch auf dem Band stehen, haben
jetzt also hier wieder den Zustand S0, K0 und eine öffnende Klammer,
gehen wieder nach S1 und so weiter und haben dann, nachdem wir dieses
schließende Zeichen gelesen haben, haben wir das Öffnende wieder
gelöscht, haben auf dem Band nichts mehr stehen und sind in der
Situation, dass wir S1 und K0 sehen, gehen nach S0, haben auf dem Band
nichts mehr stehen und sind damit fertig.
Also das ist eine einfache Art, dieses Wort zu akzeptieren, wo wir
zweimal Klammer auf Klammer zustehen haben.
Ich hoffe, dass das so verständlich gewesen ist, es ist nicht wirklich
schwierig.
Jetzt kommt eine weitere Sprache, auch eine typische Sprache, die
etwas mit Klammerstrukturen zu tun hat, aber ein bisschen anders.
Hier wollen wir eine Sprache akzeptieren über drei Zeichen, 0, 1 und
C.
Und was wir akzeptieren wollen, ist die Menge aller Wörter, V, C, V',
wobei das V' die Umkehrung von V ist.
Also, wenn wir hier stehen haben, 0, 1, 1, dann kann dahinter ein C
kommen und dann 1, 1, 0, das wäre genau so ein Wort.
Hier steht V, 0, 1, 1, da steht V', die Spiegelung des Wortes, genau
andersrum hingeschrieben.
Und in der Mitte steht das C.
Diese Sprache zu akzeptieren ist auch ein Kinderspiel mit einem
Kellerautomaten, das können Sie sich sofort überlegen.
0, 1, 1, wenn ich hier meinen Keller hätte, das mache ich natürlich
so, hier unten habe ich meinen K0 stehen, wie immer.
Ich lese 0, 1, 0, 1, 1 und anschließend, wenn ich dann das C lese,
schalte ich um.
Jetzt muss ich vergleichen mit dem, was im Keller steht.
Und wenn dann wieder 1, 1, 0 gelesen wurde, dann habe ich genau das
wieder rausgelöscht, was ich vorher reingeschrieben habe und ich sehe
als oberstes Kellerzeichen das K0, bin im Endzustand und bin fertig.
Das ist die ganz einfache Idee.
Das ist ja gerade das Last-In-First-Out-Prinzip, was hier steht.
Und ich habe einen Umschaltzeitpunkt C.
Also Eingabe VCU, ich lese das Zeichen, lese also V ein, Zeichen für
Zeichen, speichere das ab, sobald ich das C sehe, gehe ich in neuen
Zustand über und vergleiche jeweils das oberste Kellerzeichen mit dem
aktuellen Zeichen auf dem Band.
Wenn das gleich ist, lösche ich das Kellerzeichen aus dem Keller raus,
bei Ungleichheit bin ich fertig, bearbeite oder mache nicht weiter und
das Wort wird nicht akzeptiert.
Das ist also ganz einfach und das ist hier formal hingeschrieben.
Wenn ich also ein Zeichen sehe, Bedienungszustand ist 0, lese ein
Zeichen, im Anfangszustand, Anfangssituation schreibe ich das E
obendrauf.
Wenn ich irgendein Zeichen sehe und ein Zeichen K obendrauf habe,
schreibe ich das E einfach noch wieder da oben drauf, setze also K
durch EK und wenn ich ein C sehe, dieses C, was mir das Umschalten
andeutet, dann schalte ich um, ich gehe in neuen Zustand S1 und
verändere den Keller nicht und anschließend möchte ich gerne
Situationen haben, bei denen auf dem Band genau das gleiche steht, wie
auf dem Keller, das heißt, wann immer ich das gleiche Zeichen als
oberstes Kellerzeichen habe, wie auf dem Band, lösche ich das raus und
bleibe in diesem Zustand und wenn ich auf diese Art und Weise bis zum
Startkeller -Symbol K0 gekommen bin, dann weiß ich, ich habe genau
alles, was ich vorher reingeschrieben habe, wieder rausgelöscht.
Es muss genau in der umgekehrten Reihenfolge wieder auf dem
Eingabeband gestanden haben.
Ich gehe in den Endzustand S2 und bin dann hoffentlich fertig.
Also das ist ein einfacher deterministischer Kellerautomat, der solche
Wörter akzeptieren kann.
Man nennt das ja auch ein Palindrom.
Von links nach rechts oder rechts nach links gelesen ist das gleiche
Wort.
Wobei Palindrom ist eigentlich noch was anderes.
Also zum Beispiel das schöne Wort Otto ist ein Palindrom.
Und dieses Wort hier ist auch ein Palindrom.
Stellen Sie sich mal vor, Sie wollen dieses Wort hier mit dieser
Methode überprüfen.
Wie macht man das denn?
Da steht kein C drin, da steht nur 0 und T.
Ich gehe jetzt hier durch von links nach rechts.
Ich könnte ja hier umschalten.
Ich würde dann T und O lesen.
Da kommt aber noch mehr.
Ich wäre nicht fertig.
Muss ich jetzt hier umschalten oder da?
Oder da?
Wo schalte ich denn jetzt am besten um?
Das sieht nicht so einfach aus.
Und das riecht ganz stark danach, dass ich auf einmal etwas nicht mehr
deterministisch machen kann.
Es gibt ja verschiedene Möglichkeiten, bei einem solchen Wort
festzustellen, ist das ein Palindrom.
Es könnte sein, dass nach OT einfach nur TO folgt.
Es könnte sein, dass nach Otto nochmal Otto folgt.
Es könnte sein, dass hier irgendwann das Gleiche andersrum nochmal
folgt.
Das ist ganz deutlich ein Anzeichen für Nichtdeterminismus.
Und genau das machen wir jetzt.
Wir erweitern diese Automaten durch das Konzept der
nichtdeterministischen Kellerautomaten.
Und sagen, okay, ein nichtdeterministischer Kellerautomat ist also ein
solcher Automat.
Im Prinzip genau wie vorher bei deterministischen Kellerautomaten,
aber jetzt dürfen wir hier auf der rechten Seite beliebige Mengen von
Paaren S und K-Stern, also Wörter über K haben.
Das heißt, die Bedingung, die wir vorher hatten, dass wir entweder
einen Übergang machen mit dem aktuellen Zeichen unter dem
Schreiblesekopf oder einen, wenn das nicht definiert ist, einen Lambda
-Übergang machen könnten, diese Bedingung fällt jetzt weg.
Und wenn wir das nichtdeterministisch machen können, dann müssen wir
also nur in der Lage sein zu sagen, naja, nochmal zurück zu unserem
Beispiel hier, dieses Otto.
So, also es gäbe hier verschiedene Möglichkeiten umzuschalten und wenn
es eine Möglichkeit gibt, richtig umzuschalten, die bei einer
Vorgehensweise, die genauso analog ist zu dem, was wir vorgesehen
haben, zu einem Endzustand führt, dann wird das Wort akzeptiert.
Also wenn wir das Wort so abarbeiten können, dass wir tatsächlich zu
einem Endzustand kommen, dass also das, was wir als Eingabe gelesen
haben, auch wieder hier anschließend kommt, in der umgekehrten
Reihenfolge oder auch in der gleichen, wie man hier sieht, das ist ja
hier eigentlich auch schon die umgekehrte Reihenfolge.
Also wenn es sowas gibt, dann hätten wir ein Wort akzeptiert.
Genau wie vorher auch bei den nichtdeterministischen endlichen
Automaten.
Wir müssen sicherstellen, dass wir ausgehend von der
Startkonfiguration C0, wo wir dann verschiedene Möglichkeiten haben
weiterzumachen, daraus dann hier C1, C2, C3, Folgekonfiguration und
wieder das verzweigen können, dass es einen Weg gibt dadurch, der auf
eine Endkonfiguration führt.
Wenn das der Fall ist, dann sagen wir, das Wort wird akzeptiert.
Es kann viele andere Wege geben, die nicht zum Ziel führen, aber es
muss mindestens einen geben, der in einen Endzustand führt.
Und jetzt können wir das auch mit diesem Beispiel machen.
Jetzt haben wir also hier im Prinzip genau das Gleiche wie vorher bei
dem Automaten, der diese Wörter akzeptiert hat.
VC, V-Strich mit der vorgegebenen Umkehrstelle.
Jetzt sagen wir, hier zu Anfang machen wir das Gleiche wie bei dem
anderen Automaten auch.
Dann, wenn wir ein E lesen, haben wir irgendein Zeichen drauf,
schreiben wir das E einfach rein.
Und jetzt sagen wir, wenn wir auf dem Keller das gleiche Zeichen sehen
wie unter dem Schreiblesekopf, dann könnte es ja sein, dass wir gerade
das letzte Zeichen, das wir gelesen hatten, dass das nochmal kommt,
dass das gerade diese Umschaltstelle ist.
Und dann müssten wir halt umschalten und das heißt, wir könnten also
sagen, wir löschen jetzt dieses Zeichen E raus.
Das wäre die eine Möglichkeit.
Die andere Möglichkeit ist, das ist noch gar nicht die Position, wir
machen weiter, wir schreiben auch dieses E rauf.
Das heißt, hier brauchen wir die Alternative, wir müssen, wann immer
eine Situation da ist, bei der wir potenziell umkehren könnten, also
bei dem nochmal wieder zurück zu unserem Otto.
Wir sehen hier, das T ist draufgeschrieben worden, wir lesen das noch
ein T, wir könnten hier umschalten, wir müssen es aber nicht.
Da das gleiche.
Und wenn wir uns entschieden haben, umzuschalten, dann müssen wir auch
bis zum bitteren Ende weitermachen, müssen jetzt überprüfen, ist das,
was im Keller stand, genau das, was jetzt kommt.
Also, wenn wir jetzt in S2 sind und lesen das gleiche Zeichen, löschen
wir das raus.
Wenn wir in S2 sind, lesen ein anderes Zeichen, dann haben wir Pech,
es gibt keinen Übergang, der Automat hält an und ist nicht im
Endzustand.
Und wenn wir auf diese Art und Weise jetzt das K0 sehen, also alles
rausgelöscht haben,
dann machen wir einen Lambda-Übergang
und sagen, okay, dann wird also ein Zustand S3 angenommen und wir
lassen den Keller gleich.
Und dieser Zustand S3 ist jetzt gerade unser einer Endzustand, der
andere ist das S0.
Denn das leere Wort ist auch ein Palindrom, es steht W aus E-Stern.
Auch das leere Wort ist ein Palindrom, muss auch akzeptiert werden
können.
Also S0 muss auch ein Endzustand sein.
Und damit haben wir jetzt einen Automaten konstruiert, der nicht mehr
deterministisch ist.
Das ist ein Kellerautomat.
An dieser einen Stelle hier hat er halt etwas definiert, was vorher
nicht der Fall war.
Wir haben also jetzt hier zwei Folgezustände und alles andere ist
eigentlich genauso, wie bei den deterministischen Kellerautomaten.
Und damit haben wir jetzt die Möglichkeit, ein beliebiges Palindrom zu
erkennen.
Also, das zeigt uns auf einmal, diese Sprache der Palindrome kann man
anscheinend nicht mit einem deterministischen Kellerautomaten
akzeptieren.
Das ist ja erstaunlich.
Bei den endlichen Automaten war das so, da konnten wir alles, was ein
nicht deterministischer endlicher Automat kann, auch mit einem
deterministischen endlichen Automaten simulieren.
Da könnte man sich fragen, gibt es nicht eine Möglichkeit, wie ich den
Keller einsetzen kann, sodass ich das hier auch hinkriege.
Dass ich einen deterministischen Kellerautomaten bauen kann, der genau
die gleiche Sprache akzeptiert als die Sprache der Palindrome.
Und man kann beweisen, ich habe versucht, das hier intuitiv
klarzumachen, man kann beweisen, dass diese Sprache nicht von einem
deterministischen Kellerautomaten akzeptiert werden kann.
Das, was ich hier so leicht argumentiert habe, ist tatsächlich so, man
kann keinen deterministischen Kellerautomaten angeben, der diese
Sprache akzeptiert.
Also haben wir hier, wenn wir uns das hier mal so hinschreiben würden,
NLDETKA über einem Alphabet E ist also echt, nicht nur enthalten,
sondern echt, so jetzt ganz dick, echt enthalten in der Menge der
NDETKA von E.
Sehr schlecht hingeschrieben, kommt auf einer der nächsten Folien.
Also auf einmal ist Nicht-Determinismus und auf einmal ist Nicht
-Gleich -Determinismus.
Es gibt einen deutlichen Unterschied.
Und dass man hier jedes Palindrom so erkennen kann, ist, glaube ich,
deutlich.
Und damit haben wir noch nicht bei der Aussage, doch, wir sind gleich
bei der Aussage, das sind jetzt die beiden Sprachklassen, die ich
gerade so hingekritzelt habe auf der vorigen Folie.
Die Menge der Sprachen, die von deterministischen Kellerautomaten
akzeptiert werden und die Menge der Sprachen, die von Nicht
-Deterministischen Kellerautomaten akzeptiert werden.
Und wir sehen jetzt, das ist ein echtes Enthalten-Sein.
Wir haben also schon die nächste Art von Automaten und die nächste Art
von Sprachen, die uns einen mächtigeren Automaten bringen.
Die Nicht-Deterministischen Kellerautomaten.
Jetzt ist die Frage, gibt es eventuell auch Sprachen, die noch
schwieriger sind?
Das heißt, Sprachen, die nicht von Nicht-Deterministischen
Kellerautomaten akzeptiert werden können.
Ich kann da schon ziemlich viel machen mit den Kellerautomaten, mit
den Nicht-Deterministischen Kellerautomaten.
Und tatsächlich ist es so, es gibt eine Sprache, die Sprache A hoch N,
B hoch N, C hoch N, die kann ich nicht mit dem Kellerautomaten
akzeptieren.
Egal, wie sie sich anstrengen, kein Kellerautomaten ist dazu in der
Lage.
Intuitiv, warum nicht?
Wir werden das formal beweisen.
Sie werden sehen, dass es ganz einfach ist, das zu beweisen.
Das wird über den Pumping-Lemmer bewiesen.
Auf das Pumping-Lemmer kommen wir noch.
Hier gibt es eine Frage.
Aber leider keine Frage angegeben.
Also, wie kann man sich das überlegen?
Warum ist A hoch N, B hoch N, C hoch N keine Sprache, die von
Kellerautomaten akzeptiert werden könnte?
Ganz einfach.
Ich habe hier einen Keller und ich muss zählen, wie viele A's lese
ich.
Ich muss ja von links nach rechts lesen.
Ich merke mir hier irgendwie, wie viele A's ich gelesen habe, auf
welche Art auch immer.
Und die Information, die ich hier reingeschrieben habe in den Keller,
muss ich verwenden, um festzustellen, ob genauso viele B's kommen.
Wenn ich das aber alles verwendet habe, dann ist das Ding hier wieder
weg.
Ich habe ja nur einen Keller.
Das, was ich reingeschrieben habe, ist alles wieder rausgegangen.
Und jetzt kommen auf einmal C's.
Sonst würde ich wissen, sind das genauso viele C's, wie ich vorher A's
und B's gehabt habe.
Dazu bräuchte ich aber die Information, dass ich vorher N A's oder N
B's gehabt habe.
Und die Information ist weg.
Die habe ich aufgebraucht.
Weil wir prüfen, ob A hoch N, B hoch N das Anfangsstück ist.
Das heißt, ich habe keine ausreichende Zählmöglichkeit.
Ich kann mir nicht einen Zähler merken.
Ich müsste mir ja den Zähler gemerkt haben.
Ich kann auch nicht einfach für jedes A dort zwei Zeichen
reinschreiben und dann wäre so eine intuitive Idee.
Ich schreibe einfach für jedes A zwei A's da rein.
Dann habe ich ja zwei N A's anschließend drin.
Das ist ja ganz toll.
Zwei N A's und danach habe ich N B's und danach N C's und hätte ich ja
das Wort A hoch N, B hoch N, C hoch N richtig akzeptiert.
Weil ich ja nur für das B hoch N N A's rausstreiche und für das C
hätte ich ja nochmal N zur Verfügung.
Aber es könnte ja auch B hoch 1,5 N und C hoch N und 1,5 da stehen.
Dann hätte ich auch insgesamt die zwei N A's genommen und hätte nicht
gemerkt, dass die Anzahl der B's und C's nicht identisch ist.
Also es funktioniert einfach nicht.
Man kann das auch formal beweisen.
Dazu kommen wir noch.
Kommt später der Beweis.
Aber das war so die intuitive Erklärung.
Ich kann nicht ausreichend, ich kann mir den Zähler nicht merken.
Ich kann zwar zählen, aber wenn ich gezählt habe, kann ich diesen
Zähler verwenden und wieder zurückzählen.
Aber ich kann nicht den Zähler mir merken und einen anderen Zähler
aufmachen.
Das geht nicht.
Weil ich eben immer nur das oberste Kellerzeichen angucken kann.
Wenn ich einen Automaten hätte, bei dem ich die Sachen stehen lassen
kann im Keller und einfach hier sukzessive weiter runterlaufen, dann
wäre es was anderes.
Das ist aber kein Keller.
Dann müsste ich richtig auf dem Band hin und her laufen können.
Habe ich hier aber nicht zur Verfügung.
Das ist also ein anderer Automat, auf den wir auch noch kommen werden.
Das heißt, wir haben hier den Satz, den wir später beweisen können,
dass tatsächlich die Menge der Sprachen, die von nicht-ideministischen
Kellerautomaten akzeptiert werden, eine echte Teilmenge ist aller
Sprachen, die man sich so vorstellen kann.
Diese Sprache A-Hon, B-Hon, C-Hon ist insbesondere eben nicht in
dieser Menge drin.
So, und jetzt haben wir also diese Folgerung, eine Hierarchie von
Sprachen und eine Frage ist, wie ist eigentlich der Aufwand für die
Spracherkennung?
Also, wie viel Zeit braucht das eigentlich?
Deterministischer Kellerautomat, der hat in jeder Situation, in jeder
Konfiguration nur eine Möglichkeit.
Entweder er liest das Zeichen, was im Schreibkopf steht oder er hat
einen Lambda-Übergang und macht erstmal intern so ein bisschen Arbeit.
Dieses erstmal intern bisschen Arbeit machen, kann aber nicht beliebig
oft.
Ich habe ja nur eine beschränkte Zahl von Kellerzeichen, ich habe eine
beschränkte Zahl von unterschiedlichen Kellerzeichen, eine beschränkte
Zahl von unterschiedlichen Zuständen.
Das heißt, es ist eine konstante Anzahl von Übergängen, unabhängig von
der Länge meines Wortes, die ich intern machen kann.
Und dann mache ich weiter und habe im Prinzip hier Aufwand der Linears
in der Wortlänge.
Ich kann immer genau sagen, was ich tun muss und dieses intern
Arbeiten ist nur eine Anzahl von Übergängen, die unabhängig ist von
der Wortlänge, deswegen ist es eine Konstante und ich bin immer noch
linear.
Wenn ich einen nicht deterministischen Kellerautomaten betrachte, dann
habe ich viele verschiedene Möglichkeiten und hier werden wir
feststellen, etwas später, dass wir mit dem Aufwand von n hoch 3, wenn
also n die Länge des Wortes ist,
dann haben wir einen Aufwand von n hoch 3, um ein solches Wort
festzustellen, ob das Wort in der Sprache ist oder nicht.
n hoch 3 ist ganz schön viel.
Also wenn Sie also Wachstum n hoch 3 haben, für den Aufwand, um
festzustellen, ob das Wort in der Sprache ist oder nicht.
Wenn das die formale Situation wäre, um ein Programm zu beschreiben,
für eine Programmiersprache, dann würde also mit zunehmender Länge der
Programme auf einmal der Aufwand, um die syntaktische Korrektheit zu
überprüfen, kubisch anwachsen.
Wenn Sie ein 10.000-Zeilen-Programm haben und Sie müssen 10.000 hoch 3
nehmen, und ich sage nur Zeilen, in jeder Zeile sind eine ganze Reihe
Zeichen, können Sie sich vorstellen, wie lange das dauert.
Linear wäre das schon viel besser.
Und deswegen sagt man auch, das muss linear sein.
Also sind wir eigentlich schon fertig mit der wesentlichen Frage.
Die Grenze für die Sprachen, die ist genau hier.
Wir werden also sehen müssen, dass alle unsere Programmiersprachen
durch die deterministische Kellerautomaten akzeptiert werden können.
Und genau das ist der Fall.
Alle Programmiersprachen, die Sie kennen, sind Programmiersprachen,
die man durch deterministische Kellerautomaten beschreiben kann.
Hier drüber ist der Aufwand für das Wortproblem, also für die
Überprüfung der syntaktischen Korrektheit eines Wortes oder eines
Programms zu hoch.
Und deswegen vermeidet man solche Sprachen.