So,
schönen guten Morgen.
Ich begrüße Sie zur Fortsetzung der Vorlesung Grundlageninformatik 2.
Schön, dass Sie heute Morgen alle da sind.
Und was haben wir letztes Mal gemacht?
Wir haben uns beschäftigt mit, natürlich Grundlageninformatik 2, mit
endlichen Automaten, regulären Sprachen, rechtslinearen Sprachen.
Wir waren ja schon ziemlich weit gekommen bei den Automaten und hatten
dort uns sehr viele Dinge angeschaut.
Und insbesondere hatten wir richtig uns letztes Mal, nachdem wir ja
uns mit der Reduktion von Automaten beschäftigt hatten, das war hier
diese Folie und die davor, wo wir gesehen hatten, wie wir feststellen
können, welche Zustände äquivalent sind, hatten wir einen Automaten
reduziert, also die kleinstmögliche Anzahl von Zuständen gefunden und
entsprechend den dann so neu aufgeschrieben und hatten dann uns
beschäftigt mit nichtdeterministischen endlichen Automaten, also
Begriff des Nichtdeterminismus und hatten den genauer angeschaut,
hatten ein Beispiel gesehen, das uns dann verfolgt hat durch mehrere
Folien, wo wir immer wieder diesen Automaten, der hier zu sehen ist,
betrachtet haben und haben dann gesehen, wie wir diese
Übergangsfunktion erweitern können auf Wörter, haben dann gesehen, wie
wir eine Übergangsrelation auf Konfiguration definieren können, wir
haben gesehen, was die Sprachen sind, das heißt, dass es einen
Konfigurationspfad geben muss, der zu einem Endzustand führt und haben
dann gesehen, dass wir tatsächlich nichtdeterministische endliche
Automaten, indeterministische oder zu denen einen äquivalenten
deterministischen Automaten finden können, das heißt, die Sprachklasse
wird nicht erweitert.
Der äquivalente Automaten zu dem, den wir als Beispiel genommen
hatten, sah dann etwas komplizierter aus, weil halt einige Übergänge
dazugefügt werden müssen und wir hatten dann schließlich die
Erkenntnisse zusammengefasst und hatten schließlich noch uns überlegt,
wie wir in der Lage sind festzustellen, ob die Vereinigung oder das
Produkt oder die Iteration von Sprachen wieder eine Sprache ist, die
von endlichen Automaten erkannt werden kann.
Wir hatten Konstruktionen gemacht, bei denen man genau diesen
Nichtdeterminismus ausnutzen muss und es reicht dann ja, einen
nichtdeterministischen Automaten anzugeben.
Deswegen ist das eine sehr praktische Erkenntnis, dass man dadurch im
Prinzip die Sprachklassen nicht verlässt.
Und schließlich kamen wir dann zu den regulären Ausdrücken und
regulären Sprachen, wo wir ausgehend von einer Reihe von einfachen
Basismengen über Operationen eine Menge von Sprachen erzeugen, das war
die Menge der regulären Sprachen, bei der wir ausgehend von den
Sprachen, die einfach nur einzelne Zeichen enthalten und von der
leeren Menge, die durch Vereinigung, Produkt und Iteration eine Reihe
von neuen Sprachen erzeugen.
Wir hatten gesehen, dass wir das auch über reguläre Ausdrücke
beschreiben können, hatten uns dazu Beispiele angesehen und erkannt,
dass das natürlich genau die regulären Sprachen sind, die wir die
regulären Ausdrücke beschreiben und dass die endlichen Automaten
natürlich alle regulären Sprachen erkennen können, weil wir ja
ausgehend von solchen einfachen Automaten über Vereinigung, Produkt
und Iteration, wie wir das gerade gesehen hatten, alle regulären
Sprachen erzeugen können.
Das heißt, die Sprachmengen sind identisch.
Und das war dann hier nochmal ein Beispiel für den regulären Ausdruck
zu einem Automaten.
Und heute kommen wir dann noch zu dem letzten Punkt bei dieser
Sprachklasse.
Wir wollen uns wieder zurückbesinnen darauf, dass wir ja angefangen
hatten mit der Beschreibung von Sprachen durch Grammatiken.
Wir hatten ja mit dem erzeugenden System ursprünglich mal angefangen,
waren dann zunächst mal auf die Automaten gegangen, hatten jetzt die
regulären Ausdrücke kennengelernt.
Und jetzt gehen wir zurück zu den Grammatiken und erinnern uns noch
einmal, was war eigentlich eine Chomsky-Grammatik?
Das war doch so ein Gebilde, wo wir Nicht-Terminal-Symbole, Terminal
-Symbole, Regeln und ein Staatssymbol haben.
Und die Regeln sind gerade immer so Paare von Wörtern über dem Nicht
-Terminal - und Terminal-Alphabet.
Wir hatten dann diese allgemeine Definition der Chomsky-Grammatiken
eingeschränkt.
Am stärksten bei den Typ-3- beziehungsweise rechtslinearen
Grammatiken, bei denen die Regeln alle von einer dieser drei Formen
waren.
Entweder kann ein Nicht-Terminal-Zeichen durchs leere Wort ersetzt
werden, oder durch ein Terminal-Zeichen, oder durch ein Terminal
-Zeichen gefolgt von einem Nicht-Terminal.
Und weil das eine lineare Form ist, bei der die Variable immer rechts
steht, reden wir von rechtslinearen Grammatiken bei dieser Form.
Wenn man erst das Nicht-Terminal und dann eine Konstante schreiben
würde, wäre es eine linkslineare Grammatik.
Wir haben also in dem Fall rechtslineare Grammatik, rechtslineare
Produktion und das einfache Beispiel, das ich Ihnen schon mal in
ähnlicher Form gegeben hatte, oder zumindest ist das hier ein
einfaches Beispiel für eine solche rechtslineare Grammatik.
Wir haben ein Start-Symbol, wir haben ein einfaches Terminal-Zeichen,
Alphabet A und B, und wir wollen jetzt einfach nur sehen, was diese
Grammatik hier uns für eine Sprache erzeugt.
Wir haben eine Regel, bei der wir das Start-Symbol ersetzen können,
durch ein A gefolgt vom Start-Symbol, oder wir können es ersetzen
durch ein B gefolgt von einem Nicht-Terminal A, und das A können wir
durch ein kleines a ersetzen.
Was sind die Wörter, die dadurch erzeugt werden können?
Naja, wir können über diese Regel A hoch N S erzeugen, also wenn wir
von S starten, können wir dieses S ersetzen durch A S, das ist diese
Regel da oben, dann können wir das S wieder ersetzen durch A S und so
weiter, und kommen damit über beliebig häufige Anwendung oder
entsprechend häufige Anwendung auf A hoch N S.
Also das können wir erzeugen, Sie erinnern sich, diese Ableitung,
Doppelfeil -Ableitung, heißt, wir wenden eine Regel aus der Regelmenge
P an.
Und anschließend will ich natürlich dieses S hier noch irgendwie
wegbekommen, weil die Wörter der Sprache ja keine Nicht-Terminale
enthalten dürfen, dazu muss ich also mal eine andere Regel anwenden,
das wäre diese hier, S auf B A, und dann will ich das A noch
wegbekommen, und dann wird aus dem großen A ein kleines A.
Und das heißt dann, insgesamt habe ich also zum Beispiel, das war die
Reihenfolge A hoch N S, was wir gerade gesehen hatten, also A hoch 3 S
zum Beispiel, dann wenden wir einmal die Regel an, bei der wir das S
ersetzen durch B A, einmal setzen wir das A durch A, dann haben wir
das Wort A hoch 3 B A hier erzeugt.
Also das ist eine ganz einfache Grammatik.
Und letztes Mal hat jemand sich beschwert, dass das alles so formal
ist.
Natürlich ist das formal.
Aber das Schöne ist, dass ich Ihnen die Konzepte an ganz einfachen
Beispielen erklären kann.
Und die Erkenntnisse, die Sie an einfachen Beispielen gewinnen, die
ich hier auf einer Folie ganz einfach Ihnen darstellen kann, diese
Erkenntnisse gelten genauso für die komplizierten Grammatiken, die wir
aufschreiben müssen, wenn wir eine richtige Programmiersprache
beschreiben wollen.
Und das heißt, das, was wir hier an Erkenntnissen gewinnen, an den
einfachen Beispielen, die so formal aussehen und so abstrakt, das sind
genau die Erkenntnisse, die wir brauchen, um in der Praxis dann
tatsächlich etwas Sinnvolles damit zu machen.
Und das ist das Schöne an der Theorie.
Wir können abstrahieren von den vielen komplizierten Einzelheiten der
Realität und haben dann das reduziert auf die wesentlichen
Eigenschaften, mit denen beschäftigen wir uns.
Und dann werden wir die Erkenntnisse, die wir gewonnen haben, an auf
die praktischen Beispiele, auf die praktischen Anwendungen.
Dann wissen wir etwas darüber, was wir mit den rechtslinearen
Grammatiken grundsätzlich machen können.
Oder auch nicht machen können, wie beim Pumping Lemma zum Beispiel.
Sofern, das müssen wir noch zeigen, dass Pumping Lemma auch etwas mit
den rechtslinearen Grammatiken zu tun hat und der rechtslinearen
Sprache.
Also, jetzt haben wir hier das umgekehrte Problem.
Wir haben eine Sprache beschrieben, wieder eine sehr einfache Sprache.
Eine Sprache, die eine ungerade Anzahl von Einsen enthält.
Oder jedes Wort enthält eine ungerade Anzahl von Einsen.
Wie kann man eine solche Grammatik aufschreiben?
Zum Beispiel so, wie das hier steht.
Aus dem Startsymbol können wir ein Eins erzeugen und dann mit A
weitermachen.
Oder wir können eine Null erzeugen und mit S weitermachen.
Das heißt, Sie sehen sofort, wir können also beliebig viele Nullen
erzeugen.
Und wenn wir eine Eins erzeugt haben, dann müssen wir mit einer
variablen A weitermachen.
Diese Schreibweise übrigens mit dem senkrechten Strich, daran erinnern
Sie sich auch, das war dieses Alternativsymbol oder Auswahlsymbol, das
eine der Alternativen, die durch diesen senkrechten Strich getrennt
sind, ausgewählt werden kann.
Das A können wir ersetzen, entweder durch das leere Wort und dann sind
wir fertig.
Oder wir können eine Eins erzeugen und sind wieder bei der
Anfangssituation.
Dazu kommen wir zurück, wenn wir einmal eine Eins erzeugt hatten und
wir erzeugen eine zweite Eins, gehen wir zurück zu dem Startsymbol S,
das wäre auch eine gerade Anzahl von Einsen und wir wollten keine
Wörter erzeugen, die eine gerade Anzahl von Einsen haben.
Wenn wir also eine Eins erzeugen, müssen wir zurück zum Startsymbol.
Wir können auch beliebig viele Nullen erzeugen, ausgehend von dem A.
Oder das A eben weglassen, weil wir ja jetzt eine Eins in dem Wort
stehen hatten.
Und wenn wir dann wieder zu dem S zurückgegangen sind, können wir also
beliebig viele Nullen erzeugen.
Oder wenn wir eine Eins erzeugen, müssen wir wieder zu dem A gehen.
Also, wir erinnern uns daran, ich schreibe nochmal kurz hier eine
Ableitung auf, wir können von S auf Null S gehen, können dort beliebig
viele Nullen hinschreiben und können dann einmal, wenn wir hier diese
Nullen hingeschrieben haben, können wir eine Eins hinschreiben, haben
wir dann das A und können dann mit beliebig vielen Ersetzungen daraus
ein Null und so weiter, da können wir hier die Eins und wieder
irgendwelche Nullen haben.
Dann wieder eine Eins und das S und dann zum Beispiel daraus
entsprechend weitermachen.
Indem wir das S dann ersetzen nochmal durch ein Eins S, dann würde in
dem Fall eine dritte Eins da hinkommen und dann können wir das nicht
Eins S, sondern Eins A und dann würde das A durch das leere Wort
ersetzt und dann würde hier irgendwas stehen wie Null hoch A Eins,
Eins hoch Eins, dann B hoch...
Quatsch, Null hoch B Eins und dann würde hier vielleicht einfach
nochmal eine Eins stehen, das würde schon reichen.
Die Eins würden wir erzeugen dadurch, dass wir hier diese Regel S auf
Eins A hinschreiben, das A auf das leere Wort.
Eine ungerade Anzahl von Einsen.
Und Sie erinnern sich, dass wir genau für diese Sprache auch einen
endlichen Automaten konstruiert hatten, der so aussah, wie hier
angegeben.
Zwei Zustände und von dem Anfangszustand gehen wir mit einer Eins auf
S Eins, dann sind wir fertig, weil wir eine Eins erzeugt haben, eine
ungerade Zahl von Einsen.
Wann immer wir eine gerade Zahl von Eins in diesem Wort haben, sind
wir in dem Zustand S Null und mit einer Eins gehen wir dann auf das S
Eins.
Und wenn Sie das vergleichen, diese Regelmenge hier und den Automaten,
sehen Sie es eigentlich sofort, dass die sehr viel Ähnlichkeit haben.
Wir haben hier beim Automaten zwei Zustände, bei der Grammatik zwei
Nicht -Terminalsymbole.
Wir haben einen Anfangszustand im Automaten, wir haben ein Startsymbol
S in der Grammatik, wir haben einen Endzustand S Eins in unserem
Automaten, das ist der hier, und wir haben ein Symbol A, das wir auf
das leere Wort oder durch das leere Wort ersetzen können.
Das heißt, wenn wir das leere Wort ersetzen, können wir ja nicht
weitermachen, wir sind fertig.
Das entspricht dem Endzustand bei dem Automaten.
Und die Übergänge waren beim Automaten so definiert, zum Beispiel,
dass wir vom Startzustand bei Eingabe einer Eins auf S Eins gehen.
Bei der Regel ist es so, dass wir dieses Startsymbol S ersetzen können
durch Eins A, also auf ein anderes Nicht-Terminalzeichen gehen.
Das ist sehr ähnlich.
Und diese Analogie, die machen wir ein bisschen allgemeiner und
überlegen uns, wie wir denn nun vielleicht zeigen könnten, dass
endliche Automaten und rechtslineare Grammatiken so ähnlich sind, dass
sie die gleichen Sprachen erzeugen können.
Und das machen wir hier mit einem ganz einfachen Algorithmus.
Und die Idee ist einfach, dass wir praktisch die Zustandsmenge eines
Automaten, also wir wollen hier eine rechtslineare Grammatik aus einem
Automaten konstruieren, die Menge der Nicht-Terminalsymbole wird
gerade gleich der Zustandsmenge sein, die Menge der Terminalsymbole
ist genau die gleiche wie das Eingabealphabet des Automaten.
Und wenn wir eine Überführung haben von einem Zustand S auf einen
Zustand S' mit einer Eingabe E, dann werden wir eben gerade
entsprechend daraus andersrum.
Ich habe da aus der rechtslinearen Grammatik, also wenn wir von S auf
E S' gehen, würden wir im Automaten praktisch einen Übergang haben vom
Zustand S in den Zustand S' mit der Variablen E.
Wir wollen also zeigen, dass das hier genau äquivalent ist, diese
beiden Sachen.
Das ist schon richtig.
Also wir wollen eine rechtslineare Grammatik aus dem Automaten
konstruieren.
Sie sehen, ich kam gerade durcheinander, weil die Konstruktion völlig
äquivalent in beide Richtungen funktioniert.
So, wir haben die Überführungsfunktion und wollen daraus jetzt eine
Regel erzeugen.
So, das war die genaue Überlegung.
Und wenn wir einen Endzustand haben im Automaten, wenn das ein
Endzustand wäre, dann bräuchten wir eben eine Regel S' auf Lambda,
damit wir die Produktion eines Wortes abschließen können.
Und der Algorithmus sieht also so aus, relativ einfach, eigentlich
genau das hier übertragen.
Wir haben den endlichen Automaten als Eingabe mit Eingabealphabet,
Zustandsmenge, Übergangsfunktion, Anfangszustand und Menge der
Endzustände.
Wir haben vor, daraus eine Grammatik zu machen, die die gleiche
Sprache erzeugt.
Also die Sprache der Grammatik soll die Sprache des Automaten sein.
Und wir machen das so, dass wir eben diese Mengen N, T, P und S0 als
Anfangszustand jetzt hier angeben.
Ich habe hier S0 geschrieben, weil das S ist ja schon vergeben für die
Menge der Zustände des Automaten.
So, wir fangen also an damit, dass wir das Terminalalphabet gleich der
Eingabemenge des Automaten setzen, das Nicht-Terminalalphabet gleich
der Zustandsmenge.
Und wir fangen mit einer leeren Regelmenge an, da setzen wir das
Startsymbol, das SG, also kein 0 hier, sondern ein G, das Startsymbol
der Grammatik, setzen wir auf den Anfangszustand des Automaten.
Jeder Zustand wird ja als Nicht-Terminalzeichen aufgefasst.
Und wenn wir jetzt eine Überführung haben in unserer Zustandsfunktion,
Übergangsfunktion oder aus der Zustandstabelle, können wir das alles
ablesen.
Wenn wir also von S mit E nach S' übergehen, das ist das, was ich hier
oben angedeutet habe, dann machen wir daraus eine neue Regel, bei der
wir das Symbol S ersetzen durch ES', also das Terminalzeichen E
gefolgt von dem Nicht-Terminal S'.
Und das ist schon alles, damit haben wir dann alle Regeln.
Und für jeden Endzustand müssen wir einfach nur die Regel dazu fügen,
dass wir diese Variable S durchs leere Wort ersetzen können.
Das ist genau die Überführung, die wir brauchen.
Es hat schon jemand eine Frage.
Ist es für die Klausur ausreichend, die Anwendungen im Tutorial gut
verstanden zu haben, jedoch nicht bei jeder formalen Herleitung
mitgekommen zu sein?
Oder werden auch Beweise oder formale Definitionen abgefragt?
Jein.
Also, es geht mir darum, dass Sie etwas lernen.
Es geht mir nicht darum, ich werde also keine Fragen haben, das ist
nicht würdig für eine Universität.
Schreiben Sie auf, was auf Folie 17 in der 5.
Zeile stand.
Das wäre Quatsch.
Ich würde auch nicht genau eine Definition abfragen.
Aber ich kann natürlich fragen, dass Sie das Pumping Lemma anwenden
sollen.
Wenn Sie das Pumping Lemma anwenden sollen, um zu überprüfen, ob
irgendeine Sprache nicht von ähnlichen Automaten erkannt werden kann,
dann müssen Sie natürlich in der Lage sein, sich das aufzuschreiben.
Ob Sie das mit meinen Worten machen, die ich hier auf den Folien
verwende, oder mit Ihren Worten, aber vom Inhalt her das Richtige.
Das ist mir und auch den Tutoren völlig egal.
Sie sollen die wesentlichen Erkenntnisse gewonnen haben und verstanden
haben.
Auf die Wörter, die Sie gebrauchen, kommt es mir nicht an.
Sie sollen aber das Richtige aufschreiben.
Und ich kann Sie auch, wenn ich Ihnen die Aufgabe gebe, zum Beispiel
zu überprüfen, ob eine Sprache von einem endlichen Automaten erkannt
werden kann, dann müssen Sie, wenn es so ist, dass sie nicht erkannt
werden kann, genau diesen Beweis durchführen, dass diese Sprache nicht
erkannt werden kann.
Das heißt, Sie müssen sich irgendeine Zahl hernehmen, müssen ein Wort
finden und für jede beliebige Zerlegung mit diesen gewissen
Eigenschaften 1 und 2, weil auch das ist ein Pumping Lemma, zeigen,
dass es dann eine Möglichkeit gibt, dieses Mittelstück so zu
wiederholen, dass das sich daraus ergebende Wort nicht in der Sprache
ist.
Das ist eine Herleitung, das ist ein Beweis für eine Aussage, die Sie
eben zeigen müssen.
Insofern müssen Sie auch in einer Klausur einen Beweis machen, weil
Sie beweisen müssen, dass eine bestimmte Sprache nicht von endlichen
Automaten erkannt werden kann oder später nicht von kontextfreien
Grammatiken erzeugt werden kann.
Das ist eine andere Art Pumping Lemma.
Insofern müssen Sie auch einen Beweis machen können.
Aber wenn ich hier einen großen formalen Beweis für irgendeine
wesentliche Aussage mache, werde ich Sie nicht bitten, genau diesen
Beweis nochmal aufzuschreiben.
Aber Sie sollen die Erkenntnisse, die Sie daraus gewinnen, verstanden
haben und müssen sie richtig anwenden können.
Sie müssen Fertigkeiten erwerben.
Das sind die Dinge, die ich in Klausuren abfrage.
Ob Sie gewisse Dinge gelernt haben, nicht genau Buchstabe für
Buchstabe, sondern Sie müssen das gelernt haben in dem Sinne, dass Sie
wissen, was die wesentlichen Erkenntnisse sind und die auch
formulieren können.
Und ich möchte gerne sehen, dass Sie auch wissen, wie man diese
Erkenntnisse einsetzt.
Sie müssen Fertigkeiten erworben haben, dadurch, dass Sie hier dem
Stoff gefolgt sind und Übungen bearbeitet haben.
Also das zu dieser Frage.
Es ist klar, dass es nicht nur darum geht, irgendeinen Stoff
buchstabengetreu zu lernen.
Davon haben Sie gar nichts.
Sie sollen die Erkenntnisse verstehen und anwenden können.
Das ist das, was ich Ihnen vermitteln möchte.
Okay, ich hoffe, das reicht erstmal.
Sie werden noch viele Informationen dazu kriegen in den Übungen.
Wir haben auch eine Großübung, wenn ich richtig weiß, am 5.
Dezember ist eine Großübung.
Also hier eine große Saalübung, wo meine Mitarbeiter nochmal
wiederholen, was alles so an Fragen oder an Themen dran gewesen ist.
Und dann wird nochmal genauer darauf eingegangen, was dann auch
relevant ist für die Klausur oder für die Klausuren.
Aber Sie müssen eben zum Beispiel in der Lage sein, einen nicht
deterministischen Automaten deterministisch zu machen, den
äquivalenten Automaten erzeugen können.
Sie müssen in der Lage sein, einen Automaten zu reduzieren.
Sie müssen darstellen können, was zum Beispiel heißt, dass zwei
Zustände 5-Äquivalent sind und nicht 6-Äquivalent.
Woran das liegt oder warum sie vielleicht nicht 6-Äquivalent sind.
Oder ob es sein kann, dass sie 7-Äquivalent und nicht 8-Äquivalent
sind.
Oder nicht 8-Äquivalent, aber 10-Äquivalent.
Solche Dinge könnte ich Sie fragen.
Und dann müssen Sie verstanden haben, was diese Definitionen bedeuten.
Und genau darum geht es.
Okay, also hier müssen Sie verstanden haben, dass die rechtslinearen
Grammatiken und die endlichen Automaten offensichtlich eine sehr
ähnliche Ausdrucksfähigkeit haben, weil ich eben genau das, was ich
mit der Überführungsfunktion hier machen kann, in Regeln einer
rechtslinearen Grammatik überführen kann.
Und wir machen das genau andersrum.
Dann nochmal auf dieser Folie, dass wir aus einer rechtslinearen
Grammatik einen Automaten erzeugen.
Da ist es so, dass wir eine Regel haben bei der rechtslinearen
Grammatik.
Und aus der Regel machen wir eine Überführung im Automaten.
Das heißt, hier wird der Automat die Nicht-Terminalsymbole der
Grammatik als Zustände bekommen.
Und für jede Regel A auf AB werden wir einen Zustand B als möglichen
Folgezustand dieses Zustands A bei Eingabe von klein a haben.
Das heißt für alle Konfigurationen, wenn wir im Zustand A sind und wir
lesen ein kleines a ein, gehen wir in Zustand B und müssen
entsprechend weiterlesen.
Das ist klar.
Wenn das A auf ein leeres Wort geht, das war die zweite Möglichkeit
oder eine weitere Möglichkeit für die Regeln der rechtslinearen
Grammatik, dann muss das A ein Endzustand sein.
Und wenn wir das A direkt durch ein Terminalsymbol ersetzen, heißt das
ja, wir sind eigentlich auch fertig.
Jetzt wird das A durch ein kleines a ersetzt.
Wir müssen in einen Zustand übergehen.
In welchen Zustand gehen wir denn?
Dafür brauchen wir einen extra Endzustand, auf den wir gehen können
von diesem großen a aus mit klein a.
Das muss ein Endzustand sein, den wir neu dazufügen.
Und das ist schon unsere ganze Idee, die wir brauchen.
Wir können dann aus der rechtslinearen Grammatik einen nicht
-deterministischen endlichen Automaten machen.
Wieder sehen Sie, es ist ganz wichtig, dass wir die Möglichkeit haben,
einen nicht-deterministischen Automaten anzugeben, der dazu passt.
Wir brauchen nicht einen deterministischen anzugeben.
Wir wissen ja, die nicht-deterministischen sind genauso mächtig.
Und das macht die Konstruktion sehr einfach.
Also, einen nicht-deterministischen endlichen Automaten, der natürlich
die gleiche Sprache akzeptieren soll.
Der bekommt als Eingabezeichen gerade die Terminalsymbole, bekommt als
Startzustand gerade das Startsymbol der Grammatik, bekommt als
Zustandsmenge die Nicht-Terminalzeichen der Grammatik und diesen
speziellen Zustand Sigma 0 für diesen Endzustand, den wir ja noch
extra brauchten, für Regeln dieser Art.
Und dann müssen wir für jede Regel, also für jedes A und jedes kleinen
A, warum müssen wir das für jedes A machen?
Wir müssen ja unsere Tabelle aufmalen und da müssen jetzt alle unsere
Zustände hier stehen und alle Eingabezeichen.
Das heißt, insbesondere muss hier irgendein A stehen und da oben muss
ein kleines A stehen, entsprechend weiter, B, C, D und so weiter.
Und hier die Nicht-Terminalzeichen, wir müssen für jedes Nicht
-Terminalzeichen und jedes Terminalzeichen angeben, wie der Automat
oder was der Automat denn hier nun für einen Eintrag bekommt.
Oder wenn wir hier irgendeinen C haben und hier irgendeinen X, dann
müssen wir wissen, was muss an dieser Stelle in der Tabelle stehen.
Das heißt, für jedes Nicht-Terminalzeichen, jedes Terminalzeichen
müssen wir sagen, wie diese Übergangsfunktion Delta definiert wird.
Und wie wird sie nun definiert?
Wir müssen angeben, die Menge der Zustände, die wir erreichen können,
von dem Zustand A aus.
Welche Zustände sind das?
Das sind alle Nicht-Terminalzeichen, die wir über Regeln der Grammatik
erreichen konnten.
Das heißt, wenn wir eine Regel A auf klein a b haben, dann erreichen
wir im Automaten durch Eingabe von klein a den Zustand b.
Es kann ja sein, dass es mehrere Regeln gibt.
Es kann ja sein, dass das geht auf klein a, da ist wieder der
senkrechte Strich, und a, oder vielleicht auf b a und vielleicht auf c
d und so weiter.
Es kann ja mehrere solche Regeln geben.
Dann müssten wir in dem Fall also auf den Zustand a gehen und auf den
Zustand, also mit dem kleinen a würden wir auf das a gehen, mit dem
kleinen b wieder auf das a, mit dem kleinen c auf d.
Und es könnte aber auch sein, dass wir noch eine Regel haben, c b.
Und dann würden wir mit dem c aus dem Zustand a auf groß b gehen und
auch auf das groß d.
Also wir könnten eventuell mehrere Regeln haben, bei denen wir auf der
rechten Seite das b stehen, auf der linken Seite das a stehen haben,
dann das Terminalzeichen klein a und dann irgendeine Variable.
Und es kann eben sein, dass da verschiedene Variablen auftauchen in
der Grammatik.
Entsprechend müssen wir auf verschiedene Zustände gehen in dem
Automaten.
Beziehungsweise an der Menge der Folgezustände müssen alle Nicht
-Terminalzeichen drin sein, die wir erreichen können dadurch, dass wir
auf der rechten Seite dieses Terminalzeichen a haben und dann eben
dahinter das Nicht-Terminalzeichen.
Wenn es keine solche Regel gibt, bei denen das große a auf irgendein
klein a geht, dann ist die Menge leer.
Also viele solcher Einträge werden leer sein, weil wir nicht für jedes
Zeichen des Terminalalphabets eine Regel haben, bei denen jetzt gerade
das groß a auf klein a und irgendwas anderes geht.
Also das sind diese Regeln.
Und wenn es eine Regel gibt derart groß a auf klein a, also wenn das a
durch ein Terminalzeichen ersetzt wird, dann müssen wir entsprechend
dieser Folgezustandsmenge von a bei Eingabe von klein a hinzufügen den
Zustand Sigma 0.
Das ist das, was ich hier oben als Idee angedeutet hatte.
Wenn wir eben fertig sind mit der Ableitung, müssen wir im Automaten
in einen Endzustand kommen.
Das ist dann genau dieser Zustand Sigma 0.
Und Sie sehen, von dem Sigma 0 aus haben wir noch gar nichts
definiert.
Wir müssen das also am Ende noch nachtragen, dass wir für jedes
Eingabezeichen festlegen, wir haben überhaupt keinen Übergang.
Von dem Sigma 0 aus brauchen wir nicht weiterzumachen, das ist nur ein
Endzustand.
Da sind wir drin und sind fertig, der braucht keine weiteren
Übergänge.
Und Sie sehen schon, dieser Automat, den wir da bekommen, der ist sehr
nicht deterministisch, oder genauso nicht deterministisch, wie es eben
verschiedene Regeln gibt, bei denen wir auf der rechten Seite ein
Nicht -Terminalzeichen durch das gleiche Terminalzeichen ersetzen
können und dann irgendein Nicht-Terminalzeichen.
Also, das ist völlig analog zu der Konstruktion, die wir auf der
vorigen Seite gesehen hatten.
Da waren wir aber von einem deterministischen Automaten ausgegangen
und hatten zudem eine rechtslineare Grammatik erzeugt.
Hier gehen wir von einer rechtsbeliebigen rechtslinearen Grammatik aus
und erzeugen einen äquivalenten endlichen Automaten, aber der kann
natürlich entsprechend der Struktur der rechtslinearen Grammatik auch
nicht deterministisch sein.
Und ich denke, das ist naheliegend, das so zu machen.
Hier nochmal ein Beispiel, wenn wir die Grammatik nochmal nehmen, die
hatten wir schon gesehen, diese einfache Grammatik, um die Sprache zu
erzeugen, bei der alle Wörter eine nicht gerade Anzahl von Einsen
haben, dann müssen wir entsprechend unserem Algorithmus jetzt einen
Automaten erzeugen und dieser Automat sieht dann halt so aus, dass wir
von dem Zustand S aus bei Eingabe von 0 auf eine Menge von Zuständen
gehen müssen.
Wir können von S aus auf 0S gehen, das heißt, wir kommen wieder zum
Zustand S zurück.
Das ist die einzige Möglichkeit für dieses Zeichen 0.
Also haben wir hier die Menge, die nur aus dem Zustand S besteht.
Wenn wir eine Eins eingeben im Zustand S, dann haben wir in der
Grammatik die Regel S auf 1A.
Das heißt, wir gehen auf die Menge, die nur auf dem Zustand A besteht.
Und wenn wir uns den Zustand A anschauen, der ja dem Zeichen A
entspricht in der Grammatik, dann haben wir hier die Möglichkeiten für
das Eingabezeichen 1 nach S zu gehen.
Also für 1 gehen wir in den Zustand S, mit 0 bleiben wir im Zustand A.
Und dann haben wir noch die Regel A auf Lambda.
Und dafür war es klar, dass wir...
Da kommt kein weiterer Übergang hier.
Wir müssen von dem Sigma 0 dann auf die leere Menge gehen.
Also von dem Sigma 0 aus brauchen wir gar nicht weiterzumachen.
Das A auf Lambda hat ja hier keine weitere Entsprechung.
Wo haben wir das hier drin?
Genau, die Endzustände.
Da war ich gerade etwas irritiert.
Diese Regeln sagen ja nur, das charakterisiert gerade die Zustände,
die Endzustände sind.
Nämlich alle Zustände, die direkt auf das leere Wort gehen, sind
Endzustände.
Und unser Sigma 0 ist Endzustand.
Also ist, weil wir das A auf Lambda drin haben, dieser Zustand A ein
Endzustand.
Und Sigma 0 natürlich auch.
Und Sigma 0 ist hier mit drin, wird gar nicht erreicht.
Hätten wir also gleich wieder streichen können.
Wenn wir das reduzieren, würden wir das Sigma 0 gleich wieder
rausstreichen.
Also das ist der Automat, den wir dann erzeugen.
Ich kann den auch, wenn ich das nicht so stehen haben möchte, dass es
die gleichen Bezeichnungen sind, dann kann ich auch das in der
üblichen Art und Weise mit S0 irgendwas bezeichnen.
Dann habe ich hier S0, SA und das Sigma 0 stehen.
Wobei, wie gesagt, diese Zeile hier könnte man genauso rausstreichen.
Die brauchen wir eigentlich nicht.
Jetzt gibt es die nächste Frage.
Wie wird es übersetzt, wenn bei der Grammatik zwei Terminale
eingesetzt werden?
Das haben wir ja bei den restlinearen Grammatiken so nicht erlaubt.
Bei den restlinearen Grammatiken haben wir auf der rechten Seite nur
ein Terminalzeichen und ein Nicht-Terminalzeichen erlaubt.
Nicht zwei Terminalzeichen.
Ich kann hinzufügen, dass man zeigen kann, dass sich zu jeder
Grammatik, die es auch erlaubt, dass sie mehrere Terminalzeichen auf
einen Schlag dort reinschreiben können und ein Nicht-Terminalzeichen.
Dass man zu solchen Grammatiken äquivalente, strenge, restlineare
Grammatiken finden kann, die die gleiche Sprache erzeugen.
Aber die also das in zwei Schritten machen müssen.
Das erhöht nicht die Ausdrucksfähigkeit der restlinearen Grammatiken.
Trotzdem haben wir das so nicht vorgesehen.
Und deswegen kann ich mich darauf beschränken, das nur für die zu
machen, bei denen wir eben immer nur ein Terminalzeichen haben.
Also diese Art Regeln, die wir da sehen, die kommen in unseren
restlinearen Grammatiken, so wie ich sie definiert habe, nicht vor.
Man kann eine Verallgemeinerung machen.
Nur dann müsste man entsprechend eine andere Konstruktion wählen bei
dieser Überführung auf den endlichen Automaten.
Dann müsste man nämlich bei der Überführung auf den endlichen
Automaten dafür sorgen, dass man zunächst mal sich eine äquivalente
Grammatik erzeugt, die jetzt genau der Definition entspricht.
Und zu der wissen wir, wie wir den äquivalenten Automaten erzeugen.
Also das ist, wenn Sie da Wörter reinschreiben, die aus einem Zeichen
entstehen können, gefolgt von einem Nicht-Terminalzeichen, dann ist
diese Übertragung nicht so ohne weiteres möglich.
Da müssen Sie den Umweg machen über die strikte Form der
Rechtslinearität.
Okay, das zu dieser Äquivalenz.
Und dann sind wir schon ziemlich weit gekommen.
Der ist natürlich nicht deterministisch, hat ich schon gesagt.
Der kann durch das Verfahren auf Seite 251 erzeugt werden.
Sie werden, wenn Sie jetzt in Ihre ausgedruckten Folien reinschauen,
sehen Sie, dass da 250 stand.
Irgendwo habe ich meine Folie eingefügt.
Deswegen ist das 251.
Und wir haben also den Satz, dass Sie zu jedem deterministischen
endlichen Automaten eine rechtslineare Grammatik finden können und
umgekehrt.
Jetzt können Sie sagen, wir haben doch gerade zu der Grammatik einen
nicht -deterministischen Automaten gefunden.
Aber zudem gibt es ja auch einen deterministischen Automaten, der
äquivalent ist.
Also insofern gilt dieser Satz.
Und das heißt, die Sprachklassen sind identisch.
Und wir haben also jetzt diese Erkenntnis aus diesem Kapitel, dass die
Typ -3-Sprachen, die also von rechtslinearen Grammatik erzeugt werden
können, identisch sind zu den Sprachen, die von deterministischen
endlichen Automaten erkannt werden können.
Identisch sind zu denen, die durch nicht-deterministische endlichen
Automaten erkannt werden können.
Identisch sind zu den regulären Sprachen, die ausgehend von
Basismengen durch endlich häufige Anwendung von Vereinigung, Produkt
und Iteration erzeugt werden.
Und das ist schließlich die Menge der Sprachen, die durch reguläre
Ausdrücke beschrieben werden können.
Damit haben wir jetzt für die generative Methode, die akzeptierende
Methode oder analysierende Methode und die operative Methode drei
Varianten zur Verfügung, um ein und dieselbe Sprachklasse zu
beschreiben.
Und das heißt, je nach Aufgabe, die wir zu bearbeiten haben, können
wir uns aussuchen, ob wir eine Grammatik nehmen, einen Automaten oder
einen regulären Ausdruck.
Und es gibt Problemstellungen, wo wir genau diese Form nehmen oder
genau diese Form, wenn wir etwas über die Struktur sehen wollen,
nehmen wir einen regulären Ausdruck.
Wenn wir feststellen wollen, ob Wörter zur Sprache gehören, brauchen
wir einen Automaten.
Wenn wir Wörter erzeugen wollen an der Sprache, brauchen wir eine
Grammatik.
Wir können einfach hin und her schalten zwischen diesen drei
Möglichkeiten.
Also insofern können wir hier viele Sachen machen.
Wir haben also jetzt hier eben auch die Möglichkeit, Aussagen zu
machen, basierend auf einer formalen Beschreibung.
Die gelten dann für die Klasse insgesamt.
Und wir wählen also immer die günstigste Art der Sprachdefinition.
Man wählt, wenn man eine Fragestellung hat, immer das Modell des
Objektes, über das man eine Aussage machen möchte, das am besten
geeignet ist, um diese Frage zu beantworten.
Das gilt ganz generell.
Und hier haben wir die Möglichkeit, zwischen drei verschiedenen
Modellen zu wählen.
Sie werden das später noch sehen, wenn wir über Buhl'sche Funktionen,
über Schaltfunktionen, Bau von Hardware für Rechner reden.
Da können Sie auch diese Funktionen auf unterschiedliche Art und Weise
beschreiben.
Durch eine Wertetabelle, durch einen Buhl'schen Ausdruck oder durch
ein Binary Decision Diagram.
Oder Benährungsentscheidungsdiagram.
Und das sind unterschiedliche Arten, in dem Fall Funktionen zu
beschreiben.
Hier haben wir Sprachen beschrieben.
Und man wählt immer für die Aufgabe das geeignetste Modell.
Und das ist etwas, was Sie lernen müssen, wenn Sie eine Fragestellung
der realen Welt untersuchen müssen.
Erstmal, wie kann ich dieses Phänomen der realen Welt modellieren?
Was ist die geeignete Modellierung?
Was ist das?
Handelt es sich um ein Sprachproblem?
Handelt es sich um ein Funktionsproblem?
Und dann wählen Sie das geeignete Modell, um Ihre Frage zu
beantworten.
Und hier habe ich Ihnen das zeigen können, dass man je nachdem, welche
Art Frage man hat, gehört ein Wort zu einer Sprache?
Oder kann ich ein Wort erzeugen aus einer Grammatik?
Wie sehen die, wie muss ich die Wörter erzeugen?
Oder wie ist eigentlich die Struktur der Wörter, die ich in der
Sprache drin habe?
Sie haben jeweils unterschiedliche Modelle, die Sie betrachten können.
Und das ist etwas, was Sie in vielen realen Anwendungen haben.
Deswegen ist das sehr praxisrelevant.
Das wollen Sie später an vielen praktischen Problemen machen, dass Sie
in der Lage sind, systematisch ein Problem zu lösen, Antworten zu
finden, die belastbar sind, die Sie also anderen vermitteln können und
die können das einsehen, dass das eine richtige Antwort ist, weil Sie
ein geeignetes Modell gewählt haben.
Also insofern hier ein ganz einfaches Beispiel.
Die rechtslinearen Grammatiken, endlichen Automaten, sind einfache
mathematische Konstrukte zur Beschreibung von relativ einfachen
Sprachen.
Das ist das, was ich Ihnen hier vermitteln wollte.
Das sind die Erkenntnisse dieses Kapitels.
Deterministische und nicht-deterministische endliche Automaten sind
gleichmächtig.
Erste Erkenntnis in diesem Fall, für diese Art Modell ist Nicht
-Determinismus ein ganz praktisches Phänomen, kann ich nutzen.
Aber es bringt mich von der Ausdrucksfähigkeit nicht weiter.
Die haben die gleiche Ausdrucksstärke.
Wir haben mit dem Pumping Lemma gezeigt, es gibt durchaus Sprachen,
die wir nicht durch diese Modelle beschreiben können.
Das heißt, insbesondere können wir Sprachen mit Klammerschachtelungen
nicht von endlichen Automaten erkennen.
Das heißt, wir haben noch nicht die Sprachklasse, die wir brauchen, um
Programmiersprachen zu beschreiben, weil wir dort immer irgendwelche
Klammerschachtelungen drin haben, in irgendwelchen arithmetischen
Ausdrücken, oder wenn Sie Funktionen oder Methoden oder Objekte
beschreiben, Sie haben immer irgendwelche Klammerschachtelungen da
drin.
Dann wissen wir, dass die rechtslinearen Grammatiken und regulären
Ausdrücke nichts anderes bringen, aber eben andere Arten, also
Eigenschaften auszudrücken.
Und wir wissen auch, dass wir Automaten effizient machen können, in
dem Sinne, dass wir die Anzahl der Zustände reduzieren auf die minimal
erforderliche Anzahl von Zuständen.
Und dann haben wir bis auf Isomorphie eindeutigen, reduzierten
Automaten.
Haben wir also schon viel gelernt in diesem Kapitel.
Und einige dieser Themen werden uns natürlich weiter verfolgen, in den
nächsten Kapiteln.
Das ist also das Kapitel Nummer zwei gewesen, in dem wir uns
beschäftigt haben mit dieser sehr einfachen Sprachklasse.
Und jetzt kommen wir zum nächsten Kapitel, zu den Kellerautomaten und
kontextfreien Sprachen.
Und wo sind wir hier?
Genau, ich will von Beginn an das machen.
Kellerautomaten.
Wenn Sie das Buch angeschaut haben, dann werden Sie festgestellt
haben, dass wir da mit einer ganz allgemeinen Art von Automaten
anfangen, nämlich mit den Turing-Maschinen.
Allgemeinste Art von Automaten.
Und haben dort die Mächtigkeit dieser Turing-Maschine sukzessive
weiter eingeschränkt.
Und die nächste Klasse war dann der Kellerautomat.
Und wir hatten ja gesehen, in dem Buch gehen wir dann am Ende auf die
endlichen Automaten als die einfachste Art von Automaten, mit denen
man irgendetwas berechnen kann.
Die Idee war ja da, in dem Buch haben wir das Beispiel genommen, wir
wollen Primzahlen berechnen oder testen, welche Zahlen Primzahlen
sind.
Wir wollen eine Sprache haben, die gerade im Prinzip alle Primzahlen
enthält.
Wir hatten gesehen, das ist gar nicht so einfach.
Wir hatten hier festgestellt im vorigen Kapitel, die endlichen
Automaten sind nicht ausreichend.
Für gewisse Sprachen brauchen wir die Möglichkeit, etwas zu zählen und
etwas mehr zu merken, als wir das mit dieser endlichen Anzahl von
Zuständen können.
Da hatten wir ja nur diese Steuereinheit mit endlich vielen Zuständen
und wir haben das Eingabeband, auf dem wir ein Wort stehen haben, das
wir abarbeiten.
Und das reicht ja nicht aus.
Wir wollen gerne zählen können oder uns merken können, was auf dem
Eingabeband steht.
Und dazu fügen wir jetzt ein sehr spezielles Speichermedium hinzu,
einen sogenannten Kellerspeicher.
Was ist ein Kellerspeicher?
Ich male den einfach mal hier daneben.
Wenn Sie einen Keller haben, in dem Fall sieht es aus wie eine Grube,
was machen Sie dann?
Sie können dort irgendetwas reinlegen.
Dann liegt das da unten.
Dann legen Sie noch etwas da rein, dann liegt das oben drauf.
Dann liegt da noch etwas drauf und noch etwas oben drauf.
Und wenn Sie von oben drauf gucken, sehen Sie immer nur das, was Sie
oben drauf gelegt haben.
Das heißt, wenn Sie jetzt wieder etwas rausholen wollen, dann können
Sie das rausholen, was oben drauf gelegen hat.
Das heißt, das ist das Prinzip Last in, First out.
LIFO-Prinzip.
Das ist das Prinzip eines Kellers.
Oder eines Stapels, bei dem Sie etwas immer oben drauf legen.
Und das, was als letztes draufgelegt wurde, das können Sie sehen und
können das auch wieder runternehmen.
Das ist ein Keller.
Und der ist hier angedeutet durch dieses Speichermedium.
Hier unten ist das unterste Zeichen, ein K0.
Und dann stehen hier irgendwelche anderen Zeichen drauf.
Offensichtlich brauchen wir hier jetzt noch etwas mehr.
Wir brauchen ja nicht nur Zustände und Zeichen, die auf dem
Eingabeband stehen können, sondern auch Zeichen, die auf dem
Kellerband stehen können.
Und das machen wir jetzt formal.
Also habe ich gerade gesagt, Last in, First out.
Das machen wir jetzt formal und schreiben das dann gleich auf.
Oder formal kommt es auf der nächsten Folie.
Wir brauchen also Zustandsübergänge.
In dem Fall, die werden abhängig davon, was wir hier als aktuellen
Zustand S haben, was wir hier gerade auf dem Eingabeband lesen und was
wir als oberstes Zeichen auf dem Keller haben.
Das wird also jetzt bestimmen, was wir als nächstes tun.
Also die Arbeitsweise des Auto- und Kellerautomaten wird so aussehen,
dass wir uns anschauen, was sind die Informationen, die uns zur
Verfügung stehen, um zu entscheiden, was wir als nächstes machen.
Das ist der aktuelle Zustand, das Zeichen unter dem Lesekopf und das
oberste Kellerzeichen.
Und dann wollen wir etwas tun.
Und etwas tun heißt, wir können jetzt oben auf dem Eingabeband das
nächste Zeichen anschauen, das kennen wir ja schon.
Wir können auch in einem neuen Zustand übergehen, aber wir können auf
dem Keller etwas tun.
Wir können das oberste Kellerzeichen, das hier steht, das können wir
ersetzen durch ein Wort.
Wir können also irgendein Wort uns hernehmen
und können das praktisch hier reinschreiben und schreiben das
praktisch oben drauf.
Ersetzen das oberste Zeichen durch ein Wort über dem Kelleralphabet.
Wir schreiben das U dort hinein.
Man redet häufig, wenn man über einen Kellerspeicher redet, von zwei
Operationen, die man ausführen kann.
Das eine ist eine Push-Operation.
Ich kann etwas hineinschieben, das ist das, was ich hier angedeutet
habe.
Ich kann ein Wort dort hineinschieben.
Das andere ist eine Pop-Operation.
Ich werfe das oberste Kellerzeichen weg, aber nur das oberste
Kellerzeichen.
Also ich ersetze das oberste Kellerzeichen durch das leere Wort.
Dadurch habe ich dann das oberste Kellerzeichen gelöscht.
Und damit habe ich eigentlich die Operationen charakterisiert, wegen
dieses Push.
Ich habe das Push genannt, weil sie in der Literatur häufig die
Bezeichnung Pushdown-Stack haben.
Ein Pushdown-Stack ist ein Kellerspeicher.
Also Kellerautomaten im Englischen heißen Pushdown-Autometer.
Das sind also Automaten mit Kellerspeicher.
Und dieser Schreiblesekopf, das Band des Kellers natürlich, steht
immer auf dem obersten Kellerzeichen.
Das ist genau dieses LIFO-Prinzip.
Und die formale Definition, die finden Sie jetzt hier.
Das heißt, wir haben neben dem Eingabealphabet und der Zustandsmenge
jetzt noch ein Kelleralphabet.
Zeichen, die wir auf den Keller schreiben können.
Das können die gleichen sein wie auf dem Eingabeband, können aber auch
andere sein.
Und dann brauchen wir natürlich nach wie vor die Übergangsfunktion,
Anfangszustand und wir brauchen ein Zeichen, das wir verwenden, um
festzustellen, dass wir einen leeren Keller haben.
Das heißt, wenn wir das Zeichen K0 sehen hier unten, das zu Anfang
immer draufsteht auf dem Keller, dann wollen wir damit praktisch
ausdrücken, naja, dieses Zeichen K0 sagt uns oben, wir haben also
alles, was wir mal reingeschrieben hatten, ist schon wieder weg oder
wir haben überhaupt noch nichts reingeschrieben, da ist nur das K0
drin.
Das ist das Kellerstartzeichen.
Wir haben wieder eine endliche Menge von Endzuständen oder nicht
leere, endliche Menge von Endzuständen natürlich, Zustandsmenge ist ja
endlich und wir haben eine partielle Übergangsfunktion.
Die muss nicht unbedingt vollständig sein und was erstaunlich ist, wir
haben nicht nur Übergänge für Eingabesymbole auf dem Eingabeband,
sondern auch für das leere Wort.
Das bedeutet, erkläre ich Ihnen gleich.
Also, Bedingung ist, also erstmal partielle Übergangsfunktion heißt,
wir haben nicht für jede Kombination von Zustand, Eingabezeichen und
Kellerzeichen einen Übergang.
Und wenn für einen Zustand ein Eingabezeichen oder ein Kellerzeichen
der Übergang definiert ist, der Übergang wird darin bestehen, dass wir
einen Folgezustand haben und wissen, was wir auf den Keller schreiben
müssen, dann darf es keinen Übergang geben für das leere Wort.
Das heißt, dann darf es keinen Übergang geben, bei dem wir für einen
Zustand mit dem leeren Wort etwas im Keller schreiben können.
Warum macht man das?
Weil wir sicherstellen, also ich habe gesagt, das leere Wort ist auch
eine Möglichkeit.
Zustand, leeres Wort anstelle des Eingabesymbols und Kellerzeichen
bedeutet, wir ignorieren das, was auf dem Band steht und arbeiten
erstmal ein bisschen im Keller.
Sie werden gleich Beispiele sehen, wie man das einsetzt.
Und das heißt, ich möchte hieraus einen deterministischen
Kellerautomaten machen.
Und deterministisch heißt, ich habe nur eine Möglichkeit, etwas zu
tun.
Das heißt, ich kann entweder in einem Zustand ein Eingabezeichen lesen
und etwas auf dem Keller machen oder in einem Zustand, was auf dem
Eingabeband ist, ignorieren und nur im Keller arbeiten.
Ich habe aber nicht die Alternativen, das wahlweise zu machen, sondern
ich kann nur das eine machen oder das andere.
Wir werden später sehen, wir werden auch hier zum Kellerautomaten,
auch nicht deterministische Automaten definieren.
Da ist das dann egal, dann haben Sie mehrere Übergangsmöglichkeiten.
Hier brauchen wir das, dass er deterministisch ist, dass wir also
nicht wechseln können zwischen dem nur Arbeiten auf dem Keller und
dabei auch Zustände verändern und Verarbeiten von Zeichen auf dem
Band.
Falls entsprechend ein Übergang für das Lambda definiert ist, dann
wird halt das Eingabeband ignoriert und es wird nur auf dem Keller
gearbeitet.
Sie werden dafür gleich Beispiele sehen.
Und ohne die Bedingungen wäre der Automat nicht deterministisch und
wir wollen hier einen deterministischen Automaten haben.
Natürlich ist das ein Automat ohne Ausgabe, beziehungsweise wir können
nur unterscheiden, ob Zustände Endzustände oder nicht Endzustände
sind.
Also diese eingeschränkte Art der Ausgabe, das hatten wir ja schon mal
gesehen.
Und das ist jetzt also die Arbeitsweise gleich eines Kellerautomaten.
Ich sehe, es ist kurz vor neun Uhr, es ist Zeit für eine Pause.
Damit machen wir wieder kurze Pause.
Es gibt noch eine Frage, die ich noch kurz beantworten kann.
Ah, sehen Sie, da habe ich geahnt, dass die Frage kommt.
Es hatten sich eigentlich zwei Studenten gemeldet, oder ein Student
gemeldet, der wollte eine kurze Ansage machen.
Da kommen Sie schon.
So, das war jetzt mal eine etwas andere Pause.
Keine Frage zwischendurch, sondern noch mal ein Werbeblock.
Noch eine dieser wichtigen Aktivitäten der Wirtschaftsingenieure,
eigene Unternehmensberatung aufzumachen.
Da können Sie eben schon viel Erfahrungen sammeln, bezüglich Themen,
die Ihnen später im Beruf auch begegnen werden.
So, wir kommen damit dazu, das jetzt weiter zu definieren.
Also wir hatten gerade, das war hier die letzte Folie gewesen, ich
hatte Ihnen den Automaten definiert, formal.
Jetzt müssen wir sehen, wie der arbeitet.
Zu Beginn ist der Automat im Zustand S0, der Lesekopf über dem
linkesten Zeichen und der Keller enthält nur dieses Zeichen K0, das
ist das Anfangszeichen.
Und dann ist dieser, also der ist im Zustand, hat das Zeichen E, sieht
das oberste Kellerzeichen K, dann ist es möglich, dass er weder für
SEK noch für SLK einen Übergang hat.
Und das heißt, der Automat weiß nicht, was er machen soll, der hält
einfach an.
Parzell definiert, der Automat hält eben dann einfach an.
Die andere Möglichkeit ist, dass er weiß, was er tun muss, wenn er ein
Zeichen E liest im Zustand S und das Zeichen K als oberstes
Kellerzeichen, dann geht er in den Zustand S', ersetzt das K durch das
V und das linkeste Zeichen, also wenn das hier das Zeichen V ist, das
linkeste Zeichen hier, das ist dann das oberste Kellerzeichen.
Das erste Zeichen des Wortes ist dann das oberste Kellerzeichen.
Das heißt, das wird dann entsprechend so in den Keller
reingeschrieben.
Und der Lesekopf geht dann entsprechend eine Position weiter.
Die andere Möglichkeit ist, dass wir einen Übergang haben für das
leere Wort und dann haben wir nur einen Zustandsübergang, schreiben
etwas im Keller und machen weiter.
Das sind die beiden Möglichkeiten.
Und wie können wir jetzt definieren, dass ein Wort akzeptiert wird?
Na ja, wenn, nach dem Halten, das ist wichtig natürlich.
Wir müssen anhalten, das heißt, diese Situation hier muss eintreten,
dass wir nicht weitermachen können.
Es gibt also weder einen Übergang mit dem Eingabezeichen, noch einen
Übergang mit dem leeren Wort.
Und wenn wir gehalten haben und der Lesekopf oben auf dem Eingabeband
rechts von W steht, das heißt, das Wort ist vollständig eingelesen
worden und der Automat ist im Endzustand, dann wird das Wort
akzeptiert.
Jetzt ist die Frage, wie kommen wir da hin?
Wir haben nur das Verhalten für einzelne Zeichen definiert, da müssen
wir eigentlich wieder einmal die Arbeitsweise über Konfigurationen
beschreiben.
Das machen wir wieder auf der nächsten Folie.
Was ist also eine Konfiguration?
Was war eine Konfiguration nochmal?
Das war das, was wir brauchen an Informationen, um festzulegen, was
das betrachtete System von jetzt an weitermachen wird.
Welche Informationen beeinflussen das weitere Verhalten eines
Kellerautomaten?
Naja, das ist der aktuelle Zustand, der Zustand S.
Das ist das, was auf dem Eingabeband noch bearbeitet werden, noch
abgearbeitet werden muss.
Und es ist natürlich alles das, was aktuell hier im Keller steht.
Weil wir ja durch weitere Operationen, wenn wir mehrfach Push machen,
kommen wir an alle diese Informationen, die dort aktuell drinstehen,
irgendwann vielleicht noch ran.
Das heißt, der gesamte Kellerinhalt ist wichtig für das weitere
Verhalten dieses Automaten.
Zustand, Eingabezeichen, nicht ein Zeichen, sondern das verarbeitende
Restwort.
Alles, was noch auf dem Band steht, ab der aktuellen Position auf dem
Eingabeband.
Das war das, was wir brauchten für den endlichen Automaten.
Und jetzt brauchen wir eben noch den Kellerinhalt mit dazu.
Weil der auch beeinflusst, was wir im Weiteren machen können.
Und dann brauchen wir genauso wieder eine Übergangsfunktion oder
Übergangsrelation zwischen Konfigurationen.
Und es ist klar, dass wir also dann zwei Möglichkeiten haben.
Es kann sein, dass wir einen Übergang haben, wo wir ein Zeichen auf
dem Eingabeband berücksichtigen.
Dann wird also das aktuelle Zeichen hier verarbeitet.
Das heißt, das Restwort ist anschließend W.
Wir gehen in den Zustand S-Strich über und haben das K ersetzt durch
das V-Strich.
K wird durch V-Strich ersetzt, da sehen Sie das.
Es steht also anschließend V-Strich V auf dem Band.
Also alles, was unter dem obersten Zeichen K auf dem Kellerband stand,
war das V.
Und anschließend also V-Strich V dort drin.
Und wenn wir eben mit leerem Wort den Übergang machen, dann bleibt
natürlich das Restwort unverändert.
Wir bewegen ja den Gläserkopf nicht weiter und damit haben wir dann
auch eine Folgekonfiguration.
Also zwei verschiedene Arten der Übergänge.
Wir können das natürlich dann auch wieder beliebig häufig machen.
Da haben wir wieder die reflexiv-transitive Hülle, das kennen Sie.
Wir schreiben Stern dran und machen das dann beliebig oft.
Wir lassen diese Ka darunter, diese Bezeichnung für den Automaten
meistens weg.
Auch das wissen Sie.
Und nochmal, wann akzeptiert der Kellerautomat ein Wort?
Wenn wir von der Anfangskonfiguration, nämlich Startzustand, linkestes
Zeichen des Eingabewortes und leerer Keller, beziehungsweise nur das
K0, das Anfangskeller-Symbol ist drauf, in eine Konfiguration
übergehen, am Ende S Lambda V.
Wir haben das Wort auf dem Band vollständig abgearbeitet, sind neben
dem rechtesten Zeichen.
Im Keller kann auch irgendetwas stehen, ist also egal, ob der Keller
leer ist oder nicht, der kann auch ziemlich voll sein und trotzdem
werden wir dieses Wort akzeptieren, weil wir in einem Endzustand
angelangt sind und nicht mehr weitermachen können.
Wenn wir nicht mehr weitermachen können und in einem Zustand sind, der
Nicht -Endzustand ist, wird das Wort nicht akzeptiert.
Also, das zu der Sprachdefinition, beziehungsweise jetzt kommt die
Sprachdefinition, jedes Wort ist drin, das wir akzeptieren können.
Ich hoffe, es geht jetzt wieder.
Noch ein kleines Beispiel, wichtiges Beispiel hier.
Wir machen einen Automaten, Kellerautomaten bauen wir uns jetzt und
der soll folgende Übergänge haben.
Also, wir müssen angeben, wie das Delta von diesem Triple aussieht.
S0, A und K0.
Auf dem Eingabeband steht ein A und auf dem Keller steht nur das K0.
Die reflexiv-transitive Hülle hatte ich Ihnen schon mal erzählt, schon
mehrfach.
Wir können beliebig oft einen Konfigurationsübergang machen.
0x, 1x, 17x, so oft Sie es wollen.
Konfigurationsübergänge, sofern sie entsprechend der Definition des
Automaten möglich sind.
Das ist die reflexiv-transitive Hülle.
So, wir wollen jetzt einen Automaten konstruieren und wir sagen, wir
lesen auf dem Band ein A und schreiben das in den Keller.
Hier ist unser Keller.
Schreiben da ein A rein, also das K0 schreibe ich mal hier drunter.
Das ist ja immer da unten drunter, das K0.
Schreiben ein A da rein und bleiben in dem Zustand.
Jetzt lesen wir auf dem Band noch ein A und schreiben das auch einfach
in den Keller rein.
Also wir ersetzen das, was das oberste Zeichen A, was ja im Keller
war, ersetzen wir durch zwei As.
Das heißt, wir schreiben ein weiteres A dort hinein.
Dann kann es sein, dass wir vielleicht ein B lesen.
Wenn wir ein B lesen und oben auf dem Keller steht ein A, dann gehen
wir in einen anderen Zustand, den Zustand S1 und schreiben das leere
Wort.
Das heißt, wir löschen dieses A dort raus.
Stellen Sie sich vor, wir haben hier den Übergang nochmal.
Wenn wir den nochmal machen, werden wir wieder ein B hier hätten.
Das muss ich aber wieder schreiben.
Also Radierer durch den Stift ersetzen.
Stellen Sie sich vor, wir hätten hier noch ein B.
Dann müssen wir zu unserem Zustand S1 gehen erstmal.
S1 und wir lesen nochmal ein B.
Dann würden wir dieses A wieder löschen.
Wir würden also wieder ein A löschen.
Und jetzt könnte es ja sein, dass wir im Zustand S1 sehen wir auf
einmal das oberste Kellerzeichen K0.
Wenn wir im Zustand S1 das K0 lesen.
Oben hatten wir bei S0 das oberste Kellerzeichen K0 gesehen.
Aber da haben wir das Zeichen A verwendet oder das A gelesen.
Wenn wir im S1 sind und lesen das oberste Kellerzeichen K0 im Keller,
dann machen wir auf dem Eingabenband nichts, sondern gehen in einen
Zustand S2.
Und S2, Stand hier oben, soll ein Endzustand sein.
Wenn das ein Endzustand ist, und das ist der gesamte Automat, den ich
Ihnen definiere, dann heißt das für S2 gibt es keinen Folgezustand und
wir haben dieses Wort hier akzeptiert.
Mit diesem Automaten.
Und Sie werden schon sehen, oder das erkennen Sie eigentlich sofort,
das ist genau ein Automat, der diese Sprache erkennen kann, A hoch N,
B hoch M.
Also wir haben eine deutliche Erweiterung der Erkennungsmöglichkeiten.
Wir können die Sprache A hoch N, B hoch M erkennen, die wir vorher ja
gar nicht erkennen konnten.
Gibt es eine Frage?
Also, wenn mehr A's gelöscht werden sollen, als im Kellerspeicher
sind, wenn hier also noch ein B stehen würde, dann hätten wir S1, wir
würden in dem Fall, wenn wir das K0 sehen, würden wir aufhören.
Wir hätten bis hierhin gelesen, diesen Teil, wir würden das oberste
Zeichen K0 sehen und hätten jetzt den Übergang zu machen auf S2 K0.
Von dem aus geht es nicht weiter, wir sind in einem Endzustand, können
nicht weitermachen.
Aber wir haben das letzte B hier noch nicht gelesen.
Das heißt, wir haben das Wort nicht voll abgearbeitet, das heißt,
dieses Wort kann nicht akzeptiert werden.
Also A², B hoch 3 würde nicht akzeptiert werden, weil wir das B ja gar
nicht lesen würden.
Wir würden ja in dem Augenblick, wo wir den leeren Keller haben, das
heißt, wir sehen das Kellerstartsymbol K0 in dem Zustand S1, in dem
Augenblick gehen wir in den Endzustand und machen oben auf dem
Eingabeband nicht mehr weiter.
Das heißt, das Wort mit drei Bs würde nicht akzeptiert werden.
Genauso, wenn wir hier nur ein B hätten, könnten wir oben nicht
weitermachen.
Wir hätten keine weiteren Zeichen, wir hätten S1, kein Zeichen zu
lesen, das heißt, es müsste ein Übergang da sein, der ein Übergang mit
Lambda ist.
Wir haben aber nicht das oberste Kellerstartzeichen K0.
Das heißt, der Automat würde anhalten und wir hätten aber keinen
Endzustand.
Wir wären nicht nach S2 gegangen.
Also man muss sich natürlich alle diese Überlegungen machen, um zu
zeigen, dass das tatsächlich genau diese Sprache ist, die man da
erzeugt.
Also Konfigurationsübergänge für A hoch 3, B hoch 3 wären also genau
diese hier.
Warum wären das genau die, wenn wir A hoch 3, B hoch 3 drauf stehen
haben?
Würden wir eben zunächst mal die As in den Keller schreiben, dann
haben wir hier A hoch 3, K0 stehen, ich habe das hier für A Quadrat, B
Quadrat gemacht.
Und dann würden wir mit dem B in Zustand S1 gehen, würden die As
sukzessive streichen und hätten dann schließlich die drei Bs
abgearbeitet und würden dann mit S1 Lambda, K0 weitermachen auf S2 und
hätten dann entsprechend, also das ist jeweils die Konfiguration S1,
Zustand S1, es ist nichts mehr zu bearbeiten, Restwort ist leer und
wir haben oben K0 stehen, dann gehen wir nach S2, Restwort ist leer
und wir haben K0 und von S2 aus geht es nicht weiter.
Also da kann man sich sehr leicht überlegen, dass das genau diese
Sprache ist und dass jede andere Kombination von As und Bs zu einem
Zustand führt oder zu einer Konfiguration führt, aus der wir nicht
weitermachen können.
Okay, noch eine Frage.
Was passiert, wenn nach dem B noch ein A eingelesen wird?
Schauen wir uns auch das nochmal an.
Dazu muss ich da wieder kurz rauf gehen.
Also, wenn nach den Bs noch ein A eingelesen wird, also nehmen wir an,
wir hätten hier ein A stehen, was würde dann passieren?
Wir hätten ja AA und BB eingelesen oder hätten, ich nehme mal ein
anderes Wort, nehmen wir hier A, B und dann hier ein A nochmal dazu,
was würde dann passieren?
Naja, in dem Augenblick, wo wir hier ein A stehen haben, sind wir
aber, weil wir das B vorher gelesen hatten, im Zustand S1.
Wir waren von dem S0 aus mit B in den Zustand S1 übergegangen.
Wenn wir im Zustand S1 sind, gibt es aber nur Übergänge für die
Zeichen A.
Für das Zeichen A gibt es von S1 aus keinen Übergang.
Das heißt, wir können, nachdem wir ein B eingelesen haben, kein
weiteres A mehr verarbeiten, weil es dafür keinen Übergang gibt.
Der Automat hält an, ist aber nicht im Endzustand.
Das heißt, ein solches Wort würde nicht akzeptiert werden, selbst wenn
die Anzahl der As und Bs identisch wäre.
Sie können aber durchaus einen Kellerautomaten angeben, der Wörter
dieser Art auch erkennen würde, bei der die Anzahl der As und der Bs
identisch ist.
Das können Sie auch machen, dann müsste es aber etwas anders aussehen.
Müssten Sie den anders definieren.
Also, das zu diesen Automaten.
Und das ist nochmal hier allgemein angegeben, hatte ich Ihnen gerade
eben für das A hoch 3, B hoch 3 gezeigt.
Können also die ersten As alle in den Keller schreiben, mit den Bs die
As aus dem Keller wieder löschen und anschließend in den Endzustand
gehen.
Und jede andere Kombination von Zeichen auf dem Eingabeband führt zu
Situationen, aus denen wir nicht zu einem Endzustand kommen können.
Oder bei denen wir das Wort nicht vollständig abgearbeitet haben.
Jetzt gibt es sicherlich eine einfache Möglichkeit, diesen Satz
einzusehen, dass Sie für jeden endlichen Automaten einen
deterministischen Kellerautomaten angeben können.
Sie ignorieren einfach das, was da im Keller steht, dann haben Sie
einen endlichen Automaten.
Also der endliche Automat ist ja hier ein einfacher Teil von einem
solchen Kellerautomaten.
Der endliche Automat braucht den Keller halt nicht.
Der nutzt den Keller nicht aus, damit ist er insbesondere auch ein
Kellerautomat, der aber nicht wirklich eingesetzt wird.
Und entsprechend ist klar, dass jede Sprache, die von endlichen
Automaten akzeptiert werden kann, auch von Kellerautomaten akzeptiert
werden kann.
Und das heißt, wir haben diese Sprachinklusion.
Anderes Beispiel, ein bisschen praktischeres Beispiel.
Wir wollen im Prinzip arithmetische Ausdrücke beschreiben können.
Ich gebe Ihnen auch gleich noch ein Beispiel für wirklich
arithmetische Ausdrücke.
Das, was ich mir jetzt abstrakt nochmal anschaue, sind
Klammerstrukturen.
Was für Klammerstrukturen haben wir?
Ich habe hier eckige Klammern angegeben, ich kann auch andere angeben,
ist egal.
Was ist eine Klammerstruktur?
Das wären ein paar von Klammern.
Es kann aber auch sein, dass ich dahinter nochmal ein paar von
Klammern habe.
Oder vielleicht außen drum Klammern.
Und wir sehen, das sind also etwas kompliziertere Sachen als nur A
hoch N, B hoch N.
Das heißt, ein Klammerausdruck, ein wohlgeformter Klammerausdruck, ist
ein Wort, bei dem die Anzahl der öffnenden Klammern gleich der Anzahl
der schließenden Klammern ist.
Das muss sicherlich der Fall sein, aber das reicht natürlich nicht
aus.
Denn wenn ich erste schließende, dann öffnende hätte, das würden wir
nicht akzeptieren wollen.
Es muss also für jede Zerlegung des Wortes, also das war unser Wort,
jetzt schauen wir uns irgendeine Zerlegung an und zählen die
schließenden und die öffnenden Klammern.
Und es darf für jedes Anfangsstück U, die Anzahl der schließenden
Klammern, nicht größer sein als die Anzahl der öffnenden Klammern.
Bei dem Beispiel hier wäre das verletzt.
Da wäre nämlich eine schließende Klammer da und es war noch keine
öffnende da.
Also, wenn Sie von links nach rechts durchlaufen und Sie zählen
einfach nur die Anzahl der öffnenden und subtrahieren immer eine 1,
wenn Sie eine schließende Klammer sehen, dann dürfen Sie nie einen
Wert haben, der negativ wird.
Dann wäre nämlich die Anzahl der schließenden Klammern größer als die
Anzahl der öffnenden Klammern.
Die Art und Weise haben Sie also eine einfache Möglichkeit zu
überprüfen, ob das eine richtige Klammerschachtelung ist.
Also das sind hier wohlgeformte Klammer ausdrücklich hier oben.
Und hier unten ist keiner, eine öffnende, zwei schließende und danach
noch eine öffnende.
Da hätten wir also, wenn wir zählen von links nach rechts, hätten wir
1, 0, minus 1 und dann hätten wir eine 0.
Aber insgesamt ist die Anzahl der öffnenden und der schließenden
gleich, aber eben nicht wohlgeformt.
Und solche Automaten, dafür wollen wir uns auch einen Automaten
überlegen, ist ein bisschen komplizierter als das, was wir gerade
gesehen haben für A auch in B hoch N.
Und wie könnte man das machen?
Der Automat muss also als Eingabezeichen diese Klammern haben.
Das haben wir hier, diese eckigen Klammern.
Er braucht nur zwei Zustände.
Er hat wieder seinen Start, dieses Kellersymbol.
Im Anfangszustand, also wenn wir jetzt hier irgendeinen
Klammerausdruck haben, wenn er eine öffnende Klammer sieht, also für
eine schließende im Zustand S0 brauchen wir nichts zu machen, weil ein
wohlgeformter Klammerausdruck nicht beginnen kann mit einer
schließenden Klammer.
Er beginnt mit einer öffnenden Klammer und dann schreiben wir die rauf
und gehen in einen neuen Zustand.
Die erste Klammer ist auf den Keller gelegt worden.
Dann sehen wir in diesem Zustand vielleicht eine weitere Klammer.
Also wir hätten jetzt so etwas und dann vielleicht noch eine weitere
Klammer.
Dann würden wir diese Klammer auch raufschreiben auf den Keller.
Wir würden also das oberste Zeichen ersetzen durch das Wort, das aus
zweieckigen Klammern besteht.
Und wenn jetzt eine schließende Klammer kommt, dann würden wir
entsprechend eine öffnende Klammer aus dem Keller rausstreichen.
Und das ist dieser Übergang.
Und wenn wir feststellen, wir sind in diesem Zustand und wir haben
jetzt alle öffnenden Klammern wieder rausgestrichen, dann gehen wir
zurück, machen wir einen Lambda-Übergang.
Also wenn wir im Zustand S1 das Kellerstartzeichen sehen, dann gehen
wir zurück in S0 und lassen das Kellerstartzeichen stehen.
Und das heißt, jetzt könnte nochmal eine öffnende Klammer kommen,
nochmal eine schließende Klammer und so weiter.
Oder es könnten hier auch mehrere öffnende Klammern kommen, es könnte
eine schließende Klammer kommen, es könnte eine öffnende kommen, eine
schließende kommen und dann vielleicht nochmal die schließende
Klammer.
Und das wäre ein wohlgeformter, nicht schön geschrieben, aber
wohlgeformter Klammerausdruck.
Das heißt, etwas anders als vorher bei dem A hoch N, B hoch N.
Es kann eben sein, dass wir da mehrere solcher Klammerschachtlungen
nacheinander kriegen und wir müssen eben einfach nur zählen können.
Das Zählen machen wir mit dem Keller.
Also dieses Wort hier kann man dann eben ganz einfach abarbeiten,
indem man der Reihe nach das, was hier steht, in den Keller schreibt,
die öffnende Klammer in den Keller, dann haben wir hier eine
schließende Klammer, entsprechend wird sofort diese öffnende Klammer
wieder gelöscht aus dem Keller und die nächste Konfiguration ist dann
so, dass wir das Kellerstartzeichen sehen, wir gehen in Zustand S0 und
sehen wieder eine öffnende Klammer, schreiben die Klammer rein,
löschen sie, weil wir die schließende Klammer sehen, und sehen
anschließend das Kellerstartzeichen, machen den Übergang nach S0
und brauchen nichts mehr zu lesen, wir sind fertig und sind in K0, das
heißt wir haben nichts mehr zu lesen, es gibt keinen Lambda-Übergang
von S0 aus, das heißt der Automat macht nicht mehr weiter und wir sind
damit dann fertig.
So, damit haben wir also dann solche Klammerausdrücke akzeptiert, auch
das können Sie sich hier alles im X-Wizard anschauen, will ich aber
jetzt nicht explizit machen, ich denke, das Werkzeug können Sie gut
einsetzen.
Machen Sie ja auch in den Übungen intensiv, also insofern lernen Sie
das alles.
Und jetzt habe ich hier eine andere Sprache, wir wollen einen
Kellerautomaten nochmal konstruieren für eine gewisse Sprache, und die
sieht jetzt ein bisschen anders aus.
Eine Sprache, bei der die Wörter folgende Form haben, also zum
Beispiel 0 1 C 1 0 wäre ein solches Wort.
V, C, V' und das V' soll die Spiegelung von V sein, also 0 1 C 1 0.
So was nennt man auch Palindrom.
Sie können das von links und rechts gleich lesen, das ist das gleiche
Wort.
Offensichtlich ist das etwas, was man hervorragend mit einem Keller
machen kann.
Sie schreiben einfach dieses Wort in den Keller, also jedes Zeichen
davon schreiben Sie in den Keller, wenn Sie hier einen Keller haben,
würden Sie hier haben Sie Ihre K0 hier unten stehen, und da schreiben
Sie erst die 0 da rein, dann die 1.
Wenn Sie das C lesen, dann wissen Sie, aha, jetzt muss also die
Umkehrung kommen, und wenn dann die 1 kommt, löschen Sie die 1 raus,
wenn die 0 kommt, löschen Sie die 0 raus, und wenn dann das
Kellerstartzeichen wieder zu sehen ist, sind Sie fertig.
Also das ist eine klassische Anwendung eines Kellers, dass Sie etwas
gespiegelt nochmal sehen wollen.
Also der Automat liest das V Zeichen für Zeichen, speichert das im
Keller ab, und sobald das erste und einzige C erscheint, liest er das,
was hinter dem C steht, Zeichen für Zeichen, und überprüft, ob jeweils
das nächste Zeichen auf dem Eingabeband genau das nächste Zeichen oder
das oberste Zeichen im Keller ist.
Wenn es gleich ist, wird gelöscht, weil ich das dann ja gesehen habe.
Bei Ungleichheit bin ich fertig, dafür habe ich keinen Übergang, das
Wort wird nicht akzeptiert.
Also der Automat ist sehr einfach zu konstruieren wieder.
Wir haben einen Anfangszustand S0 mit einem Zeichen E.
Wenn wir das K0 noch sehen, schreiben wir das E dort hinein, bleiben
in dem Zustand S0, schreiben also so lange Zeichen in unseren Keller,
wie wir hier irgendwelche Zeichen sehen, die in 0 oder 1 sind.
In dem Augenblick, wo wir das C sehen, gehen wir in einen neuen
Zustand.
Jetzt müssen wir ja überprüfen, ob die Spiegelung des eingegebenen
Wortes wieder erscheint.
Gehen wir in einen neuen Zustand, verändern den Keller nicht.
Und im Zustand S1 ist nur die Situation interessant, dass das Zeichen
auf dem Band gleich dem obersten Kellerzeichen ist, das wird dann
entsprechend gelöscht.
Und wenn wir auf die Art und Weise zu dem Startkellerzeichen K0
kommen, machen wir einen Lambda-Übergang und gehen in den Endzustand
K0 über.
Und damit sind wir dann damit fertig.
Also das ist ein einfacher Kellerautomat, der einfach dieses Wort da
reinschreibt und entsprechend wieder rausliest.
So kann man das sicherlich machen.
Und jetzt machen wir das noch ein bisschen komplizierter und lassen
das C einfach weg.
Wenn wir das C weglassen, das ist natürlich interessant.
Also zum Beispiel das Wort 0110 wäre ein solches Wort.
V, V' das V' ist eine Spiegelung.
Jetzt kann ich aber auch das nochmal hinschreiben.
Und das erfüllt auch diese Bedingung.
Nur wie kann man das jetzt erkennen?
Sie lesen das Wort, jetzt könnte es natürlich sein, Sie haben hier 01
gelesen, jetzt kommt das 10 wieder, das heißt, da steht ja schon die
Spiegelung des Anfangswortes.
Sie könnten also hier sagen, ich gucke mal, ob das Anfangswort wieder
auftaucht.
Das würde Ihnen hier aber nicht weiterhelfen.
Dann hätten Sie das ganze Wort gar nicht gesehen.
Hier wäre der richtige Punkt.
Da haben Sie also zwei gleiche Zeichen.
Und es könnte sein, dass das hier so ein Umkehrpunkt ist, in dem Fall
wäre das richtig.
Könnte aber auch sein, dass das der richtige ist.
Weil hier entsprechend noch weitere Zeichen kommen.
Das heißt, offensichtlich ist es sehr schwierig, für diese Sprache
festzustellen, an welcher Stelle Sie umschalten müssen.
Von Einlesen und Überprüfen, ob jetzt die Spiegelung des eingegebenen
Wortes nochmal auftaucht.
Und das ist ein klassischer Fall für einen nicht deterministischen
Automaten.
Der könnte nämlich an jeder Stelle, wo potenziell ein Umkehrpunkt
wäre, einen solchen Umkehrpunkt vorsehen.
Aber es muss eine Möglichkeit geben, das richtig zu machen.
Nämlich die richtige Stelle zu finden.
Und das heißt, wenn wir das nicht deterministisch machen, dann haben
wir wieder mehrere Möglichkeiten des Übergangs.
Wir haben also einfach unsere Übergangsfunktion erweitert, indem wir
hier Mengen von Folgezuständen und möglichen Kellerinhalten
hinschreiben.
Und dann ist es klar, dass der ein Wort akzeptiert, wenn es eine
Konfigurationsfolge gibt, die zu einem Endzustand führt.
Das kennen wir vom endlichen Automaten.
Das ist genau die gleiche prinzipielle Konstruktion.
Wir machen einfach den Automaten nicht deterministisch, indem wir
Mengen von Folgesituationen erlauben.
Und dann können wir jetzt diese Sprache erzeugen.
Also, wie machen wir das dann?
Das sieht genauso aus wie vorher.
Der Automat führt das Palindrom mit dem festen Zeichen, das einen
Umkehr erlaubt.
Genau das, was ich gerade gesagt hatte.
Also hier für dieses Wort 01100110 zum Beispiel.
Da, oder noch schlimmer, wenn Sie hier nur Nullen stehen haben, könnte
jeder Punkt ein solcher Punkt sein.
Hier ist es so, dass Sie ein Zeichen einlesen und gehen sofort in den
neuen Zustand S1 über, schreiben das Zeichen in den Keller.
Und wenn Sie jetzt irgendein Zeichen auf dem Eingabeband und im Keller
ein Zeichen haben, das ungleich dem E ist, dann schreiben Sie das
Zeichen E rein.
Und sobald Sie das gleiche Zeichen dort sehen, auf dem Eingabeband wie
als oberstes Kellerzeichen, dann sagen Sie, ich könnte hier
umschalten.
Also es könnte sein, dass hier ein Punkt ist, der für das Palindrom
wichtig ist.
Das heißt, ich würde in einen neuen Zustand gehen, S2, und dieses
Zeichen E löschen, weil ich davon ausgehe, es ist das erste Zeichen
der Spiegelung des bisher gelesenen Wortes.
Oder Sie bleiben und schreiben einfach weiter Zeichen auf Ihren Keller
drauf.
Und wenn Sie in dem S2 sind und das gleiche Zeichen sehen, in S2 sind
wir gekommen, weil wir meinen, wir wollen jetzt überprüfen, ob das,
was wir bisher gesehen haben, genauso auf dem Keller steht.
Das heißt, nur für die Situation müssen wir weitermachen können.
Dann können Sie das entsprechend rauslöschen und machen weiter im
Zustand S2.
Wenn Sie im Zustand S2 das oberste Kellerzeichen sehen, dann haben Sie
offensichtlich richtig eine Spiegelung des bisher gelesenen Wortes
erkannt und gehen in den Endzustand S3 über.
Wenn Sie das aber an dieser Stelle gemacht hätten, dann wären Sie
anschließend an dieser Position und Sie hätten das Wort auf dem
Eingabeband noch nicht vollständig abgearbeitet.
Sie wären zwar im Endzustand, werden aber nicht in einer
akzeptierenden Endkonfiguration, weil Sie das Eingabewort nicht
vollständig abgearbeitet haben.
Das erreichen Sie nur, wenn Sie eben so lange in S1 bleiben und erst
hier in S2 gehen und den Rest abarbeiten.
Und Sie haben eben an jeder Position, wo Sie, solange Sie im Zustand
S1 sind, feststellen, da ist das gleiche Zeichen nochmal, da könnten
Sie umschalten.
Also, jetzt haben wir eine Sprache gefunden, die wir nicht mit
deterministischen Kellerautomaten erkennen können, aber mit einem
nicht deterministischen Kellerautomaten.
Das heißt, hier ist offensichtlich die Ausdrucksfähigkeit oder die
Akzeptierungsfähigkeit von nicht deterministischen Kellerautomaten
größer als die Ausdrucksfähigkeit der deterministischen
Kellerautomaten.
Noch eine Frage, wie kommt man zum Selbsttest?
Das verstehe ich jetzt nicht, was Sie als Selbsttest verstehen.
Das muss eine andere Frage sein, die sich nicht auf diese Vorlesung
bezieht.
Beziehungsweise, wir haben natürlich die Surveys.
Das sind Selbsttests, mit denen Sie unser Werkzeug nutzen können, um
Fragen zu den Kapiteln zu beantworten.
Die werden regelmäßig bereitgestellt.
Müssen Sie einfach das NuKit nutzen und dann auf den Survey gehen.
Okay, das war es für heute.
Vielen Dank für die Aufmerksamkeit.
Wir sehen uns am Montag wieder.