So, schönen guten Morgen.
Ich begrüße Sie herzlich zur Vorlesung der Grundlageninformatik II,
heute am Mittwochmorgen und leider fünf Minuten verspätet.
Es sind aber so viele Dinge, die ich hier noch einstellen muss.
Ich habe in den letzten Malen wieder Fehlerquellen entdeckt, die da
sein können und die dann auf einmal dazu führen, dass eine Vorlesung
nicht richtig aufgezeichnet ist, obwohl ich das seit Jahren mache.
Immer wieder gibt es neue Fehlerquellen, die uns da einen Streich
spielen manchmal.
Aber hier hat es letztes Mal ganz gut funktioniert.
Also, letztes Mal haben wir uns mit vielen Themen beschäftigt.
Nochmal ganz kurz, Pumping Lemma, wissen Sie, ist ein wichtiges Thema,
haben wir letztes Mal eigentlich schon abgehakt gehabt.
Wir hatten einige, wir hatten uns hier angeguckt an die Reduktion von
Automaten, hatten hier mit dieser Folie begonnen, hatten dann gesehen,
wie man reduzieren kann.
Ich hatte Ihnen das vorgeführt an diesem Beispiel eines Automaten, wie
man feststellt, welche Zustände eines Automaten äquivalent sind, wie
man das also sukzessive macht, indem man feststellt, sukzessive
beginnend von den Nulläquivalenten, sukzessive feststellt, welche
nicht -äquivalent, nicht-nulläquivalent, nicht-einzäquivalent und so
weiter, nicht-K-äquivalent sind.
Und sobald dann hier in dieser Tabelle Felder frei bleiben, weiß man,
das sind die Paare von Zuständen, die äquivalent sind.
Und daraus ergeben sich dann genau die Äquivalenzklassen, die man
braucht, um die Reduktion der Automaten machen zu können.
Das war ja dann der Automat, bei dem die Zustände dann die Mengen
äquivalenter Zustände jeweils sind.
Und dadurch ergibt sich dann ein reduzierter Automat, von dem man
beweisen kann, dass es keinen kleineren geben kann, dass er bis auf
Isomorphie eindeutig ist.
Und das sah dann in diesem Beispiel so aus, dass eben hier diese
umrandeten Zustandspaare jeweils zusammengefasst werden zu solchen
Zustandsklassen.
Und dadurch ergibt sich dann ein wesentlich einfacherer Automat.
Das ist also wichtig zur Kostenreduktion bei der Realisierung von
endlichen Automaten.
Und wir hatten uns dann angeschaut, noch das nächste Thema, die nicht
deterministischen endlichen Automaten, hatten festgestellt, dass man
also durchaus eine Erweiterung machen kann, bei dem man die
Folgezustände nicht eindeutig macht, sondern dort Mengen von
Folgezuständen angebt.
Ich hatte Ihnen das kleine Beispiel gegeben hier von diesem Automaten,
der alle Wörter erkennt, bei dem das letzte Zeichen vorher schon mal
aufgetaucht ist.
Da hatte ich in einer Stelle etwas durchgestrichen, was natürlich so
nicht ganz richtig war.
Das BBWAA ist natürlich ein Wort, das zu dieser Sprache gehört, weil
ja AA am Ende ist.
Wenn dort nur das A stehen würde, dann wäre es natürlich nicht in der
Sprache, weil das A nicht vorher aufgetaucht ist.
Wenn hier aber AAA am Ende steht, ist natürlich das Wort auch mit
drin.
Da hatte ich nur eine andere Folge von Zustandsübergängen hier in dem
Fall gemacht.
Und die führte nicht zu dem gewünschten Ergebnis, dass wir am Ende in
einem Endzustand sind.
Das macht eben noch mal deutlich, dass es viele Möglichkeiten gibt, zu
einem Endzustand zu kommen.
Und sobald es eine Möglichkeit gibt, dorthin zu kommen bei der
Abarbeitung eines Wortes, dann wird das Wort auch akzeptiert, selbst
wenn es eben viele andere Möglichkeiten gäbe, dieses Wort
abzuarbeiten, ohne in den Endzustand zu kommen.
Man könnte ja zum Beispiel bei diesem BBWAA auch einfach in dem
Anfangszustand bleiben und immer mit, egal welches Eingabewort kommt
oder Eingabezeichen kommt, immer im Zustand S0 bleiben.
Und das führt eben nie zum Endzustand.
Es geht nur darum, dass man die Möglichkeit hat, zum Endzustand zu
kommen.
Und das reicht aus, um zu sagen, dieses Wort kann akzeptiert werden.
Und damit wird es von dem nichtdeterministischen Automaten auch
akzeptiert.
Das war die Aussage, die wir da gemacht haben.
Wir haben das dann formal auch aufgeschrieben.
Nachdem wir die Konfiguration dargestellt hatten, haben wir gesagt,
das wird akzeptiert, wenn wir zu einer Endkonfiguration kommen können.
Wir hatten damit die Sprachen definiert für solche
nichtdeterministischen endlichen Automaten.
Und hatten dann überlegt, wie man zu einem nichtdeterministischen
Automaten einen äquivalenten deterministischen Automaten konstruieren
kann, was mit einem einfachen Verfahren geht.
Das hatten wir an dem Beispiel nochmal durchgeführt, wo wir ausgehend
vom Anfangszustand dann alle Folgezustandsmengen definiert haben, die
man dann als Zustände in einem hoffentlich äquivalenten
deterministischen Automaten definiert.
Wir kamen dann auf diese Menge der erreichbaren Zustandsmengen.
Und das sind dann halt die Zustände in dem äquivalenten Automaten, der
dann so aussah, wie hier eingerahmt dargestellt.
Das Zustandsdiagramm für den Automaten, der die gleiche Sprache
akzeptiert, wie dieser vorher gezeigte Automaten mit vier Zuständen.
Der sieht halt deutlich komplizierter aus, weil er jeden Übergang
deterministisch genau macht, auf diesen Zustandsmengen, die wir uns
vorher überlegt haben.
Also es geht, man kann zu jedem nicht-deterministischen ähnlichen
Automaten einen äquivalenten deterministischen Automaten definieren.
Und damit sind diese Automaten nicht mächtiger als die
deterministischen.
Sie haben nur eine andere Art, eine Funktion zu beschreiben, die
häufig wesentlich einfacher und kompakter ist, als das, was wir bei
der Spezifikation als deterministischen Automaten machen würden.
Wobei wir natürlich, wenn wir das implementieren, dann den tatsächlich
so deterministisch machen müssen.
Aber das ist etwas, was wir dann eben bei der Implementierung machen
können.
Wir können zur Spezifikation das erstmal nicht deterministisch
aufschreiben.
Das war das, was wir uns hier überlegt hatten.
Und dann kamen hier noch so ein paar Vorteile, die ich dargestellt
habe.
Insbesondere habe ich dann Ihnen gezeigt, wie man Operationen auf
Sprachen zeigen kann, bzw.
dass wir zeigen können, dass die Vereinigung, das Produkt und die
Iteration von Sprachen, die von endlichen Automaten akzeptiert werden,
auch wieder Sprachen sind, die von endlichen Automaten akzeptiert
werden.
Das war über diese Konstruktion geschehen, bei der wir dann die
Zustandsmengen des Jungt vereinigen, einen neuen Anfangszustand
dazufügen und damit in der Lage sind, da wir von diesem neuen
Anfangszustand sowohl in den einen als auch in den anderen Automaten
gehen können, dadurch in der Lage sind, die Vereinigung von zwei
Sprachen zu akzeptieren.
Wir hatten das dann nochmal kurz skizziert, wie das gehen könnte für
das Produkt und die Iteration, indem man entsprechend von dem
Endzustand eines Automaten bei dem Produkt dann auf die Folgezustände,
der Anfangszustände des Folgeautomaten geht oder bei der Iteration auf
die Folgezustände hier angedeutet, die Folgezustände des
Anfangszustands dieses Automaten, der dort iteriert werden soll.
Das also waren diese Operationen und diese Automaten, die konstruiert
sind, jeweils nicht deterministische Automaten, können also auf diese
Art und Weise relativ einfach definiert werden.
Wir kamen dann zu der nächsten Art, wie man Sprachen formal
charakterisieren kann, nämlich über Operationen.
Und diese Art, über Operationen zu definieren, heißt, wir definieren
hier eine Sprache darüber, dass wir, das war hier die Definition der
regulären Sprachen, eine Basismenge nehmen, eine Menge von
einelementigen Teilmengen von E und die Leeremenge.
Und wenn wir dann endlich häufig Vereinigung, Produkt und Iteration
anwenden, bekommen wir neue Sprachen dazu und die Menge aller
Sprachen, die wir dadurch bekommen, also durch endlich häufiges
Anwenden von Vereinigung, Produkt und Iteration, das sind die
regulären Sprachen.
Und jetzt kommen wir als nächstes dann zu dem Begriff des regulären
Ausdrucks und das ist dann die erste neue Folie für heute, bei der wir
uns den Begriff des regulären Ausdrucks anschauen, der also nur dazu
dient, praktisch anzugeben, welche Operationen sollen ausgeführt
werden auf diesen einelementigen Basismengen, um eine Sprache zu
erzeugen.
Und so ein regulärer Ausdruck gibt also praktisch nur das Schema an
oder gibt die Vorgabe, wie eine solche Sprache erzeugt werden soll.
Sie kennen solche Definitionen aus der Logik, das haben Sie in
Grundlage der Informatik 1 gelernt, wie man logische Kalküle
aufschreibt, Sie haben die Aussagenlogik kennengelernt, die
Prädikatenlogik erster Stufe und ähnliche Dinge, das sind einfach
formale Modelle und hier haben wir genauso ein formales Modell, bei
dem wir einmal gewisse Basiselemente haben, das sind hier Zeichen, ein
Zeichenkreis durchgestrichen, das ist einfach ein Zeichen, das soll
also ein regulärer Ausdruck sein.
Es ist jedes Zeichen aus dem Alphabet E ein regulärer Ausdruck und
wenn wir zwei reguläre Ausdrücke haben, Alpha und Alpha Strich, dann
soll die Zeichenfolge, Klammer auf, Alpha plus Alpha Strich, Klammer
zu, ein regulärer Ausdruck sein, genauso die Zeichenfolge, Klammer
auf, Alpha mal Alpha Strich, Klammer zu, ein regulärer Ausdruck und
die Zeichenfolge, Klammer auf, Alpha Stern, Klammer, ein regulärer
Ausdruck.
Das sind einfach Zeichenfolgen, Wörter über einem, in diesem Fall
Alphabet, das besteht aus diesem Kreis, durchgestrichen aus den
Elementen des Alphabets und dazu kommen noch Klammer plus Mal und
Stern, also Klammer auf, Klammer zu, Mal und Stern.
Das sind einfach Regeln, wie wir Wörter schreiben mit der Verwendung
dieser Zeichen.
Mehr ist das im Augenblick nicht.
So, das sind reguläre Ausdrücke.
Es ist also jeweils ein wohlgeformter Term, können wir das mal ein
bisschen interpretieren, das sieht aus wie ein wohlgeformter Term,
über einer variablen Menge E, sowie einer Funktionssymbolmenge, Plus,
Mal, Stern und diesem Zeichen hierfür, was wir normalerweise als leere
Menge bezeichnen.
Das hat aber damit erstmal noch gar nichts zu tun.
Und diese Funktionssymbole, die wir hier haben, haben also
verschiedene Bedeutungen.
Plus und Mal können wir als zweistellige Funktionssymbole
interpretieren, Stern als einstellig und dieses andere Zeichen dort
als nullstellige Operation.
So kann man das formal einfach erklären, was dort gemacht wird.
Sie sehen hier dieses Alpha plus Alpha Strich, Klammer zu, ist eben
einfach ein Term, der einen zweistelligen Operator Plus entsprechend
verwendet, um zwei Terme Alpha und Alpha Strich geeignet zu
verknüpfen.
Das ist die Standardvorgehensweise, wie man Terme über irgendwelche
Basismengen, Variablenmengen und Operatoren definiert.
Sie haben das kennengelernt für die Operationen Logisches Und,
Logisches Oder und dann noch die Negation.
Das waren auch drei Operationen und dann gibt es noch nullstellige
Konstanten, die für Wahr und Falsch und dann hat man alles das, was
man braucht.
Das sind einfach nur Ausdrückungen.
Jetzt wollen wir das Ganze natürlich auch interpretieren.
Wir wollen ja Sprachen damit darstellen.
Und diese Sprachen bekomme ich, indem ich jetzt diese formalen Terme
interpretiere in einer gewissen Art und Weise.
Das heißt, ich interpretiere die oder belege sie mit einer bestimmten
Bedeutung.
Und das muss ich jetzt so machen, dass ich sage, was ist die Sprache?
Also Language, deswegen L.
Ich möchte die Sprache eines regulären Ausdrucks definieren.
Das mache ich rekursiv, genau wie bei der Definition dieser regulären
Ausdrücke.
Die Sprache dieses nullstelligen Funktionssymbols ist die leere Menge.
Also hier auf der rechten Seite ist das jetzt das Zeichen für die
leere Menge.
Mag ein bisschen verwirrend sein.
Also das Zeichen für die leere Menge wird als leere Menge
interpretiert.
Ich hätte auch sagen können, das ist die leere Menge.
So schreiben wir die ja manchmal auch.
Das ist also hier Synonym in dem Fall.
Hätte ich vielleicht so hinschreiben sollen, damit klar ist, was ich
hier meine.
Dann für jedes Element aus dem Alphabet E wird dieses Zeichen E
interpretiert als die Sprache, die aus genau einem Wort besteht,
nämlich dem Wort, das nur aus einem Zeichen E besteht.
Also einfach nur die Sprache, die aus diesem Zeichen besteht.
Das waren genau die Basismengen bei der Definition der regulären
Mengen.
Und dann sagen wir, wenn wir zwei reguläre Ausdrücke haben, Alpha und
Alpha Strich, das folgt also jetzt hier dieser Regel, wie wir
Ausdrücke aufbauen, dann interpretieren wir die aus Alpha und Alpha
Strich aufgebauten Ausdrücke, Alpha plus Alpha Strich, in Klammern,
als die Sprache, also das L von Alpha, also wir interpretieren die
Sprache Alpha, wir interpretieren die Sprache des Ausdrucks Alpha
Strich, das ist das zweite, was wir machen, und wir vereinigen diese
beiden Sprachen.
Genauso für die anderen Terme, für Mal und für Stern.
Und das heißt, dieser Punkt dort wird interpretiert als Produkt von
Sprachen, und dieses Alpha Stern wird interpretiert als Iteration der
Sprache des Ausdrucks Alpha.
Das ist einfach nur eine Interpretation dieser formalen Terme, als ein
Schema zur Erzeugung von Sprachen aus Basismengen.
Genau das steht hier, es werden die Terme interpretiert durch
Sprachen, die entsprechend den dort spezifizierten Operationszeichen
interpretiert werden, als Operation auf Vereinigung, Produkt und
Iteration auf Sprachen.
Das Ganze kommt sofort mit einem Beispiel, damit Sie sehen, was damit
gemeint ist.
Ich muss einfach das so formal machen, um Ihnen nochmal klar zu
machen, dass wir hier einmal die rein formale Ebene haben, die Terme,
und dann die Interpretation, wir sagen zu jedem Term, welche Sprache
dadurch definiert ist.
Das ist eine Interpretation, das kennen Sie aus der Logik, da hat man
zu jeder logischen Formel, jede logische Formel hat man interpretiert,
in dem Fall durch einen Wahrheitswert, wahr oder falsch.
Und das wurde auch gemacht durch eine einfache Interpretation der
Zeichen in einer logischen Formel, durch entsprechende Operationen auf
der Menge dort der Wahrheitswerte 0 und 1 bzw.
wahr und falsch.
Es ist in der Art nichts anderes, einfach die formale Interpretation
einer Termmenge.
Diese Ausdrücke sehen manchmal etwas kompliziert aus, diesen Punkt,
der hier oben steht, den lassen wir meistens weg.
Wir werden auch die Klammern, soweit es sinnvoll ist, weglassen und
führen dann übliche Vorrangregeln ein, dass die Klammer vor Iteration,
vor Produkt und vor Summe geht.
Das ist völlig klar.
Wenn ich hier sowas hinschreibe wie A plus B mal C und dann das hier
mal D oder sagen wir mal A noch dazu hier und dann hier vielleicht
noch mal irgendwie B Ne, so nicht.
Das war mal B Stern.
Ja, das kann ich auch anders hinschreiben.
Da kann ich auch hinschreiben, einfach damit es eindeutig bleibt, A
plus B mal C, D und dann B Stern.
Das ist der gleiche Ausdruck, nur etwas vereinfacht.
Wir müssen nicht alle Klammern hinschreiben.
Solange also klar ist, in welcher Reihenfolge die ausgeführt werden
müssen, ist es klar.
Hier wird also der Stern nur angewandt auf das B und wir haben hier C
und D, also die drei eben durch Produkt verbunden.
Auf diesen Punkt hätte ich auch verzichten können, aber das A plus B
muss halt ausgeführt werden, muss halt hier in Klammern bleiben, damit
ich nicht B mal C hier hinschreibe, sondern damit das eben
entsprechend richtig interpretiert wird.
Okay, das also zu den Vereinfachungsregeln, das kennen Sie alles aus
der Arithmetik.
Und jetzt gebe ich Ihnen ein paar Beispiele.
Was für Sprachen kann man damit erzeugen?
Die einfachste Sprache, die wir erzeugen können, und die einfachste
wäre natürlich die leere Menge.
Was passiert, wenn wir dieses Zeichen für die leere Menge iterieren?
Iteration auf der Menge.
Das ist, ja wieso ist das diese Sprache, die aus dem Lambda besteht?
Also Alpha gleich ist dieser Ausdruck.
Eigentlich hätte ich ja Folgendes hinschreiben müssen.
Also wenn ich das interpretiere, dann ist L von diesem Kringelstein,
ich lasse mal die Klammer weg da drin, das wäre doch gleich L von
leere Menge, oder Zeichen für leere Menge, und diese Sprache iteriert.
Das hier wäre entsprechend die, ich male jetzt dieses Zeichen hin,
diese leere Menge iteriert.
Und das wäre gleich, wir wissen, was die Iteration einer solchen
Sprache ist, das war die Vereinigung aller leere Menge hoch I, I aus
N0.
So, leere Menge hoch I, das sind also alle möglichen Produkte der
leeren Menge mit sich selbst, das ist aber in dem Fall insbesondere
gleich leere Menge hoch 0, vereinigt leere Menge hoch 1 und so weiter.
Diese hier, die sind alle gleich leer, und das hier ist gerade Lambda.
Leere Menge hoch 0 ist die Sprache, die das leere Wort enthält.
Wenn ich irgendeine Menge habe, irgendeine Menge A, und die hoch 0
nehme, A hoch 0, das ist die Sprache, die das leere Wort enthält.
Also auch für die leere Menge gilt das.
Deswegen gilt also das, was hier steht, L von diesem Ausdruck, ist die
Sprache, die das leere Wort enthält.
Alle anderen Folgemengen, leere Menge hoch 1, hoch 2 und so weiter,
das sind alles die leeren Mengen.
Jetzt hat schon jemand eine Frage.
Wie kann man die Multiplikation von Sprachen verstehen?
Ganz einfach.
Sie werden das gleich sehen an einem Beispiel.
For all questions, was genau stellt man sich in diesem Kontext unter
Iteration vor?
Das habe ich hier gerade nochmal dargestellt.
Iteration als Vereinigung aller Produkte der Sprache mit sich selbst.
Was heißt iteriert?
Also was macht das?
Auch das habe ich gerade eben dargestellt.
Ich denke, ich habe diese Fragen alle beantwortet.
Wie man jetzt solche Sprachen, wie man so ein Produkt bildet, das
sehen wir gleich nochmal an dem nächsten Beispiel.
Hier gebe ich Ihnen einen einfachen Ausdruck.
Nämlich dieser Ausdruck, Klammer auf, A+, Klammer auf, B, C, Klammer
zu, Klammer zu.
Das ist der Ausdruck und ich behaupte, das ist die Sprache.
Warum ist das diese Sprache?
L von Alpha, von diesem Ausdruck hier, ist nach Regeln, die wir gerade
gesehen haben, da müssen wir also die Sprache von dem A nehmen, das
ist der eine Term hier drin.
Der andere Term ist das BC.
Und das ist die beiden Sprachen vereinigen.
Das ist nur die Vereinigung von Sprachen.
Die Sprache, die zu dem Zeichen A gehört, ist einfach nur die Sprache,
die aus dem einen Wort besteht, das aus dem einen Zeichen A besteht.
Also das ist diese eine einelementige Menge, die nur das Zeichen A
enthält.
Vereinigt mit der Interpretation dieses Ausdrucks.
Dieser Ausdruck ist ein Produkt von zwei Termen B und C.
Das ist also die Sprache, also die Interpretation von B.
Mal genommen mit der Sprache, die zu dem Ausdruck C gehört.
Das kann ich entsprechend weitermachen.
Das ist die Sprache, die zu B gehört und zu C.
Das sind gerade die jeweiligen einelementigen Mengen, die jeweils die
Zeichen B und C enthalten.
Die müssen als Produkt verknüpft werden.
Produkt von zwei solchen Mengen ist gerade das Hintereinanderschreiben
der Wörter aus der ersten Sprache und der zweiten Sprache.
Also wenn wir L mal L Strich nehmen, dann ist das die Menge aller U, V
so hintereinander geschrieben, sodass U aus L und V aus L Strich ist.
Das ist die formale Definition.
Hier haben wir nur jeweils ein Element in den beiden Mengen, nämlich B
und C.
Die beiden nebeneinander geschrieben gibt gerade das Wort BC.
Und das heißt, wenn wir die beiden Mengen vereinigen, dann kommt
daraus die Menge, die nur aus den beiden Wörtern klein a und bc
besteht.
Das ist also das, was dieser Ausdruck hier darstellt.
Das ist Produkt, Iteration und so weiter damit einmal beschrieben.
Wir sehen gleich noch mehr Beispiele.
Dann haben wir hier noch ein Beispiel a plus b in Klammern mal c.
Das wäre in dem Sinne dann eben auch wieder diese Menge.
Warum?
Weil das hier ist gleich Sprache von a plus b mal Sprache von c.
Das wäre gleich dieser L von a vereinigt L von b und das hier mal
dieser Sprache, die nur aus a besteht.
Und das wäre dann entsprechend gleich der Sprache, die aus dem Element
a besteht, vereinigt mit der Sprache, die aus dem Element b besteht
und das ganze Produkt mal diesem a.
Und das wäre wiederum gleich der Sprache, die aus a und b besteht mal
der Sprache, die aus dem c besteht.
Und das ist dann entsprechend gerade a mal b und b mal c, die Sprache,
die hier oben steht.
Das war jetzt ganz eben jeder einzelne Schritt mit einem
Gleichheitszeichen hier dargestellt.
Keine zwei Schritte zwischen diesen zwei Gleichheitszeichen.
Das ist alles kanonisch entsprechend der Definiz oder der
Interpretation der regulären Ausdrucke, die ich Ihnen gerade vorher
dargestellt habe.
Jetzt haben wir hier noch einmal einen Ausdruck, wo noch mal die
Iteration vorkommt.
Da war ja noch mal eine Frage gewesen.
Also wenn wir a Stern mal b hier hinschreiben, entsprechend mit der
vollständigen Klammerung, dann ist das hier die Sprache.
Hier steht es jetzt auf diese Art und Weise.
Warum ist das diese Sprache?
b a b a a b und so weiter.
Das ist die Sprache L von a Stern mal L von b.
Das wäre entsprechend L von a, die iteriert mal der Sprache, die nur
aus dem b besteht.
Und das L von a Stern, das wäre dann entsprechend die Sprache, wo nur
der eine elementige Sprache a, die iteriert.
Ein Stern mal der Sprache, die aus dem b besteht.
Das a Stern, wissen wir, ist die Menge aller Folgen von a.
Also beliebig oft die Menge a hintereinander geschrieben.
Das ist dann genau die Sprache, die hier vorne steht.
Also beliebige, ich hätte das auch anders hinschreiben können, als die
Sprache, die aus den Folgen a hoch i b besteht, wobei i aus n Null
ist.
Also beliebige Folgen von a, gefolgt von einem b.
Kurze Frage hier zwischendrin.
Wofür sind reguläre Ausdrücke wichtig?
Das werden Sie sehen.
Man kann auf diese Art und Weise Sprachen beschreiben.
Und wenn Sie zum Beispiel eine Suchanfrage machen, da werden Sie ganz
oft eine Suchanfrage in einem Text formulieren, Sie oft als regulären
Ausdruck.
Im Prinzip spezifizieren Sie dadurch durch einen regulären Ausdruck
eine gewisse Menge an Texten, die einem bestimmten Muster gehorchen.
Da spezifizieren Sie einen endlichen Automaten, der die
Mustererkennung macht.
Sie werden solche Texte schon durchaus mal geschrieben haben, wenn Sie
etwas kompliziertere Suchanfragen schreiben für irgendeinen
Suchalgorithmus oder irgendeinen Interface, um einen allgemeineren
Ausdruck zu spezifizieren.
Sie sagen ja hier im Prinzip, ich suche alle Wörter, bei denen ich zu
Anfang beliebig viele A's habe und danach ein B.
Das heißt, ich habe hier die Möglichkeit, eine Sprache zu definieren.
Ich kann die auch über eine Grammatik definieren.
Das werden Sie aber, wenn Sie eine Suchanfrage spezifizieren wollen,
nicht tun.
Sie werden auch nicht einen Automaten spezifizieren, nicht eine
Automaten -Tabelle hinschreiben, um alle Sprachen zu definieren, die
auf diese Suchanfrage passen.
Sie definieren durch eine Suchanfrage eine bestimmte Menge von
Wörtern, die genau diese Eigenschaft haben, dass sie dieser
Suchanfrage entsprechen.
Und für diese Suchanfragen ist es besser, da einen regulären Ausdruck
hinzuschreiben.
Das ist einfach eine andere Art, eine Sprache zu charakterisieren.
Und wir werden sehen, dass diese regulären Ausdrücke im Prinzip genau
die gleichen Sprachklassen definieren, wie die ähnlichen Automaten und
wie die rechtslinearen Grammatiken, zu denen wir gleich noch kommen
werden.
Das heißt, wir haben verschiedene Arten, das gleiche Objekt zu
beschreiben.
Und das ist eine ganz wichtige Vorgehensweise, dass ich je nachdem,
welche Fragestellung ich habe, ein bestimmtes Objekt passend
charakterisiere.
Und wenn ich verschiedene äquivalente Beschreibungen habe, wähle ich
mir die aus, die für meinen aktuellen Zweck, die am besten geeignet
ist.
Es gibt bestimmte Fragestellungen, da brauche ich einen regulären
Ausdruck zur Beschreibung.
Es gibt andere Fragestellungen, wie zum Beispiel, gehört ein Wort zu
einer bestimmten Sprache, da will ich einen Automaten haben, der genau
diese Antwort gibt, ob das Wort drin ist oder nicht.
Und wenn ich sage, ich möchte ein Wort in einer Sprache erzeugen,
möchte ein Programm schreiben, da muss ich wissen, was sind die
Regeln, um ein Programm syntaktisch korrekt aufzuschreiben.
Dann brauche ich eine Grammatik.
Für das Erzeugen eines Wortes aus einer Sprache, das Schreiben eines
Programms, nützt Ihnen der Automat, der dieses Programm dann
syntaktisch korrekt hat, überprüfen kann, sehr wenig.
Der gibt Ihnen nicht die Regeln an.
Das ist eine andere Art der Beschreibung.
Also um ein Programm hinzuschreiben, um ein Wort zu schreiben, das
syntaktisch korrekt ist, brauchen Sie eine Grammatik.
Um für ein Wort zu überprüfen, ob es entsprechend den Regeln der
Grammatik konstruiert wurde, brauchen Sie einen endlichen Automaten.
Oder entsprechend bei Sprachen der anderen Chomsky-Ebenen brauchen Sie
einen entsprechenden Automaten.
Und wenn Sie die Struktur der Wörter genauer angucken wollen, dann
nehmen Sie einen Ausdruck, der Ihnen über Operationen beschreibt, wie
die Wörter aufgebaut sind.
Das sind andere Fragestellungen, die Sie haben.
Und Sie haben den Luxus, dass Sie jeweils eine unterschiedliche Art
der Beschreibung wählen können.
Das ist eine ganz wichtige Vorgehensweise, wenn Sie formal etwas
modellieren.
Sie haben eine gewisse Fragestellung und müssen zu dieser
Fragestellung die geeignete formale Modellierung wählen, sodass Sie
diese Fragestellung am besten beantworten können.
Das ist eine der grundlegenden Aufgaben, mit denen Sie als
Wirtschaftsingenieur später immer wieder zu tun haben werden, dass Sie
ein Problem der realen Welt irgendwie bearbeiten müssen.
Sie haben irgendein Problem zu lösen in irgendeinem Produktionsablauf
oder wer weiß wo, Geschäftsvorfall oder welche Dinge auch immer.
Und Sie müssen in der Lage sein, das vernünftig zu beschreiben, die
wesentlichen Eigenschaften daraus zu ziehen, um die Fragen, die Sie
beantworten müssen dazu, in der bestmöglichen, effizientesten Art und
Weise und effektivsten Weise beantworten zu können.
Das ist etwas, was man lernen muss.
Das lernen die Physiker.
Für die ist das Handwerkszeug.
Das wissen die genau, dass sie verschiedenste Modelle brauchen.
Das brauchen Sie als Wirtschaftsingenieur genauso.
Eine bestimmte Art von Objekten, bei denen man das eben auch
beschreiben kann, was ich Ihnen hier präsentiere, ist halt, wie gehe
ich mit den Elementen Informationsverarbeitung um.
Wie beschreibe ich die Sprachen?
Wie beschreibe ich die informationsverarbeitenden Systeme?
Und dann kann ich da geeignete Aussagen drüber machen.
Das ist also das, worum es hier eigentlich geht, die geeignete Art der
Modellierung für bestimmte Fragestellungen zu finden.
Gut, das zu dieser Frage.
Sie werden gleich noch sehen, was wir damit alles machen können.
Jetzt haben wir natürlich sofort diesen Satz als einfache Folgerung.
Die Menge der regulären Sprachen, die war so definiert, Basismengen,
einelementige Mengen, und jede Sprache, die durch endlich häufiges
Anwenden von Vereinigung, Produkt und Iteration daraus erzeugt wurde,
ist eine reguläre Sprache.
Das ist offensichtlich so, dass jede Sprache, die aus einem regulären
Ausdruck erzeugt wurde, ja genau so aufgebaut wird.
Ich kann also aus einem regulären Ausdruck erzeuge ich ja gerade ein
endlich häufiges Anwenden von Vereinigung, Produkt und Iteration auf
einelementigen Basismengen.
Und das sind genau die Sprachen, die ich durch reguläre Ausdrücke
beschreiben kann.
Das heißt, ich habe jetzt mit den regulären Ausdrücken das formale
Modell, um diese vorher definierte Sprachmenge tatsächlich zu
beschreiben.
Ich brauche nur reguläre Ausdrücke hinzuschreiben.
Jetzt wissen wir auch, das hatte ich Ihnen vorher gezeigt, die Menge
der von einem endlichen Automaten akzeptierbaren Sprachen ist
abgeschlossen unter Vereinigung, Produkt und Iteration.
Das heißt, dass die Klasse, die abgeschlossen ist gegenüber diesen
Operationen, ist offensichtlich die Menge der regulären Sprachen
enthalten in der Menge der Sprachen, die von endlichen Automaten
akzeptiert werden.
Weil ja die endlichen Mengen von endlichen Automaten akzeptiert
werden, das hatten wir schon mal zu Anfang gesehen.
Jede endliche Menge wird akzeptiert, also jede Menge, die aus nur
einem Zeichen besteht, wird akzeptiert von einem endlichen Automaten.
Natürlich wird auch die Menge, die aus der leeren Menge besteht,
akzeptiert von einem endlichen Automaten.
Und wir wissen, dass jede Vereinigung oder Produkt und Iteration von
Sprachen wieder von einem endlichen Automaten akzeptiert wird.
Also ist jede reguläre Sprache eine Sprache, die von endlichen
Automaten akzeptiert wird.
Frage ist, ist es auch andersrum richtig?
Ich kann natürlich das so machen, dass ich dann einen endlichen
Automaten konstruiere als Akzeptor der Sprache, die dadurch definiert
ist.
Das schauen wir uns gleich noch ein Beispiel an.
Die Frage ist, ob es auch andersrum gilt, dass jede Sprache eines
endlichen Automaten auch durch einen regulären Ausdruck beschreibbar
ist.
Auch das gilt tatsächlich.
Werden wir das auch noch sehen.
Und dann folgt dann daraus, dass die beiden Definitionen oder beiden
Charakterisierungen gleich mächtig sind.
Dass also Sprachen, die von endlichen Automaten akzeptiert werden, die
gleichen sind wie die von regulären Ausdrücken beschriebenen.
Ich werde Ihnen jetzt ein Beispiel zeigen, wie man zu einem regulären
Ausdruck einen endlichen Automaten konstruiert.
Wie kann man das allgemein machen?
Wir hatten ja uns dafür schon mal überlegt, wie das geht.
Ich hatte Ihnen das gerade noch mal erläutert, warum das der Fall ist.
Wir können das sofort im Prinzip schließen daraus, dass jede endliche
Menge eine Sprache eines endlichen Automaten ist.
Und wir hatten gesehen, dass die Vereinigung von Produkten und
Iterationen von diesen Sprachen wieder eine Sprache ist von einem
endlichen Automaten.
Ich kann das auch konstruktiv aufbauen, indem ich sage, naja, diese
endliche Menge hier, oder diese Menge, die leere Menge, wird natürlich
zum Beispiel von diesem Automaten hier akzeptiert.
Der einen Anfangszustand hat und einen Endzustand, aber der Endzustand
ist gar nicht erreichbar.
Das ist ein nicht deterministischer endlicher Automat und der
akzeptiert die leere Menge.
Da habe ich also die Forderung eingehalten, dass ich einen
Anfangszustand habe, dass ich eine nicht leere endliche Menge von
Endzuständen habe.
Und die Sprache, die akzeptiert wird, ist offensichtlich die leere
Menge.
Wenn ich ein einzelnes Zeichen akzeptieren möchte, dann kann ich das
mit einem sehr einfachen Automaten machen, der auch wieder nicht
deterministisch spezifiziert ist.
Der hat also nur diesen einen Übergang von dem Anfangszustand in einen
Endzustand.
So, und dann kann ich natürlich entsprechend weiter daraus mit den
Operationen, die wir definiert haben, weitere Automaten aufbauen,
indem ich diese hier durch Vereinigung, durch Produkt oder Iteration
zu komplexeren Automaten aufbaue.
Auch dazu ein Beispiel gleich, hier steht noch etwas über eine
Konstruktion mit Lambda-Automaten.
In der Literatur finden Sie manchmal für die Konstruktion eines
Automaten, der die Vereinigung von zwei Sprachen akzeptiert, die von
zwei anderen Automaten akzeptiert werden, dass man das mit Lambda
-Automaten macht, bei denen man Übergänge hat zwischen zwei Zuständen
mit dem leeren Wort.
Darauf kann man verzichten, geht auch, ist eine äquivalente
Konstruktion, ist aber so nicht erforderlich.
Ich gebe Ihnen ein Beispiel, wenn wir also hier zu diesem einfachen
Ausdruck Astern plus A mal B, das ist also die Menge der Wörter, die
entweder nur Folgen von A sind oder die Zeichenfolge A, B.
Wie kann ich dazu einen endlichen Automaten konstruieren?
Wir haben die Basisautomaten oben gerade hingeschrieben und wir
brauchen also für das Astern, da wird das Zeichen A akzeptiert und das
wird iteriert.
Und ein Automat, der genau das macht, den kann ich systematisch
erzeugen, wenn ich diesen hier iteriere, dann sieht er zunächst mal
etwas komplizierter aus, das kann ich zusammenfassen zu einem Zustand
und dann habe ich hier einen Anfasszustand, der gleichzeitig
Endzustand ist und ich kann aus dem Zustand nicht rauskommen, mit dem
A bleibe ich immer drin, mit anderen Zeichen kann ich dort nichts
machen, ich kann also nur mit dem A hier immer rumlaufen.
Das ist der Automat, der die Sprache Astern akzeptiert, beliebig lange
Folgen von A.
Den kann ich also systematisch konstruieren, auf die Art und Weise,
die ich Ihnen gestern erzählt habe, aber ich kann ihn auch hier direkt
so hinschreiben.
Das ist auch systematisch auf die Art und Weise konstruiert, aber ich
habe da ein paar Schritte ausgelassen.
Und dann muss ich die Folge A mal B konstruieren, also den Automaten
für diese Folge A mal B, das ist der Automat, wenn ich die
hintereinander schreibe, dann habe ich hier den Zustand S0, S1 und S2,
die werden ja des Jungt vereinigt, die beiden Automaten, die A und B
jeweils akzeptieren und werden so verknüpft, dass ich also mit A auf
den Zustand S1 komme, mit B dann weiterlaufe zum Zustand S2 und dann
habe ich das Wort akzeptiert.
Das war ja die Produktbildung von zwei Automaten.
So, und dann muss ich die beiden vereinigen, das Plus anwenden.
Wenn ich die beiden vereinige, dann habe ich also einmal den Weg vom
Anfangszustand auf diesen Iterationsautomaten, wobei ich da mit dem A
halt rübergehen muss, und dann habe ich noch diesen anderen Automaten,
der gerade das Produkt von A und B akzeptiert.
Damit habe ich diese beiden Sprachen vereinigt und ich habe insgesamt
die Sprache, die zu A-Stern plus AB gehört, damit mit diesem Automaten
akzeptiert.
Oder kann die mit dem Automaten akzeptieren.
Sie sehen, das ist ein ganz einfacher, regulärer Ausdruck.
Wir können daraus einen endlichen Automaten konstruieren.
So können Sie also im Prinzip zu einem beliebigen, regulären Ausdruck
einen Automaten konstruieren, der genau diese Sprache akzeptiert.
Das ist ein relativ einfacher, geradliniger Vorgang, wie Sie daraus
einen solchen Automaten konstruieren.
Da könnten Sie sofort ein Programm für schreiben, entsprechend den
Angaben, die ich letztes Mal gemacht habe, um daraus Automaten zu
konstruieren.
Die werden erst ein bisschen zu groß sein.
Dann können Sie die noch vereinfachen mit der Reduktion von Automaten
und dann haben Sie den dazu passenden Automaten tatsächlich gebaut.
Der nächste Satz ist jetzt der, den ich schon angedeutet habe.
Ich kann tatsächlich zu jedem endlichen Automaten auch einen regulären
Ausdruck finden, der genau die Sprache beschreibt, die der Automat
akzeptiert.
Das ist die andere Richtung.
Wie kann ich aus einem Automaten einen regulären Ausdruck definieren?
Und dieser Algorithmus ist komplizierter.
Das ist nicht sofort offensichtlich, wie man das macht.
Wir werden das in einem Beispiel sehen.
Sie werden in den Übungen viele Beispiele dazu bearbeiten.
Wir haben mit dem Aufgabenpool dazu einige Beispiele drin.
Das muss man einfach ein paar Mal machen.
Dann sieht man, wie man das in etwa macht.
Man kann das natürlich auch als Algorithmus aufschreiben.
Also hier steht zwar kein praktikables Verfahren.
Selbstverständlich gibt es ein effektives Verfahren, das einen
Automaten überführt in einen regulären Ausdruck.
Aber es ist ein bisschen kompliziert.
Und ich zeige Ihnen dazu gleich ein Beispiel auf der nächsten Folie.
Hier nur erstmal die Folgerung aus den beiden Sätzen, die wir gerade
hatten.
Es ist also die Menge der Sprachen, die von endlichen Automaten
akzeptiert werden, gleich der Menge der Sprachen, die von nicht
deterministischen Automaten, also endlichen Automaten akzeptiert
werden, gleich der Menge der Sprachen, die von regulären Ausdrücken
akzeptiert werden oder beschrieben werden.
Und damit haben wir drei Sprachklassen mit unterschiedlichen formalen
Modellen, die die identische Klasse von Sprachen beschreiben.
Wir wissen, dass die nicht ausreicht.
Wir kennen Sprachen, die da nicht mit erfasst sind.
Aber wir wissen, dass es Sprachen gibt, die nicht regulär sind.
Die Sprache A auch in B hoch N können wir also nicht durch einen
regulären Ausdruck beschreiben.
Aber immerhin haben wir hier jetzt drei äquivalente Beschreibungen für
diese Sprachklasse.
Und jetzt ein Beispiel, wie wir zu einem endlichen Automaten versuchen
können, einen regulären Ausdruck zu beschreiben.
Also das ist jetzt ein Automat und der hat also hier einen
Anfangszustand S0.
Dann kann man von S0 aus zum Endzustand S3 kommen, kann den auch
wieder verlassen mit A oder B.
Und mit B kommt man von S0 hier runter zu dem S1, kann da beliebig oft
ein B ausführen, kann dann mit B drin bleiben in S1, kann dann mit A
in S2 gehen, kann mit weiteren A's in S2 bleiben, kommt mit B wieder
zurück.
Und Sie sehen, man kommt nach S3 eigentlich nur, wenn man ein A als
letztes Zeichen hat.
Das sieht man schon mal.
Ich muss also in S0, von S0 aus kann ich mit einem A auf den
Endzustand kommen.
Und da schaue ich mir einfach an, unter welchen Bedingungen bin ich
bei S0.
Dazu gibt es folgende Möglichkeiten, ich kann entweder Initial bei S0
sein, also ich weiß zum Beispiel, dass A ist aus dieser Sprache, die
nenne ich mal L, also habe ich jetzt E-A geschrieben, L von E-A, das
sei gleich L.
A ist also aus L, das weiß ich.
Dann kann ich natürlich auch nach A, kann ich A oder B schreiben und
dann wieder A.
Also nach S0 komme ich, also wenn ich von S0 irgendwie laufen will,
wieder auf S0.
Was muss ich dann für Zeichenfolgen eingegeben haben?
Da muss ich ein A eingegeben haben und nach dem A ein A oder ein B.
Dann bin ich wieder bei S0.
Es gibt noch eine andere Möglichkeit, ich kann über B gelaufen sein,
also mit B angefangen haben nach S0.
Dann muss nach einem B eine beliebige Folge von B gewesen sein,
deswegen ein B-Stern.
Da kann ich also hier in dem S1 bleiben.
Danach muss ein A gekommen sein, damit ich nach S2 komme.
In S2 kann ich beliebig viele As geschrieben haben und nach diesen As
muss noch ein B gekommen sein.
Das sind jetzt zwei reguläre Ausdrücke, A mal A plus B und BB-Stern A,
A -Stern B, die genau diese beiden Zyklen beschreiben.
Diesen Zyklus und den Zyklus.
Und die kann ich natürlich beliebig oft machen.
Den hier auch beliebig oft.
Ich kann beliebig oft da durchlaufen und komme immer wieder nach S0
zurück.
Und ich weiß, wenn ich in S0 gewesen bin, muss ich noch ein A
dazufügen, damit ich nach S3 komme und das Wort akzeptiert wird.
Also sieht auch die Sprache für diesen Automaten wie folgt aus.
Ich muss anfangen entweder mit A mal A plus B oder habe BB-Stern A, A
-Stern B.
Ich kann das beliebig oft machen, also das eine oder das andere.
Hier stand jedes Mal ein Stern dran, das kann ich genauso gut nach
draußen ziehen.
Kann also beliebig oft in diesen einzelnen laufen.
Erst die eine Schleife, dann die andere Schleife und so weiter.
Und muss am Ende noch ein A dahinten dran schreiben.
Und damit habe ich genau den Ausdruck, den ich brauche.
Dieses hier beschreibt die Menge aller Wörter, die bei diesem
Automaten dazu führen, dass ich beginnend von dem Anfangszustand S0
irgendwann auf den Zustand S3 komme.
Das ist hier nochmal genauer aufgeschrieben.
Da steht genau das drin, was ich hier gerade so aufgemalt habe.
Auch dazu gibt es schon wieder eine Frage.
Was sind die Kriterien für Nicht-Regularität?
Also, wie gesagt, eine Sprache ist regulär, wenn sie durch einen
regulären Ausdruck beschreibbar ist.
Das heißt, wenn sie aus den ein-elementigen Basismengen durch endlich
häufiges Anwenden von Vereinigung, Produkt und Iteration erzeugt
werden kann.
Eine Sprache, die ich auf diese Art und Weise nicht erzeugen kann, die
ist nicht regulär.
Ich habe jetzt für reguläre Sprachen kein Pumping Lemma in dem Sinne,
für diese formale Beschreibung.
Ich habe aber für eine andere formale Beschreibung dieser Sprachen,
nämlich für die endlichen Automaten, von denen wir wissen, sie
beschreiben genau die gleiche Sprachklasse, ein Pumping Lemma
abgeleitet.
Und mit diesem Pumping Lemma kann ich für eine Sprache, die mich
interessiert, überprüfen oder feststellen, dass sie nicht von einem
endlichen Automaten akzeptiert werden kann, wie die Sprache A hoch N,
B hoch N.
Und damit weiß ich durch dieses Pumping Lemma für die endlichen
Automaten, dass diese Sprache dann auch nicht regulär ist.
Denn sonst würde sie ja von einem endlichen Automaten akzeptiert
werden können.
Also insofern haben wir hier für Nicht-Regularität auch das Pumping
Lemma.
Das basiert zwar nicht auf der Beschreibung durch solche Terme,
sondern basiert auf dem Modell mit den endlichen Automaten, aber das
können wir ja verwenden.
Wenn wir also fragen, ist eine Sprache eventuell nicht regulär,
verwenden wir das andere Modell mit den endlichen Automaten und können
dann über das Pumping Lemma bzw.
diese Folgung aus dem Pumping Lemma sofort, wenn das der Fall ist,
zeigen, diese Sprache wird nicht akzeptiert.
Ein Beispiel wäre A hoch N, B hoch N.
Das also zu dieser Frage.
Damit haben wir jetzt also gesehen, wie wir zu einem endlichen
Automaten einen regulären Ausdruck erzeugen können.
Das ist hier ein nicht ganz einfaches Beispiel, aber noch nicht sehr
kompliziert.
Sie werden andere Beispiele sehen, bei denen es manchmal ein bisschen
länger dauert, bis Sie herausfinden, was eigentlich der reguläre
Ausdruck ist.
Und etwas, was ich Ihnen auch sofort sagen muss dabei ist,
selbstverständlich können Sie jeweils viele verschiedene reguläre
Ausdrücke angeben, die die gleiche Sprache definieren.
Das ist nicht eindeutig.
Statt der Iteration kann ich natürlich auch, ich kann das mehrfach
hinschreiben einfach.
Über Vereinigung kann ich ja beliebig viele identische Mengen
definieren, die ich vereinigen kann.
Das ist alles nicht so, da gibt es viele verschiedene Möglichkeiten.
Das ist nicht eindeutig bestimmt.
Es gibt manchmal welche, die sind dann besonders einfach.
Aber wenn auf 2,65 die Klammer aufgelöst wird, wird das A auf beide
Summanden angewendet, also reingezogen.
Stimmt das dann noch?
Also, selbstverständlich stimmt das noch.
Ich meine dieses Beispiel hier, das ist ja 2,65.
Dieses A wird auf beide Klammern angewendet.
Aber eben, hier steht ja noch die Iteration.
Iteration vor Klammer.
Das war die Regel.
Wir müssen ja erst alle folgen, in dem Fall hier, dieser beiden Terme.
Das sind die beiden Terme, die wir haben.
Dieser hier, A mal A plus B und B B-Stern A A-Stern B.
Die werden beliebig oft iteriert, die Sprachen.
Das sind die beiden Sprachen, die wir hier haben, die werden beliebig
oft iteriert.
Und darauf wird das A dahinter geschrieben.
Es ist ja nicht so, dass ich zunächst mal das A hier in die Klammer
ziehe und dann iteriere.
Die Iteration hat Vorrang vor der Klammer.
Ich mache die Klammer, das hier wird iteriert und dann kann ich das
Produkt bilden.
Ich kann nicht einfach A mal Klammer machen und dann iterieren, das
geht nicht.
Also hier muss man die Reihenfolge der Operationen machen.
So, das war jetzt schon genug zu dieser Beschreibungsart.
Operationelle Methode, wir können durch Operationen Sprachklassen
beschreiben.
Was jetzt noch fehlt in diesem Kapitel, ist die Beschreibung der
Sprachen durch Grammatiken.
Jetzt kommen wir also zu dieser Art der Beschreibung von Sprachen
zurück.
Die erzeugende Methode, die ich Ihnen ganz zu Anfang schon dargestellt
habe.
Da hatten wir diese verschiedenen Chomsky Grammatiken.
Jetzt kommen wir zurück zu der Definition der Chomsky Grammatik.
Zur Erinnerung, die hatten wir beschrieben durch eine Menge von Nicht
-Terminalsymbolen, durch Terminalsymbole, durch eine Regelmenge.
Wobei bei den Regeln jeweils links und rechts irgendwelche Zeichen
stehen, also Zeichenfolgen.
Und das heißt, wir wollen daraus dann Wörter ableiten.
Mal sehen, ob das noch eine Frage ist zum... ok, das ist in Ordnung.
Dann war das also die allgemeine Definition von Chomsky Grammatiken.
Sie erinnern sich an diese Hierarchie, die wir definiert hatten.
Immer eingeschränktere Anforderungen an die Grammatik, beziehungsweise
weitere Anforderungen an die Regeln der Grammatik.
Und die Typ-3-Grammatiken, die rechtslinearen Grammatiken, waren
gerade die, bei denen die Regeln sehr einfach sind, nämlich links
immer nur ein einziges Nicht-Terminalzeichen und rechts entweder ein
leeres Wort oder ein einzelnes Terminalzeichen oder ein
Terminalzeichen gefolgt von einem Nicht-Terminalzeichen.
Das ist hier formal aufgeschrieben.
Die Regelmenge ist eine Teilmenge dieses Kreuzproduktes.
Links nur Nicht-Terminalzeichen und rechts entweder Terminalzeichen
oder Terminalzeichen gefolgt von Nicht-Terminalzeichen oder das leere
Wort.
Das ist eine rechtslineare Grammatik.
Und wir werden sehr schnell sehen, dass wir damit genau die gleichen
Sprachen beschreiben können wie mit den endlichen Automaten oder
regulären Ausdrücken.
Also, da wir nur solche Regeln haben, auf A mal B, also wo rechts ein
Nicht -Terminalzeichen geht, kann man also jeweils nur ganz rechts
jeweils ein Zeichen ersetzen.
Wir werden dazu gleich noch genügend viele Beispiele sehen.
Hier ist ein einfaches Beispiel, bei dem wir eine Nicht
-Terminalzeichenmenge A, S haben.
Dabei ist S das Startsymbol, Terminalzeichen A und B.
Und unsere Regelmenge sieht so aus.
Wir können aus dem S ein AS erzeugen, aus dem S auch ein BA erzeugen
und das A ersetzen durch A.
Welche Wörter sind da drin?
Das ist also relativ einfach.
Dieser eine...
Aus diesem einen Regeln, S auf AS, kann ich A hoch N, S erzeugen.
Wie mache ich das?
Aus S leite ich ab, unter Anwendung der Regeln der Grammatik, das ist
die Regel, die ich nehme, A, S.
Daraus leite ich ab, Sie erinnern sich, der Doppelfeil war das
Ableiten eines Wortes aus einem anderen Wort durch Anwenden einer
Regel.
Jetzt kann ich dieses Zeichen S wieder ersetzen, also habe ich hier A,
A, S.
Entsprechend kann ich das weiter ableiten auf A, A, A, S.
Und durch weitere Iterationen komme ich dann gerade hier auf dieses
zum Beispiel A hoch N, S, wie hier angegeben.
Also beliebige Folge von As gefolgt von einem S ist ein Wort, das ich
ableiten kann aus dem Startsymbol.
Ich kann auch die andere Regel anwenden, S auf B, A.
Wenn ich dann S durch B, A ersetze und dann anschließend das A auch
ersetze, dann kommt eben gerade eine Menge von Wörtern zustande, bei
der ich erst eine beliebige Folge von As erzeuge.
Dann das B mit dem A, also hieraus würde ich jetzt erzeugen A hoch N,
B, A.
Und daraus würde ich erzeugen A hoch N, B klein A.
Das besteht nur noch aus Terminalzeichen, da kann ich nichts weiter
ersetzen.
Das ist also mein Wort, das dann in der Sprache drin ist.
Und damit habe ich eine sehr einfache Sprache beschrieben.
Sie wissen sofort, die Sprache kann ich natürlich auch sofort als
regulären Ausdruck hinschreiben.
Das wäre also die Sprache A-Stern-B-A.
Auch A-Stern ist richtig, ich muss nicht mindestens ein A erzeugen,
ich kann auch ohne ein A sofort ein B erzeugen, ein B-A und dann das A
hintendran.
Also A-Stern-B-A ist die Sprache, die hier angegeben ist in dieser
Mengenschreibweise.
Und das ist also hier ein einfaches Beispiel für das Ableiten.
Hier unten steht nochmal so eine Ableitungsfolge für das Wort A hoch
3, B, A.
Gut, damit kommen wir jetzt noch zum weiteren Beispiel.
Wir suchen jetzt für eine... also das war gerade eben aus einer
Grammatik eine Sprache erzeugen.
Jetzt haben wir eine bestimmte Sprache, wollen dafür eine Grammatik
erzeugen.
Solche Aufgaben werden Sie natürlich auch bearbeiten dürfen.
Dass wir eine Sprache irgendwie definieren.
Hier sagen wir, sie enthält eine ungerade Anzahl Einsen.
Sie wissen, die Sprachen, die wir Ihnen als Futter geben zum
Bearbeiten, zum Lernen, was damit gemacht ist, sind immer sehr
einfach.
Und die realistischen Sprachen, die Sie brauchen, um
Programmiersprachen...
oder die Programmiersprachen sind viel zu kompliziert.
Da können wir höchstens Teile von nehmen, wie meinetwegen
Identifikatoren oder arithmetische Ausdrücke oder ähnliches.
Auch dafür werden Sie Beispiele sehen gleich oder etwas später, nicht
in diesem Kapitel.
Das sind dann so Teile, die wir mal als Aufgaben machen können oder
auf Folien zeigen können.
Die richtigen realen Grammatiken usw.
werden natürlich immer deutlich aufwendiger sein.
Aber das methodische Rüstzeug gewinnt man genauso bei diesen einfachen
Beispielen.
Und gerade Anzahl Einsen.
So eine Sprache hatten wir schon mal angesehen.
Da hatten wir damals einen Automaten konstruiert.
Jetzt konstruieren wir eine Grammatik, die genau diese Sprache
erzeugt.
Das ist also die Sprache, die so aussieht, wie hier angegeben.
Sie erinnern sich, der Automat dazu sah so aus.
S0, S1.
Und mit einer Eins gingen wir von S0 nach S1.
Mit einer Nullen blieben wir in S0.
Wenn wir in S1 sind, mit Nullen blieben wir in S1.
Mit Eins gehen wir zurück.
Was machen wir hier bei dieser Ableitung?
Wenn wir aus S jetzt zum Beispiel eine Null erzeugen.
Wenn wir da Null S hinschreiben, das können wir also beliebig oft
machen.
Beliebig oft können wir also irgendeinen Null hoch I hinschreiben.
S.
Dann können wir auch mal ein Eins ableiten.
Aber wenn wir ein Eins ableiten wollen, dann müssen wir dahinter ein A
schreiben.
Also könnte hier Null hoch I und dann Eins A stehen.
Dann können wir die Regeln A auf Lambda anwenden, also das A
rausstreichen.
Dann wären wir fertig.
Dann hätten wir ein Eins dort drin.
Wir könnten eine Eins erzeugen, dann wären wir wieder bei S.
Wir könnten auch eine Null hinschreiben und das beliebig oft.
Also wir könnten jetzt durch beliebig häufiges Anwenden daraus Null
hoch I, Eins Null hoch J machen.
Wenn wir eine Eins erzeugen, dann natürlich wieder ein A dahinter.
Wir könnten mit einer Eins jetzt entsprechend daraus Null hoch I, Eins
Null hoch J, Eins S machen.
Und jetzt können Sie aus dem S was Gleichartiges erzeugen wie das, was
wir hier zu Anfang gemacht haben.
Also beliebige solche Folgen.
Und auf eine vollständige Folge von Terminalzeichen können wir nur
kommen, wenn wir das A durch ein Lambda ersetzen.
Das S kriegen wir nicht weg, wenn das da drin ist.
Das können wir nur durch Null S oder Eins A ersetzen.
Das A können wir rauswerfen, indem wir das A auf Lambda rausstreichen.
Und wenn man das A rausstreicht, dann hat man entweder eine Eins da
drin oder man ist, nachdem man zwei Einsen hatte, diese beiden Einsen
dort von dem S durch eine weitere Eins wieder auf A gekommen.
Man hat also eine ungerade Anzahl von Einsen in dem Wort und hat dann
das A rausgeworfen.
Das heißt, das ist genau die Grammatik, die diese Wörter erzeugt.
So, das war der Automat.
Und wenn Sie sich das anschauen, hier die Regel S auf Eins A oder Null
S und A auf Eins S oder Null A.
Das sieht aber sehr ähnlich aus wie das, was wir hier in dem Automaten
aufgeschrieben hatten.
Und man kann also hier eine sehr einfache Analogie feststellen.
Wir haben beim Automaten zwei Zustände gehabt, bei der Grammatik zwei
Nicht -Terminalsymbole.
Wir haben beim Automaten einen Anfangszustand S0, wir haben bei der
Grammatik ein Startsymbol S.
Wir haben einen Endzustand S1 beim Automaten, bei der Grammatik haben
wir ein Symbol A.
Das entspricht so ein bisschen diesem Endzustand und wir können über A
auf Lambda das Abarbeiten im Prinzip oder das Erzeugen von Zeichen
beenden.
Das heißt, wir können dort aufhören mit der Erzeugung eines Wortes.
Das entspricht dem, was wir in dem Automaten als Endzustand
beschrieben haben.
Und wenn wir also hier hingeschrieben haben, ein Übergang, Delta von
S0, 1 war S1, dann haben wir hier die Regel S geht auf 1 und ich
schreibe da das Zeichen A hin.
Also es sieht sehr ähnlich aus.
S0, S1 entsprechen gerade S und A und die Regeln sehen ja wirklich,
also der Übergang zwischen den Zuständen und die Regel passt genau
dazu.
Und das kann ich jetzt entsprechend systematisch machen.
Ich kann also, was man sofort vermutet ist, dass das sehr äquivalente
Konzepte sind und wir können das auch systematisch machen.
Wir können aus einem deterministischen endlichen Automaten sofort eine
rechtslineare Grammatik erzeugen.
Wie machen wir das?
Die Menge der Nicht-Terminalsymbole simuliert die Zustandsmenge.
Also wir haben als Eingabe einen endlichen Automaten.
Ausgabe eine rechtslineare Grammatik, die dazu äquivalent ist.
Das heißt, die gleiche Sprache beschreibt.
Wir haben also mit den Nicht-Terminalsymbolen die Zustandsmenge des
Automaten charakterisiert oder simuliert.
Die Terminalsymbole entsprechen gerade dem Eingabealphabet des
Automaten.
Und wenn wir uns die Überführungsfunktion anschauen, dann erzeugen wir
für jede Überführung eine Regel, die entsprechend gerade die Nicht
-Terminalzeichen verknüpft unter Einsatz des Zeichens, das die
Überführung im Automaten gewährleistet hat.
Und wenn wir solche Regeln haben, S auf Lambda, dann sind das gerade
die Regeln, die für einen Endzustand den Abbruch einer Ableitung
ermöglichen.
Also, genau das ist hier unten aufgeschrieben.
Der endliche Automat hat ein Eingabealphabet, Zustandsmenge,
Überführungsfunktion, Anfangszustand, Endzustandsmenge.
Die Grammatik hat Nicht-Terminalzeichen, Terminalzeichen, Regelmenge
und ein Startsymbol S.
Ich schreibe hier S-Index G, um anzudeuten, das ist das Startsymbol
dieser Grammatik.
Das hat nichts zu tun mit der Zustandsmenge des Automaten S.
Und die soll equivalent sein.
Und dann fangen wir an, indem wir diese Menge T mit E identifizieren,
N mit S, wie oben angedeutet.
Das ist hier diese Idee.
Und die Regelmenge ist zu Anfang leer.
Und das Startzeichen von SG soll gerade das S0, dem also gerade
entsprechen.
Und jetzt sagen wir, wenn wir eine Überführung haben, die einen
Zustand S beim Zeichen E nach S' überführt, dann fügen wir eine Regel
hinzu zu unserer Grammatik, bei der links ein S steht und rechts E-S'.
Hier unten sind S und S' und E jeweils die Nicht-Terminal- und
Terminalzeichen meiner Grammatik.
Damit ist das hier eine Regel.
Und das machen wir für jede Überführung, damit haben wir eine Menge
von Regeln aufgeschrieben.
Und für jeden Endzustand fügen wir eine Regel hinzu, bei der wir
dieses S ersetzen durch Lambda.
Das S ist in dem Fall eben kein Zustand, sondern hier oben ist es ein
Zustand, da unten ist es ein Nicht-Terminalzeichen der Grammatik und
damit sind wir fertig.
Das ist die ganz einfache Konstruktion einer Grammatik aus einem
endlichen Automaten.
Und andersrum geht das natürlich genauso, da machen wir aber einen
nicht -deterministischen endlichen Automaten.
Wir können also nicht sofort einen, oder es wäre aufwendiger, daraus
einen deterministischen zu machen.
Das brauchen wir ja nicht.
Wir wählen also immer das passendste Modell.
Nochmal zu dieser Bemerkung.
Also, wenn wir eine Regel haben, A auf AB, eine rechtslineare Regel,
dann mache ich daraus eine Übergangsvorschrift für meinen Automaten,
der natürlich als Zustandsmenge gerade die Nicht-Terminalzeichen
meiner Grammatik hat.
Und für diesen Zustand, jetzt Zeichen A, bei Eingabe von klein a, das
hier, soll B ein möglicher Folgezustand sein.
Warum muss ich hier Nicht-Determinismus einfügen?
Es könnte ja sein, dass ich aus einmal diese Regel habe, A auf AB, es
könnte aber auch eine Regel geben, A auf AC, oder A auf...
Ups, Entschuldigung, da habe ich ein Zeichen vergessen.
Es könnte sein, dass ich als weitere Regel habe AC, es könnte sein,
dass ich hier auch AD habe.
Ich kann ja mehrere Regeln haben.
Und dann müssten B, C und D in dieser Menge der Folgezustände sein,
von dem A bei Eingabe von A.
Diese drei Möglichkeiten habe ich.
Deswegen brauche ich hier nicht-deterministischen Automaten.
Sie sehen, wie praktisch das ist, dass wir den eingeführt haben.
Wenn ich das deterministisch machen wollte, wäre es deutlich
aufwendiger.
Ich kann auch sagen, es gilt für alle Wörter, dass ich aus der
Konfiguration, bei der ich im Zustand A bin, und das A eingebe und das
W noch abarbeiten muss, die Folgekonfiguration, das B ist, und es muss
das W noch abgeleitet werden.
Das ist dieser Übergang.
Also, das ist halt diese Überführung.
So könnte ich aus der Regel eine Überführung im Automaten machen.
Und wenn ich also eine Regel habe, A auf Lambda, dann sage ich, A ist
ein Endzustand.
Das passt zu dem, was wir vorher auch überlegt haben.
Wenn ich das A ersetze durch das leere Wort, habe ich eine Erzeugung
beendet.
Dann muss ich im Endzustand sein.
Deswegen muss das A dann ein Endzustand sein.
Und wenn ich von A auf das kleine A gehe, wenn ich also ein A ersetze
durch ein Zeichen, dann wird es ein bisschen komplizierter.
Dann muss ich einen weiteren Endzustand erzeugen.
Also von dem Zustand in dem Fall wäre ich also in einem Zustand A und
würde ein A lesen und gehe dafür in einen besonderen, den nenne ich
jetzt Sigma Null, hätte auch Sigma nennen können, einen speziellen
Endzustand, von dem aus ich nicht weitermachen kann.
Von dem brauche ich keine weiteren Übergänge zu haben.
Ich muss nur in den hineinkommen können durch die Eingabe dieses A.
Dann habe ich das Wort akzeptiert, von dem aus geht es nicht weiter.
Aber das ist ein Endzustand.
Das sind die Regeln, die ich hier erzeugen muss.
Das ist hier als Algorithmus aufgeschrieben.
Eine Rechtslineargrammatik wird eingegeben.
Es entsteht ein nicht deterministischer Automat.
Und das, was ich gerade beschrieben habe oben, war, dass wir in der
Grammatik die Übergänge A auf AB haben.
Und für jede solche Regel muss das Zeichen B in der Menge der
Folgezustände sein.
Wenn ich also Zustand groß A bin und das kleine A eingebe, muss jedes
solche B entsprechend da drin sein.
Das ist das, was ich hier oben angedeutet habe.
Das ist also hier diese Bemerkung gewesen.
Es kann sein, dass die Menge leer ist.
Es kann sein, dass die aus einem Element besteht.
Es kann sein, dass die aus vielen Elementen besteht.
Und wenn eine solche Regel A auf A drin ist, dann brauche ich eben
auch noch die Möglichkeit, dass ich...
Und hier ist es so, in dem Fall sage ich, dass es dieses Delta A, A
vereinigt mit Sigma 0.
Ich mache ja hier sukzessive eine Erweiterung dieser Mengen.
Es kann ja sein, dass ich von dem A aus eine ganze Reihe von
Überführungen habe.
Es kann ja sein, dass hier einfach nur die weitere Regel A noch dabei
ist.
Dann muss ich natürlich die BCD in der Folgezustandsmenge drin haben,
aber eben auch diesen Zustand Sigma 0, damit ich auf diesen Endzustand
kommen kann.
Und das war es schon.
Dann muss ich noch sagen, dass ich von dem Sigma 0 aus nicht
weiterlaufen kann.
Dann bin ich fertig.
Also auch eine sehr einfache Äquivalenzbeziehung zwischen diesen
rechtslinearen Grammatiken und den nicht-deterministischen endlichen
Automaten.
Und damit bin ich schon fertig mit diesem Teil.
Hier nochmal ein Beispiel.
Wir haben hier diese einfache Grammatik, die gerade dazu diente, die
Sprache, die Wörter zu akzeptieren, die eine ungerade Anzahl von
Einsen haben.
Hier ist nochmal der Algorithmus angegeben, den wir gerade beschrieben
haben.
Zu einer solchen Grammatik wollen wir einen endlichen Automaten
konstruieren.
Das liefert dann gerade diesen Automaten von S aus.
Wo haben wir die Regeln der Grammatik?
Von S aus kann ich mit 0 nur auf 0S kommen.
Das heißt, die Menge der Folgezustände ist gerade die Menge, die aus
dem S besteht.
Unter 1 komme ich auf A, also ist die Menge der Folgezustände gerade
die Menge, die nur aus dem einen Symbol A besteht.
Wenn ich in Zustand A bin, dann kann ich mit 0 bei dem A bleiben und
mit 1 komme ich zu der Menge von Zuständen, in diesem Fall nur der
eine Zustand S drin.
Und von dem Sigma 0, wir haben hier noch die Regel A auf Lambda drin,
Sigma 0 kann man noch dazu schreiben, da komme ich gar nicht hin, das
hätte ich auch genauso gut rausstreichen können.
Also das brauchen wir in dem Fall gar nicht, weil wir diese gar nicht
erreichen können.
Wir haben keine Regel, bei der wir A durch irgendwie nur ein Zeichen
ersetzen.
Also Sigma 0, wenn wir das da drin haben, würden wir hier nur auf die
leere Menge gehen.
Das Sigma 0 ist gar nicht erreichbar, deswegen könnte man die Zeile
auch gleich wieder rausstreichen.
Und entsprechend können wir das auch hier unten gleich wieder
rausstreichen.
Ich könnte es auch jetzt formal, wenn Sie wollen, dass ich das mit den
üblichen Beschreibungen für...
Also wir haben immer Zustände beschrieben als irgendein S0, S1, S2
usw.
Ich kann auch schreiben, das ist dann ein S0 und SA und SA und S0 und
dann ist das aber der gleiche Automat.
Also das ist dann der Automat, wobei ich hier dieses Sigma 0
eigentlich gar nicht brauche.
Das hätte ich eigentlich gestern Abend auch gleich rausstreichen
können.
So, die brauchen wir also, das Sigma 0 brauchen wir in dem Fall nicht.
Das Sigma 0 brauchen wir, das steht im Algorithmus natürlich drin, der
wird erzeugt, nur wir sehen sofort, wir können den vereinfachen,
können das Sigma 0 wieder rausstreichen, weil das Sigma 0 gar nicht
erreicht wird.
Der Algorithmus erzeugt das mit dem Sigma 0, aber das steht ja hier
oben, da steht Zustandsmenge ist das N vereinigt Sigma 0.
Insofern wird das durchaus erzeugt, wir können es aber gleich wieder
rausstreichen, weil der Zustand Sigma 0 gar nicht erreicht wird.
Okay, damit sind wir mit dieser Konstruktion auch fertig.
Und wir sehen natürlich, der ist dann nicht deterministisch, das stört
uns nicht, wir wissen, das ist äquivalent zu den anderen.
Ich kann daraus einen deterministischen Automaten machen, das brauchen
wir bei diesem Fall gar nicht zu tun.
Und ich weiß damit, dass die rechtslinearen Grammatiken äquivalent
sind zu den endlichen Automaten.
Und damit ist das also alles genau äquivalent.
Und wir haben damit jetzt diese Folgerung, dass die verschiedenen
Sprachklassen hier alle identisch sind.
Sprachen, die durch Typ 3 Grammatiken erzeugt werden, Sprachen, die
durch endliche Automaten akzeptiert werden, Sprachen, die durch nicht
deterministische endliche Automaten akzeptiert werden, Sprachen, die
durch reguläre Ausdrücke spezifiziert werden können.
Das sind alles die gleichen Sprachen und das ist auch noch die Menge
der Sprachen, die durch reguläre Ausdrücke.
Also das ist hier die Menge der Sprachen, die aus Basismengen durch
endlich häufiges Anwenden von Vereinigung, Produkt und Iteration
erzeugt werden.
Und das hier ist die RA von E, die Menge der Sprachen, die durch
reguläre Ausdrücke beschrieben werden.
Wir wissen, die sind alle identisch.
Und damit haben wir jetzt schon mal eine gewisse Erkenntnismenge
erzeugt hier.
Und das Wesentliche ist, dass wir wissen, dass sämtliche Aussagen, die
für eine Sprachklasse abgeleitet wurden, auch für die anderen
natürlich gelten.
Das hatte ich in einem Beispiel schon dargestellt, als die Frage kam,
woher weiß ich, dass eine Sprache nicht von einem regulären Ausdruck
beschrieben werden kann, indem ich zeige, dass ich zeigen kann, die
kann nicht von einem endlichen Automaten akzeptiert werden aufgrund
des Pumping Lemmas.
Und damit wissen wir auch Dinge zu Überausdrucksfähigkeit, Komplexität
und so weiter.
Und man wird also je nach Anwendung die günstigste Art der
Sprachdefinition wählen, entweder erzeugend oder analysierend oder
operativ.
Damit haben Sie drei verschiedene formale Modelle kennengelernt mit
entsprechenden Eigenschaften.
Und damit sind wir bei der letzten Folie dieses Kapitels.
Die wesentlichen Erkenntnisse sind also deterministisch und nicht
-deterministisch, endliche Automaten sind gleichmächtig.
Das andere, die nicht-deterministischen liefern eine kürzere
Darstellung der wesentlichen Eigenschaften.
Pumping Lemma charakterisiert Eigenschaften dieser Sprachen, also
Struktureigenschaften.
Die rechtslinearen Grammatiken, regulären Ausdrücke bringen nichts
Neues, sondern sind eben nur andere Arten, das darzustellen.
Und ich kann außerdem die endlichen Automaten sehr klein machen, indem
ich sie reduziere.
Ich kann also versuchen, kostengünstigste Realisierung eines endlichen
Automaten zu erzeugen.
Das sind die wesentlichen Erkenntnisse.
Und was ich nicht geschrieben habe hier, ist natürlich, es gibt eine
Sprache...
Achso, hier steht es, dass eine Sprache eben nicht erzeugt werden
kann, insbesondere Sprachen mit Klammerschachtelungen.
Und wir wissen natürlich, dass Klammerschachtelungen etwas sind, was
wir in jeder Programmiersprache darstellen können müssen.
Deswegen reicht diese Sprachklasse nicht aus und wir schließen
deswegen dieses Kapitel ab.
Das waren die endlichen Automaten.
Und wir können dann kommen zu der nächsten Sprachklasse, die hier
entsprechend in meinem Verzeichnis irgendwo aufbewahrt ist.
Die ich auch gestern Abend noch schnell Ihnen bereitgestellt habe.
Bei Ilias und Kapitel 3, genau.
Da sind wir.
Da kommt das Kapitel 3, was Sie sich vielleicht noch nicht angeguckt
haben, aber womit ich auf jeden Fall beginnen kann.
Das ist also das nächste Kapitel.
Da werden wir es mit mächtigeren, formalen Modellen zu tun haben, die
mehr beschreiben können.
Das sind sogenannte Kellerautomaten und kontextfreie Sprache.
Nächste Automaten-Klasse.
Kellerautomaten.
Das sind nicht unbedingt Automaten, die irgendwo im Keller sind.
Das sind dann vielleicht auch Kellerautomaten, aber andere.
Also Kellerautomaten haben eine gewisse Eigenschaft.
Und das ist eine Erweiterung endlicher Automaten, bei der wir einen
unbeschränkt großen Speicher dazunehmen.
Was ist die Idee von diesem Speicher?
Sie sehen hier so eine komische Konstruktion.
Das kennen Sie.
Das kommt gleich hier.
Ich muss hier erstmal meinen Stift wieder auswählen.
So, wir haben ein Eingabeband.
Da steht unser Wort drauf, das wir abarbeiten wollen.
Das Eingabeband führen wir unserem Lesekopf vorbei.
Der Automat, der hat selbstverständlich wieder Zustände.
S0 bis Sn, irgendeine Zustandsmenge.
Wir haben den Schreiblesekopf und wir haben offensichtlich noch ein
bisschen mehr.
Wir haben einen Kellerspeicher.
Stellen Sie sich vor, ich gebe Ihnen mal ein Beispiel, dass wir damit
in der Lage sind, dieses Wort A-A-A-B-B-B zu erkennen, dass das auf
dem Band steht.
Wie macht man das?
Wenn wir ein A lesen, wir haben hier einen Keller zur Verfügung.
Stellen Sie sich vor, Sie haben einen Keller.
Sie graben eine tiefe Grube, das ist Ihr Keller.
Und Sie haben ein A gelesen, das werfen Sie einfach hier unten rein
und machen weiter.
Sie lesen das nächste A, Sie werfen das A hier wieder rauf.
Sie lesen noch ein A und Sie werfen das A hier oben in den Keller.
Dann lesen Sie ein B.
Sie gucken in den Keller und sagen, oh, da ist ein A.
Dieses A, das lösche ich wieder raus.
Ich lese noch ein B, Sie gucken in den Keller und sagen, oh, da ist
noch ein A, das lösche ich raus.
Dann lese ich noch ein B, gucke in den Keller und stell fest, oh, da
ist noch ein A, das lösche ich raus.
Und jetzt habe ich drei A's und drei B's gelesen.
Und ich weiß, dass ich genauso viele A's wie B's gelesen habe in
dieser Reihenfolge, weil ich ja für jedes B, das ich gelesen habe,
dort immer ein A im Keller gesehen habe, das ich vorher reingelegt
habe.
Das ist das Prinzip des Kellers.
Ich kann auch sagen, ich habe einen Schreibtisch und da sitzt
irgendjemand dran, der hier irgendwas machen will.
Und bei dem legt man immer irgendwelche Arbeit drauf und der arbeitet
so, dass er das, was als letztes gekommen ist, als erstes wieder
runtergenommen wird.
Das ist das Prinzip Last In First Out.
Das LIFO-Prinzip.
Und das ist auch das Kellerbearbeitungsprinzip.
Ich kann das, was ich als letztes reingelegt habe, anschauen.
Das war hier irgendwelche Zeichen drin, das ist hier angedeutet.
Ich habe ein Band, da steht jetzt unten noch ein Zeichen K0 drauf.
Das Problem ist nämlich, wenn ich hier reingucke und stell fest, oh,
der Keller ist leer.
Was heißt denn das, der Keller ist leer?
Ich sehe da unten den Boden dieses Kellers.
Und den Boden des Kellers bezeichne ich mit einem speziellen
Kellerbandzeichen K0.
Also wenn ich K0 sehe, heißt das, aha, das ist der Boden des Kellers.
Und dieses K0 wird nie rausgenommen.
Aber obendrauf können irgendwelche Zeichen sein, die habe ich hier
draufgelegt.
Und das oberste Zeichen kann ich immer anschauen, hier das oberste
Zeichen.
Und ich kann da was Neues draufschreiben, ich kann es ersetzen, ich
kann auch Sachen rauswerfen.
Und dann kann ich weiter runtergucken.
Ich kann aber nie in den Keller weiter unten reinschauen, um also
hier, wenn ich hier irgendwas drin habe, irgendwelche Elemente, um da
hinzukommen, muss ich den ganzen Teil erstmal rauslöschen.
Das ist das Kellerprinzip.
Last in, first out.
Und Sie sehen, ich habe Ihnen als Anfangsbeispiel sofort gezeigt, wie
man A hoch 3, B hoch 3 intuitiv mit so einem Kellerprinzip erkennen
kann.
Das heißt, das, was wir mit den endlichen Automaten nur mit endlich
vielen Zuständen nicht konnten, nämlich zählen, das können wir mit so
einem Keller machen.
Zumindest können wir gewisse Zählvorgänge damit machen.
Und das müssen wir jetzt formal aufschreiben.
Das, was ich hier gerade eben so intuitiv dargestellt habe, wie man
ein solches Kellerprinzip nutzt, um zum Beispiel A hoch 3, B hoch 3 zu
akzeptieren.
So, das ist also nochmal dieses Bild.
Und jetzt müssen wir das nochmal genau erläutern.
Zustandsübergänge abhängig von natürlich dem aktuellen Zustand.
Welcher dieser Zustände ist gerade aktuell?
Was steht hier auf dem Eingabeband?
Und was steht hier auf dem Keller obendrauf?
Alle Informationen, die wir haben, können wir ausnutzen.
Alle uns verfügbaren Informationen.
Und wir können dann etwas tun.
Wir können abhängig von Zustand, Eingabezeichen und Kellerzeichen zum
Beispiel das auf dem Kellerfolgendes machen.
Wir könnten das oberste Kellerzeichen ersetzen durch irgendein Wort
über dem Kelleralphabet.
K sei ein Kelleralphabet.
Auch durch das leere Wort.
Ersetzen durch das leere Wort würde bedeuten, ich lösche das Zeichen
daraus.
Und ich kann also auch was anderes reinschreiben.
Jetzt schreibe ich etwas obendrauf.
Dann würde ich halt den Kellerinhalt vergrößern.
Man nennt manchmal die beiden Operationen, das Hineinschreiben oder
das Rausholen von Informationen, auch Push und Pop.
Also Kelleroperationen, wenn Sie sich anschauen, Datenstruktur Keller,
wird häufig mit den beiden Operationen Push und Pop verbunden.
Und Push bedeutet, ich schreibe dieses Wort V auf den Keller rauf.
Das heißt, ich schreibe das Wort V K, wenn K das aktuelle Zeichen oben
ist.
Und Pop bedeutet, ich schreibe das leere Wort, ich lösche das Zeichen
K raus.
Das sind also die beiden typischen Operationen, die man für
Kellerstrukturen kennt.
Und Schreibwiese kommt immer auf dem obersten Kellerzeichen, das habe
ich schon gesagt.
Und jetzt kommt die formale Definition.
Wieder ein Mehrfachtuppel hier, haben wir also jetzt sieben Elemente
drin.
Eingabealphabet, eine Zustandsmenge hier, Zustandsmenge S.
Wir haben ein Kelleralphabet, wir können auf dem Keller natürlich
andere Zeichen verwenden als auf dem Eingabeband.
Können auch gerne die gleichen nehmen, aber es muss ein definiertes
Kelleralphabet geben.
Wir haben dieses Kellerstartzeichen K0.
Wir haben Anfangszustand S0.
Und wir haben wieder eine Menge von Endzuständen, damit wir
Entscheidungen treffen können, ob ein Wort, das wir abgearbeitet
haben, akzeptiert wird oder nicht.
Das machen wir darüber, ob der Automat in einem Endzustand ist oder
nicht.
Und wir haben eine Übergangsfunktion, die in diesem Fall aber partiell
ist.
Das ist aber seltsam.
Wieso denn partiell?
Und Sie sehen hier, wir haben hier einen Übergang abhängig vom
Zustand, von Zeichen oder dem leeren Wort und einem Kellerzeichen und
anschließend haben wir einen Zustand und einen neuen Inhalt im Keller.
Also schreiben dort irgendwas.
Die Bedingung für das Delta ist folgende.
Wenn ein Übergang für einen Zustand und ein Zeichen und ein
Kellersymbol definiert ist, dann ist für diesen Zustand mit dem leeren
Wort und diesem obersten Kellerzeichen kein Übergang definiert.
Warum braucht man das?
Ich möchte Folgendes tun können.
Ich möchte Zeichen auf meinem Band lesen können und entsprechend etwas
tun im Keller, also einen neuen Zustand und etwas auf den Keller
schreiben.
Ich möchte aber auch folgende Möglichkeit haben, dass ich das, was auf
dem Eingabeband aktuell steht, ignorieren darf.
Ich lese das einfach nicht, sondern mache erst mal intern etwas.
Und das bedeutet, ich bin in einem Zustand, in dem ich nur intern
arbeite.
Und dieses interne Arbeiten wird dadurch ausgedrückt, dass ich auf dem
Eingabeband nichts lese, sondern nur auf dem Keller irgendwelche
Veränderungen mache.
Wir werden am Montag sehen, wie man das dann entsprechend bei einigen
Beispielen macht.
Also falls das definiert ist, wird das Eingabezeichen ignoriert.
Und ich mache nur Keller- und Zustandsveränderungen.
Und ansonsten wäre der nicht deterministisch.
Wir werden später auch nicht deterministische Kellerautomaten
kennenlernen, aber das dauert noch ein kleines bisschen.
Es ist genau wie vorher ein Automat ohne Ausgabe.
Wir haben nur Endzustände.
Man könnte die auch mit Ausgaben versehen, das brauchen wir aber
nicht.
Das sei für heute genug.
Vielen Dank für die Aufmerksamkeit.
Wir sehen uns am Montag wieder.