Wir haben uns beim letzten Mal nicht deterministische endliche Automaten angeschaut, die sehr ähnlich sind zu
deterministischen, endlichen Automaten mit dem unterschied Dass die, übergangsfunktion delta Einen Funktionswert
hat der eine ganze Menge von Zuständen sein kann oder äquivalent Wer eine, Übergangsrelation haben Der Grund
war Vielleicht erstmal ganz abstrakt, dass das, was mächtigeres ist, , Wir, Können, da auch manchmal einfacher
Sachen beschreiben Aber Auch, als hilfsmittel für einen Beweis, der uns jetzt am Herzen liegt nämlich zu zeigen,
dass endlicher Automaten und Chomsky drei Sprachen das Gleiche sind also die gleiche Sprachmenge, was wir dazu gemacht
haben, waren ein paar langweilige Definitionen. Wir haben eine Übergangsfunktionen, auf Zustandsmengen definiert
Und dann Übergangsfunktionen auf Zustandsmengenkreuz ganze wörter Grafinterpretation. Das ist relativ trivial und wir
haben dann auf erstaunlich einfache Weise ein ganz zentrales ergebnis Bekommen Das Nämlich ein
nichtdeterministischer endlicher Automat, Deterministisch, Gemacht werden kann mit einem relativ einfachen Trick,
also wir haben hier Zustandsmenge alphabet Übergangsfunktion, Startfunktionen, , Wir, Bauen. Jetzt den für einen
nichtdeterministischen Automaten jetzt Bau, der heißt a und ein deterministischer Automat a Strich der, die gleiche
sprache Erkennt sieht jetzt so aus Der Der, wichtigste trick ist dass unsere Zustandsmenge jetzt , Alle,
Teilmengen, der Zustandsmenge des deterministischen Automaten sind , Oder, Wir werden gleich sehen Dass Es,
ausgleich Bestimmte Teilmengen zu nehmen die man sehr einfach konstruieren kann.
, Das, Alphabet, ist Natürlich das gleiche die Übergangsfunktion ist nichts anderes als dieses Delta quer, das war
diese Übergangsfunktion, die man Auch auf, dem deterministischen schon definieren Kann Genau
wenn man zustandsmengen sieht Die Der Staatszustand Ist Die einelementige Menge datenzustand Ist nicht
deterministischen automaten Und die Endzustände sind eben gerade die Mengen von Zuständen, die einen Endzustand des
nicht der terministischen Automaten enthalten und der Beweis war irgendwie ganz witzig, weil das ein Dreizeiler ist,
allerdings mit einem taschenspielertrick Weil, das ist delta Dach das tauscht man an einer Stelle aus, und das darf man,
weil die Definitionen genau zusammenpassen. Also, es gibt ein Delta Dach für deterministische Automaten und ein Delta
Dach für Nicht deterministische automaten aber So, wie wir diesen Automaten a Strich definiert haben ist, das das
gleiche und damit wird der Beweis trivial, ja, das war die Grundidee. Wir hatten uns auf dieses Beispiel schon
angeschaut, nicht deterministischer Automat mit vier Zuständen , Wo, Der, deterministischen dann acht Zustände hat
und hier sehen wir bereits , , Die, Menge, Aller Teilmengen von den Dingen hat der sechzehn Elemente, aber wir
brauchen nur die, die erreichbar sind durch diese Funktion delta Quer Und das war in dem Fall nur die Hälfte, das
ist die gute Nachricht, die schlechte Nachricht ist, ich kann eine ganz analoge Konstruktion machen, die mir zeigt, dass
es tatsächlich sein kann Dass Die, zustandsmenge des Deterministischen Automaten exponentiell größer ist als die
des nichtdeterministischen Automaten und sogar einem sehr einfachen Fall wir haben hier einen nichtdeterministischen
Automaten A, der im Wesentlichen sagt , Ste, Buchstabe, Des Wortes solle Null sein und ansonsten ist egal,
woher kann irgendwas kommen, das, den wir hier übergang? Null, eins von s aus, dann kommt irgendwann eine Null und
danach müssen genau k minus eins Zeichen kommen und dann habe ich meinen Endzustand Und wir werden jetzt zeigen
dass es also der jetzt k plus eins Zustände, die Maximale Anzahl zuständig brauchen würde, oder zwei hoch k plus eins.
Wir werden jetzt zeigen, dass er zwei Hochk tatsächlich brauchen, also behaupten, es gibt keinen deterministischen,
endlichen Automaten a Strich mit einer zustandsmenge Die, kleiner ist als zwei hoch k, der die Sprache l von a
akzeptiert Beweis durch Widerspruch also nehmen wir mal an, es gäbe so einen a strich es muss zwei eingabeworte länge
, Zwei, Eingabeworte, oder Zwei Wörter x und Y, dass die ungleich sind, aber wenn ich Delta dach auf s und x
anwende kriege ich das gleiche raus wie wenn ich Delta dach auf s und y Anwende Das liegt, einfach daran
Nennt Man das schubfachprinzip Man Hat Hier zwei hochk mögliche Eingaben, aber weniger als zwei Hochk mögliche
Ergebnisse Das heißt, es muss, zwei Eingaben geben, die das gleiche Ergebnis produzieren ja so, also jetzt nehme
ich mir diese Wörter X und y und wähle eine Position, wo die sich unterscheiden, also wo x i ungleich y i ist und o bda
sei jetzt x i gleich Null und y i gleich eins, wenn das nicht der Fall ist, vertausche ich einfach die Rolle von x und y
so Das Stimmt, irgendwas das Ah doch nein nein, nein, nein, das stimmt nicht, Kann Das dahin dass
hier, ein k minus i plus eins, oder das, was stehen sollte, , Also, Null, hoch K minus i plus eins, also hier das
Bild, und das tritt das eigentlich ganz gut. Also ich habe hier das x unter y, die unterscheiden sich hier an der Stelle
I hänge ich sowohl am x als auch an y eine geeignete Anzahl nullen dran, wieviel das ist, muss man noch ausrechnen und
da reinsetzen, dann endet x wie und ich will ja dann insgesamt k haben Wie Soll das kartezeichen von hinten sein
ja, okay, genau. Also das sind Hier Das hier, sind K Minus i, und dann kommen i dazu, dann sind das k plus in das
genau das, was ich brauche, okay, stimmt sogar, ja, also ich habe das jetzt so gebastelt diese neuen Wörter , X,
, x Null Hoch i Minus Eins und y Null i Minus Eins, dass Bei Diesem neuen wort tatsächlich das Kart letzte
Null ist und bei dem neuen ist das Kard Netz zu einer eins, das heißt das hier ist der N von A und das hier nicht, ja?
und jetzt habe ich ja beim Problem Wenn Ich, x beziehungsweise y in den Automaten Reinstopfe kriege ich den
gleichen Zustand. Ja, , Die, Weiteren eingaben sind Die gleichen Dafür Muss, man auch nochmal sagen, da muss
man " i " das letzte " i " nehmen da, wo die sich unterscheiden, glaube ich, sonst könnte auch noch was passieren,
danach kommen Sachen, die man nicht mehr unterscheiden kann, die machen also beide das gleiche, das heißt entweder die
werden beide akzeptiert oder beide nicht akzeptiert, aber was ich will, ist das, dass das hier akzeptiert wird und das
nicht, und das kann aber nicht funktionieren. Ja, Widerspruch.
Ja, also das bedeutet der dieser Preis, den wir für die Potenzmengenkonstruktion bezahlen, ist nicht ganz klein, es kann
mal exponentiell groß werden. Das scheint aber wohl so zu sein, dass das in der Praxis nicht so oft passiert also man
kann damit eine ganze Menge Dinge tun ja Vor Allem, wenn man die Mengen die Man braucht wirklich adaptiv
erzeugt, da ist hier Tatsächlich Mal ein kleiner Algorithmus der das also, wenn man diese
Potenzmengenkonstruktion tatsächlich Ab im Rechner durchführen will, um den deterministischen Automaten zu kriegen,
könnte man einen Pseudocode in dem der Art setzen. Es gibt zwei Mengen Kuh Strich Ist die zustandsmenge des
deterministischen Automaten und zu du, das sind die Zustände, die ich noch nicht exploriert habe am. Anfang Weiß ich nur
dass der Staatszustand drin ist. Also die Menge, die nur es enthält , Und, Ich, setze die gleich weil ich das noch
nicht verarbeitet habe, so, dann habe ich eine while Schleife, die sagt Solange , tu Du Nicht leer ist
nämlich irgendeine Menge m aus zu du also irgendein Zustand des deterministischen Automaten entferne dir aus Duo und
gucke jetzt für jedes mögliche Eingabezeichen, was ist denn Der Nachfolgezustand also Ich, Berechne Delta quer M
Komma für alle einen Sigma, wenn ich einen neuen Zustand erzeuge das Ding also nicht den Kuhstrich ist füge, ich hier
seinen Kuh Strich oder in duo Ein da die Beobachtung ist das oft Die erzeugte zustandsmenge viel Kleiner als als
zwei auch kuhbetrag Fragen dazu, und jetzt können wir tatsächlich unseren Kreis schließen Ein Zu drei grammatik in
einen Nichtdeterministischen automaten zu Übersetzen der die gleiche Sprache akzeptiert ist, passt trivial, sei ja
so g gleich, Vau Sigma, Ps, eine Typ, drei Grammatik, , Variablen, Symbole, Eingabealphabet, Produktion,
Staatenbude, jetzt betrachte ich den nichtdeterministischen endlichen Automaten a Dessen Zustände im Prinzip die
Variablen Symbole der Grammatik sind plus ein Neuer Zustand Gleiche Eingabe ,
Zustandsübergangsfunktion, Müssen, Wir Noch sagen machen wir jetzt in Relationennotationen und die Endzustände sind
, , , Ja, Das, Ist, F, oder die Menge mit dem Element F und falls es die Produktion Sna Repsilon
Auch das, groß ist oder die Menge mit dem Element Gruß es und die Übergangsfunktion ist dann einfach so, dass das eine
Produktion Q nach a q Strich, übergangsreaktion Q A Kuhstrich gibt Also Diese Ableitungsproduktionen werden
eins Eins Übersetzt, in Zustandsübergänge Des, Endlichen Automaten mit der Zusatzregel Dass,
Genau Also Die diese dinger die In den Variablen sowohl erzeugen, die werden eins zu eins in diese
Übergangsrelationen ersetzt und die, die ein Terminalsymbol ersetzt, " Haben Die werden, halt in die
Übergangsrelation In den endzustand Übersetzt Auf Den Beweis will Ich gar nicht im Detail eingehen. Man kann jetzt
wieder durch Vollständigeduktion und sehr einfach zeigen, dass es eine Eins zu eins Beziehung zwischen Ableitungen und
akzeptierenden Faden gibt also eine Ableitung.
Es sieht ja so aus bei einer Totalgrammatik fangen wir mit dem Staatssymbol an. Er erzeuge den ersten Buchstaben der
Ausgabe und ein Variablen Symbol aus dem Variablen Symbol erzeuge ich den zweiten Buchstaben und neues Variablensymbol
in jedem schritt erzeuge ich genau einen Ausgabebuchstaben Bis ich, dann das den Zweitletzten erzeugt habe und
dann hier die Variablen sowohl A N Minus Eins habe und dann wird eine Produktion angewendet, die das " A N Minus eins
durch ein Terminalsymbol ersetzt nämlich das Wm Und Dann habe ich meine Ableitung, das entspricht halt genau einem
Pfad in diesem Automaten, der gelabelt ist, wird diesen Relationen S W eins a eins a eins wie zwei a zwei a, zwei B,
drei A, drei und so weiter und das ist trivial, weil weil hier ist die eins zu eins Beziehungen und findet sich hier
direkt wieder, könnte man natürlich auch als Übungsaufgabe oder da so Aufgabe stellen, das detailliert zu beweisen, oder
die eine Richtung, zumindest weil so eine Äquivalenz müssen natürlich jemand daraus folgt in die eine und in die andere
Richtung beweisen so " ah, mir ist jetzt im Prinzip So ein kleiner einschub Also, etwas, was wir geschenkt kriegen,
, Dadurch, Dass wir, die Äquivalenz Zwischen Zu Drei und Deterministischen Endlichen
Automaten bewiesen haben Die Sagt, um mich folgendes Für Jede türkei Gibt Es eine Typ drei Grammatik,
deren Ableitung eindeutig sind. Also wo gegeben ein Wort gibt es genau eine Ableitung dieses Worts, das ist im
Allgemeinen nicht der Fall, also Sie können ganz leicht Reguläre, Sprachen angeben also, Zu, drei Sprachen
Grammatiken dafür, bei denen es mehrere mögliche Ableitungen eines Wortes gibt. Aber es gibt immer eine Grammatik, bei
der das nicht der Fall ist, und das ist natürlich interessant zum Beispiel für , Syntaxanalyse, Von von
Programmiersprachen oder Sowas ah den Beweis geziere ich auch wieder nur Man benutzt. Diese übersetzung Man
Nimmt diese Eine Chomsky Drei Sprache übersetzt sie einen nichtdeterministischen, endlichen Automaten, den
übersetzt man mit der Potenzmengenkonstruktion in einen deterministischen, endlichen Automaten, den übersetzt man mit
dieser einfachen Eins zu eins Beziehung in eine neue Showski, drei Grammatik und Für Die ist ganz leicht
nachzuweisen, dass die Ableitungen Da Eindeutig sind also eine eindeutige Ableitung und Deterministisches
Verhalten Dem Automaten das ist im Prinzip Das gleiche Werde Ich aber auch nicht im Detail beweisen Iiiso, jetzt
kennen wir schon zwei Mechanismen zur Beschreibung regulärer Sprachen, unendliche Automaten, Al. Diese Sprachen werden
ganz oft in der Praxis eingesetzt, wo dann auch der Programmierer, die spezifiziert, aber dafür verwendet man eine
dritte Notation, nämlich reguläre Ausdrücke, und die will ich jetzt erklären.
Ja, also, wenn Sie zum Beispiel irgendeine Skriptsprache wie Perl oder so verwenden, da können sie , Reguläre,
Ausdrücke, oder Noch viel mächtigere Varianten von dem, was ich hier schreibe, hinschreiben, um Pattern Matching zu
machen. Und dahinter versteckt sich aber das, was wir hier machen, ja, also was ist ein regulärer Ausdruck? das ist eine
induktive Definition.
Dieses leere Mengensymbol ist ein regulärer Ausdruck. Epsilon ist ein regulärer Ausdruck, ein Terminalsymbol als solches
ist ein regulärer Ausdruck, das sind unsere Basisfälle, kann ich aus zwei Regulären ausdrücken Alpha und Beta einen
neuen machen, in dem ich dazwischen des Mengenvereinigungssymbol, Schreibe, Oder, Das Produktsymbol Ja Ich
kann aus einem regulären Ausdruck neuen machen, indem ich Klammern Drun schreibe, indem ich einen Stern dahinter mache
oder ein Plus dahinter mache, ja, das ist jetzt eine rein syntaktische Definition, also wir müssen uns natürlich auch
überlegen, was das bedeutet , , Da, Kann, Jetzt ein bisschen Verwirrung aufkommen Weil Hier, ist es
jetzt tatsächlich so die Bedeutung und die syntaktische Seite sind jetzt sehr nah beieinander, weil wir haben bereits
entsprechende Definitionen gemacht bei unserer mathematischen Notation für Aber es, ist wichtig dass man den
unterschied versteht, und zwar nicht nur um die Beweise, die jetzt noch kommen zu verstehen, sondern auch ganz
allgemein, um zu verstehen, was passiert eigentlich in der theoretischen Informatik, oder was passiert, wenn ich Sachen
formal spezifiziere, auch jenseits dieses konkreten Beispiels reguläre Sprache in der zweiten Sprache Spalte steht jetzt
immer das, was das bedeutet, also das, was links steht, ist einfach eine Zeichenkette Ja, Da treten zum Beispiel
auch so Symbole wie , Vereinigungsmenge, Punkt, Klammern, Auf, und so weiter Das Was das, beschreibt ist
immer eine Menge von Wörtern über dem Alphabet und im Allgemeinen ist da kein Vereinigungsmengen Und keine klammern Oder
Sterne drin, das sind schon einmal zwei ganz verschiedene Dinge, das sind einfach Zeichenkette Alphabet, erweitert durch
diese Spezialsymbole, , Und, Das hier sind Mengen von Zeichenketten Über dem eingabealphabet Ja, und das
syntaktische Links beschreibt die Mengen rechts, und zwar was beschreibt das? naja, das leere Mengensymbol beschreibt
die leere Menge nicht so schwierig Dass Epsilon, beschreibt Die Menge die das leere Wort enthält das A beschreibt
die Menge, die das ein buchstabenige Wort A enthält.
Dieses Ding beschreibt die Vereinigungsmenge Von elf von alpha Und elf von Beta, also wir definieren jetzt L Von
einem regulären Ausdruck ist sozusagen dessen Ist Eine formale sprache Alpha Punkt Beta Ist elf von Alpha
Punkt Elf und Beta, also das Mengenprodukt, alle , Alle, wörter aus Alpha und dahinter irgendein Wort aus Beta ist
in der neuen Menge.
Ja, die Klammern sind jetzt erstmal ändern nichts, das ist einfach elf und Alpha Aber Ändern natürlich was wenn
ich dann noch andere Operatoren da dran mache wie hier, so diese da oder auch die Uno-R, operatoren Stern Und plus a
Stern steht halt für die klinische Hülle von elf von Alpha und plus für die positive Hülle von elf von Alpha. Ja, also
eine mögliche Eselsbrücke sich merken, warum das sehr unterschiedliche Dinge sind, ist zum Beispiel. A Stern ist eine
Zeichenkette der Länge zwei, die Bedeutung ist eine unendlich große Menge von Wörtern durch alle Wörter, die aus oder
nur aus as bestehen da damit die Verwirrung komplett wird, ist das dann so, dass in wissenschaftlichen papieren und
vielleicht auch bei uns in der Vorlesung , gelegentlich, mal, so ein Punkt oder ein l von weggelassen wird. Und
dann sieht das noch ähnlicher aus, aber das machen wir nur, wenn aus dem Kontext klar wird, ob jetzt dieser syntaktische
Ausdruck oder die Interpretation davon gemeint ist also nochmal ganz allgemein zu dem Begriff Syntax Basis
Semantik Computerprogramme Beschreiben Syntaktische Objekte. Wenn ich aber jetzt ein Computerprogramm verifizieren will.
Also wenn ich formal beweise, dass das korrekt ist, Dann muss, ich mich irgendwie auf diese semantische Ebene
begeben, was bedeutet das Hier Bei regulären sprachen war das eben die Menge dieser Wörter bei Computerprogrammen
sind das dann eher sowas wie die Mengen von Zuständen, die ein Programm annehmen kann oder sowas und sie werden das
gleiche in der Prädikatenlogik in der Vorlesung formale Systeme zum Beispiel kennenlernen. So Machen, wir mal ein
paar Beispiele , Das Ist, das einen regulären Ausdruck für die Menge aller Wörter bei " Null " eins, so dass der
das vorletzte zeichnen. Null ist, naja, da dürfen erstmal beliebig viele Null und Einsen kommen also Null vereinigt eins
in klammern Stern Beliebig viele Null und Einsen, dann muss eine Null kommen und danach darf nur noch genau ein Zeichen
kommen, aber mich interessiert mich, welches Null Vereinigt eins in klammer Das ist relativ einfach noch alle Zeichen
kennen, die die Teilzeichenfolge eins " Null " enthalten. Naja, ist ganz einfach Null vereinigt eins stern Dann, die
eins null nullvereinigt Einstern sehr intuitiv zu bauen und das ist wohl auch der Grund, warum man solche Ausdrücke sehr
gerne , In, Skriptsprachen verwendet Oder Jetzt Jetzt ein Bisschen schwieriger enthält nicht eins,
Null, überlegen wir mal, und da behaupte ich, dass es gerade Null Stern Isstern, die eine Richtung ist natürlich klar,
Nullstern Einstern kann die eins Null nicht enthalten kann es sein, dass es irgendein Wort gibt, das die Eins Null nicht
enthält und nicht von dieser Form ist , , Das, Kann, Nicht. Sein dann nehmen wir mal an, das Ganze fängt mit
einer eins an, ist es entweder so, das ist zu Ende, dann ist es gut, dass es Null eins Stern , Oder, es
Kommt, Es, kommt noch was danach, dann dürfen das aber nur Einsen sein, dann ist auch okay, dann ist es eins Stern, ja
Also sobald, irgendwo eine Null kommt und ich meine Eins hatte, habe ich auch die Eins Null irgendwo als
Teilzeichenkette Das heißt, ich weiß schon mal, dass das eins Stern und danach kommt nichts mehr, das ist richtig,
sobald ich eine Eins hatte, darf keine Null mehr kommen, es dürfen nur noch Einsen kommen, das wird hier durchaus
gedrückt , Und, Vorher dürfen aber beliebig vielen Null kommen also das jetzt formal zu beweisen, muss man ja eine
Folie voll schreiben in der Fall unterscheiden ja, aber das ist jetzt schon mal nicht intuitiv, da muss man irgendwie
nachdenken , , , Ach, Während, Dieses, Enthält, eins Null Eins, das ist wieder Simpel, das ist genau wie
hier nur dass da statt Eins Null Einzel Eins Steht Jetzt Enthält nicht eins Null Eins, da muss ich sagen, ich habe
eben fünf Minuten darüber nachgedacht konnte nicht so genau erklären, warum dieser hässliche Ausdruck das jetzt tut,
könnte man sicherlich direkt beweisen. Der Trick ist aber , Es, Gibt. Ein allgemeines Theorem das das sagt wir sind
abgeschlossen. Unter Komplementbildung nehme ich an und das Der Beweis dafür Ist konstruktiv das heißt, da sagt
ihnen Nein, dann nehmen Sie irgendwie den Regulären ausdruck für Enthält eins Null eins , Und Dann, gibt er
ihnen einen Algorithmus an wie sie den so umbauen Dass es, dann enthält nicht eins und eins ist aber der wird
dadurch größer und hässlicher, ja, das zeigt, dass reguläre Ausdrücke, wie wir sie bisher haben, nicht alles abdecken,
was man gern bei Pattern Matching haben will, aber andererseits könnten sie dann auch eine Skriptsprache bauen, die
diesen Notoperator dann auch noch hat, und dann bauen Sie das halt ein ne , Oder, Hier wäre jetzt mal was
anwendungsnäheres In Programmiersprachen benutzt Man diese regulären Sprachen nicht für die ganze Sprache dafür
ist das nicht mächtig genug Aber Um, einzel symbole Zu definieren zum Beispiel zu sagen, was ist eine ganze Zahl,
was ist eine Fließkommazahl und die habe ich das jetzt mal für eine ganze Zahl angegeben, die kann ein Vorzeichen
enthalten, muss aber nicht also nix oder plus oder eins, und dann kommt eine Ziffer, die sollte aber nicht null sein,
zumindest ist das im Deutschen, so dass man eigentlich keine führenden Nullen schreibt, und ich glaube, in C ist das so
eine führende Null bedeutet, das ist eine Oktoberzahl oder sowas, da muss man also auch aufpassen Also Die, null
darf Nicht, am Anfang stehen und dann dürfen beliebig viele Ziffern kommen, aber die Null darf natürlich am Anfang
stehen, wenn sie alleine steht, ja, in dieser Spezifikation ist zum Beispiel plus Null oder Minus Null auch nicht
erlaubt, da werden einige Programmiersprachen das erlauben , Aber, Das, Ist sicherlich eine sinnvolle
Definition dessen, was man als Zeichenkette, die eine ganze Zahl beschreibt im Dezimalsystem ansehen könnte Fragen dazu
bett so , Und, Jetzt was habe, ich davon jetzt habe ich plötzlich einen neuen Formalismus zur Beschreibung Formaler
sprachen Was Hat das mit typ drei Sprachen zu tun und die Antwort ist alles , Da, , und Der, Beweis wird
zurückgreifen auf diesen Kreis, den wir bereits geschlossen haben zwischen , Deterministischen, Ländlichen
automaten Chance Gibt zu drei Und Nicht deterministischen ähnlichen Automaten, Wir werden. Nämlich zeigen
dass man deterministische endliche Automaten leicht in reguläre Ausdrücke übersetzen kann und andererseits reguläre
Ausdrücke " leicht , Nicht Deterministischer ", endlich automaten, übersetzen kann, und damit ist das hier alles
das gleiche grafentheoretisch ist das hier ein stark zusammenhängender Graf? ne, wenn ich jetzt zum Beispiel eine Tomsky
Typ drei Grammatik habe und daraus einen regulären Ausdruck machen will Müsste ich hergehen Den erstmal in
nicht deterministischen endlichen Automaten umwandeln, den wir ja Potenzmengenkonstruktionen in einen deterministischen
Umwandeln und dann Kann Ich daraus einen regulären Ausdruck ableiten ja, aber wie gesagt, die beiden roten Pfeile
müssen wir jetzt noch zeigen, fangen wir da mal mit an Einen, regulären ausdruck in Einen nichtdeterministischen
endlichen Automaten übersetzen die Idee ist eigentlich ganz einfach, wir bauen einen Automaten aus Teilausdrücken, also
ich baue also, ich mache so eine Art Rekursive Konstruktion, man nennt das auch strukturelle Induktion. Wir bauen für
Teilausdrücke, Automaten und Stöpsel diese Automaten so zusammen, dass die Wörter, die der komplexere Ausdruck
definiert, alt akzeptiert werden, ja, Basisfälle kennen wir bereits , Wesentlichen, Hatte, ich, die Bilder gemalt
und dann daraus Beispiele für Nicht-Deterministischer endlich, automaten Gemacht für die letzte Vorlesung Basisfälle wir
brauchen einen endlichen Automaten für die leere Menge , Das, War, das ding es ist kein Endzustand und alles geht
in s über für das leere Wort, Es Ist, ein endzustand aber jeder Übergang für den Fehlerzustand Den
buchstaben a Naja Mit a gehe ich in den Endzustand über, aber alles andere geht in den Fehlerzustand, und wir
hatten hier diese Abkürzung dafür, wo der Fehlerzustand jetzt implizit war , Tragen Dazu also basisfall ist
ziemlich Simpel Und jetzt muss ich halt die einzelnen Operatoren, , Abklappern, Und schauen wie wie ich da
die Passenden automaten Baue Also Machen wir mal die Vereinigungsmenge , Wir, Machen, Das also
Vereinigungsmenge von L Eins und l zwei, wir bauen jetzt für L? eins und l? zwei , Nichtdeterministische,
Ähnliche, Automaten a eins und a zwei , Del Eins beziehungsweise l zwei akzeptieren Ja Es ich Sorge
dafür dass die Zustandsmengen hier Disjunkt sind also, ich verwende unterschiedliche Namen für die Zustände, sonst
kriege ich ein Problem, und jetzt ist es ziemlich einfach den Und, Neun automaten zu Bauen Ich, Führe einen
neuen Staatszustand s ein weitere Zustände sind die Vereinigungsmenge Der Zustandsmengen von A eins und A zwei
Also Grafisch, sieht Man, das hier neuer Zustand, denn die alten Automaten, die haben natürlich ihre eigenen
Startzustände, und ich habe hier die grünen Pfeile gestrichelt, weil im neuen Automaten sind die eben keine
Startzustände mehr, sondern der neue Zustand S ja am Genau und jetzt, das Wichtigste ist natürlich die Übergangsfunktion
Delta zu spezifizieren und ist aber hier sehr einfach Die Bewegt, sich ja weitgehend auf Disjunkt Zustandsmengen,
das heisst Delta verhält sich wie Delta Eins für Zustände in Q Eins und wie Delta zwei für Studenten in q zwei, da ich
muss ja nur noch überlegen, was passiert mit dem Startzustand und die Idee ist, dass dieser Staatszustand, der muss
sozusagen auf zwei Hochzeiten tanzen, der muss Das Verhalten sowohl Von dem ersten als auch von dem zweiten
Staatszustand simulieren, und das kann ich aber relativ leicht erreichen zu einem nichtdeterministischen, endlichen
Automaten Indem ich, einfach sage Delta S Komma a ist die Vereinigungsmenge Von delta S Eins Komma A und
Delta ist zwei Komma, wobei ja jetzt ein beliebiger Buchstabe in Sigma ist ja So und jetzt muss ich noch was über
die Terminalzustände Sagen Im allgemeinen ist das einfach f eins vereinigt f zwei also, die Endzustände der beiden
Automaten werden Übernommen, was das Ganze eigentlich bedeutet, hier ist Ich Gebe, jetzt ein Wort eine in diesen
nichtdeterministischen Automaten und im Endeffekt, der simuliert beide Automaten Parallel zueinander, das geht bei einem
nichtdeterministischen, ganz zwanglos , Und wenn, er dann in einem davon im im Endzustand ist, kann man dieses Wort
akzeptieren , Und, Entsprechend ist meine Endzustandsmenge einfach die vereinigung Dieser beiden mengen Es
gibt jetzt nur noch den Spezialfall wenn Der, anfangszustand einer der beiden Teilautomaten selber ein Endzustand
ist, dann muss auch der neue Endzustand, ein Endzustand, der neue Staatszustand muss dann auch ein Endzustand sein
Fragen dazu , , , Also, Das, Ist, jetzt schon halbwegs intuitiv Aber natürlich, muss man das auch
beweisen, ähm, und eben das auch in zwei Schritten. Wieviel Übung habt ihr, soll ich den Beweis noch machen oder mache
ich damit nächstes Mal weiter , Gut, Dann mache, ich den Beweis noch, ähm genau, also das geht in zwei Schritten.
Wir zeigen erstmal, dass , Elf, Von, a teilmenge von elf von eins vereinigt elf, Und, Zwei, ist Das
Beweise ich indem ich, mir ein beliebiges wort w aus elf von a nehme Und Jetzt mache ich eine Fallunterscheidung
und tritt wieder eine Induktion, also fangen Mache Eine induktion über Die Länge von W Wenn Weh das leere
Wort ist Dann Folgt Dass Essen Endzustand Sein Muss und nach Definition davon, wann darf der neue
Zustand Essen Endzustand sein, kann das nur der Fall sein, wenn entweder s eins oder s zwei Endzustände Waren
Reichen sie, das entweder also einer von beiden natürlich, beide darf auch sein. Das bedeutet aber, dass das leere Wort
in L? eins, oder l? zwei auch drin sein muss und folglich ist es in der Vereinigungsmenge Ja so und jetzt schritt wenn w
die Form hat ein Buchstabe und dann irgendwas x, ähm, dann heißt das ja, es gibt einen Pfad In Unserem
nichtdeterministischen endlichen Automaten in dem großen Der bei, s anfängt erster Buchstabe ist A geht in
irgendeinen Zustand Q, dann wird das wort x eingegeben und dann landet ja in einem Zustand F, der einen In Der
endzustandsmenge sein Muss , Und, Jetzt mache ich eine Fallunterscheidung Dieser Erste zustand Q In Dem
ich Lande könnte in q eins oder Q zwei landen, da das alles völlig symmetrisch ist, gucke ich mir nur den Fall Ku eins
sind , Großko, Eins An dann heißt das ja, dass es einen Pfad genau. Also, wenn der erste Zustand q eins in Großku
Eins ist, heisst das Ich Habe. Einen übergang gemacht in die Also Dieser fahrt springt Sozusagen in die
Zustandsmenge von Dem Ersten, teilautomaten und Delta ist ja so gebaut, dass, wenn ich einmal in dem ersten
Automaten drin bin, bleibe ich da auch, das heißt, dieser Fahrt muss sich komplett in dem ersten Automaten bewegen, also
in Q eins bewegen in Großko Eins am Und, Naja, da, f, ein Endzustand ist und ich in Q eins mich bewege, muss das
einen Zustand aus groß f? eins sein, also ein Endzustand von , Dem, Automaten, a Eins ah das bedeutet aber, dass a
x in Airlines Sein Muss weil, ich habe ja hier praktisch das gleiche Es Gibt, ja einen Passenden s
Eins Nach q eins weil, so habe ich die Übergänge von Von S definiert das heißt, es gibt dann einen Pfad von S.
Eins , , Durch, Den, Ersten automaten zu einem Endzustand von dem Ersten automaten Folge Ist Das
Ganze in f eins und damit auch in der Vereinigungsmenge Genau und der fall Erster Zustand ist in in der in groß Q zwei
ist Analog zu andere Richtung.
Nein, , Entschuldigung, Genau, Oh jetzt. Habe, ich in was? okay, jetzt weisst Dass L, a Teilmenge von L eins
vereinigt l zwei ist und mit welchen habe ich gerade gemacht? ich bin jetzt verfehlt.
Welche habe ich eben gemacht? ich bin jetzt durcheinander , Entschuldigung, Ich, Bin ein bisschen durcheinander,
ich mache das nächstes Mal nochmal, okay, dann machen wir jetzt die Übung, ja, ich brauche aber hier okay, , Dann
Machen, wir jetzt mit der Übung weiter Erstmal Noch ein ganz kurz ein paar organisatorische Sachen, vielleicht
gerade noch drei Minuten, Dableiben, , Das, Tutorium nummer Neun da Gabs Eine raumkollision beziehungsweise
Wir haben den falschen Raum aufgeschrieben Dass Es, im raum Minus Hundertzwanzig nicht in Minus Hundertsieben,
also Das Tutorium von Alexander Noe ist Minus Hundertzwanzig Gut , Ja, Wir bitten darum dass die
Übungsblätter Nur handschriftlich abgegeben werden also, keine irgendwie Techlösungen oder so, andererseits mit
Automaten macht es Eh keinen Spaß sie am Computer zu machen Ja , für die Die es verpasst haben, es gibt
keinen Übungsschein, sondern ein Klausur Bonus, aber die Übung ist Klausur relevant.
Also es lohnt sich vielleicht durchaus zuzuhören und Wir haben. Heute morgen schon Übungsblätter Ohne eine
tutoriumsnummer Aus dem Briefkasten gezogen. Also bitte daran denken immer oben rechts groß, die Tutoriumsnummer darauf
zu haben, sonst kann es sein, dass mir die Blätter Nicht zuordnen kann oder irgendwann keine Lust mehr haben in der
Liste nachzuschauen, wer jetzt in welchem Tutorium ist und die Platte dann korrigiert werden okay, , Dann, Fangen,
wir mal an mit , Vollständiger, Induktion, Damit, Haben, wir ja Davon haben wir ja schon einige
Aufgaben in der Vorlesung in der letzten Übungen auf dem Blatt und im Tutorium gemacht Was Gibt es denn so an
Dingen, über die man überhaupt induzieren kann, weil da hatten mehr verschiedene Varianten , Das, Erste war die
wortlänge Herr Oma über die Die Buchstaben Des Final Abgeleiteten Worts induziert und damit, was zeigt
Dann Hatten, wir induktionen über die Anzahl der Ableitungsschritte gesehen, das war Zum Beispiel mit Der
mit der Tabelle und das Wo, wo man dann Eine , allgemeinere induktionsvoraussetzungen hatte und dann mit der
Tabelle gezeigt hat, welche Regel angewendet, auf welche Form Von, Möglichem wort Wiederum, Maß für Eine
Form von Möglichem Wort ergibt und dass das dann alles wieder in der Sprache aus Der induktionsvoraussetzung war
und Die Davon, die keine nicht Terminale mehr Enthielten Das war, dann genau die Sprache, da gibt es auch die
Varianten, ob man jetzt , Über, Einzelne schritte oder Die Gesamtzahl der Ableitungsschritte, die Induktion führt
Das Ist, mal so mal so praktischer und dann Hatten Wir noch die Induktion Über Endliche Teilfolgen
einer totalen Ordnung, da waren zwei Beispiele in der Vorlesung.
Das erste war die Induktion über die Lexikographische reihenfolge Und das zweite war gerade vor zehn Minuten, aber
, Die, Sind, eher seltener Es Gibt, auch noch ein paar Techniken, die man da verwenden kann, die das Ganze
vielleicht etwas einfacher machen Manchmal Ist, es einfacher den ersten Ableitungsschritt zu betrachten, manchmal
ist einfacher, den letzten zu betrachten Es Kann auch hilfreich sein den , Induktionsanfang Größer Zu machen
also das für n gleich Null und n gleich eins zu zeigen beispielsweise, denn dann kann man Induktions in der
Induktionsvoraussetzungen auf zwei Schritte zurückgreifen , Das Ist, auch manchmal hilfreich oder Wie Vorhin
schon ein angesprochen Eine stärkere induktionsvoraussetzung zu machen damit man dann in der Tabelle alle
möglichen Ableitungen durchgehen kann und zeigen, dass alles in der Sprache bleibt , Oder, Manchmal gibt es auch
den Fall, wo man Worte aufspalten muss in zwei Teilworte, die beide Kürzer sind, , Und, Dann mit der
Induktionsvoraussetzung Sagen kann dass das Kombinierte Wort in der Sprache ist, aber dafür muss man dann in
der Induktionsvoraussetzung meistens voraussetzen, dass es für alle Werte kleiner als n Bild, Was Man, zeigen wird
okay, jetzt Übergebe Ich ja also , Fangen Wir mal an mit , Ein Bisschen wiederholung zur Champagner
Hierarchie Es Gibt ja jetzt ein paar Grammatiken gleich und Die Frage ist In welcher Klasse die sind also
die Grammatiken, so wie sie da Hingeschrieben sind, Möglicherweise Kann es auch sein dass man die Sprachen auch in
einer anderen Klasse ausdrücken Kann aber es gilt darum, in welcher Klasse die Sprachen so sind wie Sie da, die
die Grammatiken so Sind wie sie so da stehen Machen Wir vielleicht am besten über Handzeichen, , Wer,
Ist, der meinung dass das eine Chomsky drei Grammatik ist, findet jemand kontextfrei, kontextsensitiv , Und, Typ
null also , Die Grammatik ist Kontext sensitiv also typ eins, denn es werden hier Nicht, Terminale, und
Terminale gemischt abgeleitet während Für Eine kontextfreie grammatik also Typ, zwei , Dürfte, hier nur ein
einziges nicht terminal stehen und natürlich für alle, die ihre Arme oben behalten, haben Sie es auch Tomsky Null, ja
natürlich durchaus richtig, immer noch natürlich Mag Jemand raten was für, eine Sprache, die erkennt, genau das
ist eine einfachere Form von der Grammatik, die wir in der Vorlesung hatten, die auch Ndr. Auch n. Co reinerkennen
Die zweite grammatik Hat Also Es ist wieder die gleichen Variablen und das gleiche Alphabet, aber andere
Produktionsregeln.
Wer ist der Meinung, dass die Chomsky drei ist , Kontextfrei, Aber, nicht, chomsky drei okay, noch was Höheres, wer
bietet mehr?
ja, also die ist Typ, Drei, Ja, dann, das sind hier alles Ableitungen der Form, ein Terminal auf n , Ein
Nicht, terminal auf ein Terminal und ein nicht terminal oder nur auf ein Terminal, die Ableitung Erst nach epsilon
ist Hier natürlich zugelassen Und Die erkennt ja die Sprache der Wörter in den nach jedem A ein B kommt also auf
jedes Arm muss immer ein B folgen.
Die dritte Grammatik sieht so aus, es gibt die Ableitung vom Staatssymbol auf B und das Staatssymbol Klein a Grosa
Kleinartstartssymbol Ist Sie regulär äh Nein, , Ist, Sie kontextfrei viele ist, die Kontext sensitiv, aber
nicht kontextfrei, okay? ja, aber das stimmt auch, das setzt die fehlende Typ zwei Grammatik Freiwillige Zur
Sprache die Die, erkennt also das sind Worte Mit gerader anzahl as denn hier also in der ersten Regel in der
Ableitung von s werden immer gerade Anzahl as erzeugt oder Bs, und die zweite Regel erzeugt nur Bs, das heißt es, da
können beliebige irgendwo Bs landen, aber die Anzahl as ist immer gerade Gut, Okay, , ich, Nehmt es mit
Gut Eine Anmerkung noch Zur letzten Aufgabe ist mir aufgefallen Also Wann, immer ein Wort in der sprach In
Also wann, immer eine Grammatik in einer Tomski hierarchieklasse Liegt liegt, sie auch in allen anderen da drunter.
Es kann allerdings sein, dass sie nicht in dieser Form dadrunter liegt. Also, wir erlauben ja zum Beispiel bei Jobsky
drei Grammatiken immer wieder die Ableitung auf Epsilon, dass das Wort Kürzer wird.
Es liegt unter anderem nicht in Jomski eins garantiert nicht und in Tomsky zwei, normalerweise auch nach vielen
Definitionen nicht Das man, kann das immer in Natomski eins, oder Johnski zwei Grammatik noch ausdrücken, aber es
muss nicht direkt drin liegen, genau , Jetzt, Kümmern, wir uns nochmal ein bisschen um Zomsky, zwei Grammatiken,
, Ja, Und, zwar, um Ableitungsbäume die waren in der Vorlesung nur relativ kurz dran, und vor allem hat man nicht
gesehen, wie einer Schritt für Schritt aufgebaut wird, deswegen wollte ich das einfach nochmal machen, wir haben eine
ganz einfache Grammatik, die wir sonst auch im Mastronomski zwei Grammatik kennen, die ah hoch n b hochend Grammatik in
Ihrer wahrscheinlich auch wirklich einfachsten Form, genau, wir haben also hier einmal die kürzeste Ableitung, die es da
drin gibt, wenn ich jetzt noch einen zwischenschritt Einbau, dann sieht der Ableitungsbaum so aus und so weiter,
beliebig viele a hoch nw Als Besonderheit in Meiner Notation ist vielleicht so, dass ich die Terminalsymbole alle
auf eine Ebene schreib, aber ansonsten ist es genau gleich wie in der Vorlesung sollte im Endeffekt genau gleichlaufen
, Warum, Ich, das nochmal mache es auch, weil das euch bei vielen Induktionen helfen kann, und zwar ist es hier
jetzt einfach so, dass man Wenn man, mehr schritte macht Kann Man einfach sich das vorstellen in dem
Baum, als würde man diesen Baum in anderen Baum reinhängen. Also, wenn ich jetzt einfach nur , Also, Wenn, ich die
erste Ableitung neu mache, begrüße ich den Baum nur nach oben, und man kann es auch so machen, dass wenn man in dem Baum
noch irgendwo nicht terminal hat, kann man da auch andere Wörter dranhängen, die aus diesem nicht terminal erzeugt
werden. Also diese Bäume sind häufig gut dazu da, sich bei einer Induktion vorzustellen, was mit dem Wort irgendwie
passiert Genau Ansonsten habe ich noch ein weiteres Beispiel Und zwar, handelt es sich hierbei um den
Ableitungsbaum, Der, In, der Vorlesung gemacht wurde er ist ein bisschen größer, und er besteht aus , Aus, Einem
rechenausdruck im Endeffekt Genau Und ich wollte ihn einfach mal schrittweise aufbauen, einfach damit man sieht,
genau wie wie eine Ableitung mit einem Ableitungsbaum, , Zusammenhängt, Genau, Als ersten schritt leiten wir
ab e zu e plus t, das plus ist schon Ist So ein terminalsymbol das heißt, wir schreiben das unten hin hier unten
sammelt sich praktisch das Wort an das wir erzeugen wollen, und auf beiden Seiten haben wir eben noch weiter nicht
Terminale, genau dann wird es Eh zu einem Tee abgeleitet, und das kann man Wiederum, Ableiten zu einer
Multiplikation das hier unten Ist Ein multiplikationspunkt Vielleicht Nicht ganz glücklich gewählt unter
dieser Linie genau, und so kann man das einfach immer weiter machen, ähm, genau hier, dieses dieses F es wird später
abgeleitet zu einem Terminalsymbol, weil ich mir nicht die ganze Weil ich, mir nicht die ganze Folie mit
Terminalableitung vollstopfen wollte, ähm Gibts am Ende einen schritt, wo alle Apps die Terminal sind, , Zu, Ihrem
terminal symbol Abgeleitet werden, aber ansonsten gehen wir immer von Machen Wir, eine linksableitung also wir
betrachten immer das Linkeste, nicht Terminal, das überhaupt noch abgeleitet werden soll, hier machen wir jetzt eine
Klammerung, um hier was Neues auszudrücken , Man, Sieht, das ganze ist Rechts von der Multiplikation. Deswegen
müssen wir Klammern, wenn wir jetzt hier in der Klammer, wie wir das tun wollen, ein Plus haben , Die Grammatik,
war So erzeugt die habe ich jetzt hier nicht nochmal aufgeschrieben, aber die Grammatik war so erzeugt, dass man aus E
und t nicht direkt nicht Nicht Direktterminale ableiten konnte deswegen gibt es ja jetzt ein paar
Zwischenschritte, die eigentlich relativ uninteressant sind. Hier geht es auch noch den einen großen
Zwischenschritt Mit der rechten Seite wollten wir eigentlich gar nicht so viel machen.
Und jetzt kommt einmal der Ableitungsschritt, der die ganzen Terminale einfügt, so , So Wird, der ableitungsbaum zu
der Ableitung, die auch schon in der Vorlesung gegeben war aufgebaut, also wenn ihr da einfach nochmal irgendwann
drüberschauen wollt, dieser ganze Ableitungsweg war auch auf den Vorlesungsfolien dort waren dann diese Fünf
terminalen ableitungen halt Irgendwie Drüber verteilt, aber ich denke, hier sieht man nochmal ganz gut, wie diese
Ableitung aufgebaut wird, gut, dann jetzt Auch Wieder, was das in der Vorlesung nur ganz kurz gemacht wurde, dass
ich ein, dass wir einfach einmal praktisch irgendwo Als Beispiel haben Wollten Und zwar, das war das
Wortproblem über Tomsky eins Grammatiken in der Vorlesung wurde gesagt, das Wortproblem über tomsky eins Grammatiken
Lässt Sich einigermaßen sinnvoll lösen und der Algorithmus war aber war aber nur sehr formell beschrieben und es
gab kein gutes Beispiel dazu. Deswegen wollte ich das jetzt einfach mal machen, weil in der Vorlesung dazu keine Zeit
ist normalerweise also die Vorlesung ist einfach voll mit Stoff, , Wir, Müssen, wir einigermaßen zügig durchmachen
und die Beispiele werden dann häufig auf die Übung verlagert werden.
Genau also, wir fangen hier auch an , Hm, Das, Ist, jetzt eine Joinski eins Grammatik, wir betrachten Wir
Fangen, beim startsymbol an und die Frage ist eigentlich, ob das Wort Aet Abbac in der Sprache drin liegt, ähm, wenn man
sich die, äh, Ableitung mal anschaut, es kann abgeleitet werden zu te oder zu Epsilon, diese Konstruktion müssen wir
immer machen, wenn Epsilon in der Sprache drin ist , T, Kann wiederum abgeleitet werden zu t zu A, B, C, A oder C,
das heißt aus einem aus einem Tee kann man sagen werden immer Wörter, die mehr as und c, also so die mindestens so viele
as und Cs enthalten, wie sie Bs enthalten, ähm, dieses hier ist eine abgekürzte Schreibweise für ganz viele Ableitungen,
nämlich für alle der Form, die zwei Nichtterminale vertauschen Das Heißt, die verändern nichts an den , An,
Den mengen und Diese hier verändern auch , Also, Das, sind dann nur noch unsere Terminalableitung Das Heißt,
diese sprache beschreibt so ungefähr alle Wörter, die mindestens so viele as und Cs enthalten, wie sie Base enthalten,
von denen aber ungefähr alle, weil, ob , Weil wir, dürfen die ziemlich beliebig vertauschen Wir Suchen jetzt
also nach dem Wort abc und um es ein Bißchen einfacher zu machen, sagen wir, wir suchen nach dem Wort des Also
nach, dem wort groß A b Ac weil es im Endeffekt daselbe Ist Und, Für, Johnski eins Grammatiken ist das Schöne,
dass wir einfach ausprobieren können, und zwar wir können so ausprobieren wie dessen Computer auch tun würde. Wir
versuchen immer, eine von den obersten Ableitung zu machen, also die Ableitungen werden praktisch Priorisiert von oben
nach unten, und wir versuchen immer, eine zu machen, die erste Ableitung wäre, es geht über auf Epsilon, wir sehen, hier
kann nichts mehr abgeleitet werden, das heißt, es ist eine sackgasse Das, brauchen wir uns nicht mehr weiter anschauen,
das heißt wir gehen zurück zu dem S und schauen, was können wir als nächstes machen? die nächste Ableitung ist in der
Reihenfolge. Ja, es geht über auf T.
Die Erste ableitung von T aus ist Tee zu verdoppeln, machen wir einfach mal die nächste Ableitung, die wir hier
drauf machen können ist wieder Tee zu verdoppeln, wir machen das, und zwar genau, bis wir vier Elemente haben, weil das
Schöne an Jonomski eins Grammatiken ist, dass das Wort niemals Kürzer werden kann, das heißt, sobald wir hier versuchen,
das Fünfte t Abzuleiten Wissen wir das keine das, kann nur eine sackgasse Sein wir, kommen niemals wieder zurück auf
vier Buchstaben, das heißt das hier funktioniert nicht, und das ist der eine große Unterschied, den Jomsky eins
Grammatiken im Vergleich zu Jomsky Null Grammatiken haben dieser Abbruch hier bei Einerjonowski, nur Grammatik müsste
ich jetzt hingehen beliebig weit nach unten gehen, weil die könnten alle noch zur Epsilon abgeleitet werden, und dann
komme ich bei einem unendlich großen Suchraum raus, und das funktioniert nicht mehr. Das Schöne ist einfach nur, dass
hier bei James g eins Grammatiken der Suchraum beschränkt wird, und zwar weil ich hier sagen kann, ich gehe nicht genau,
deshalb habe ich auch in jeder In Jeder iterationsstufe genau Vier Kästchen Hingeschrieben weil, sobald, wir diese
vier Kästchen an nicht terminalen, irgendwann sprengen , Kann es nicht mehr kann nicht mehr zum Gesuchten Wort
führen, okay? also hier geht es nicht mehr weiter mehr Test zu machen, das heißt wir versuchen was anderes, das einzige
andere, was wir hier noch machen können, ist Einzelne, Tests zu zu As oder Cs ableiten weil wir können
auch kein Abc mehr erzeugen, weil das würde ja wiederum auch wieder alles sprengen, wenn wir hier anfangen, dann gehen
wir hier in Subgraph rein der, im endeffekt Alle worte aus acc und ts enthält die vier Buchstaben genau haben. Wir
wissen aber das Wort, das wir suchen ist, da garantiert nicht drin, was ein Algorithmus tun würde es genau diesen
kompletten Suchraum ausfüllen und austesten sehen, dass da nichts bei rumkommt und dann hier zurück. Backtrain Ist im
endeffekt Einfach eine Tiefensuche auf einem Graph die hier in Die Hier, in der Sackgasse Läuft in eine sehr große
Sackgasse Das, hat irgendwie ein paar hundert , Paar, hundert wörter sind Hier drin und ein Haufen , Einen,
Haufen, verbindung Zwischen Den Wörtern, weil hier sind ja auch die ganzen , Tauschachen, Drin, Und alles mögliche
ähm, aber hier ist eine Sackgasse Im endeffekt Wird gebacktrack Zu diesem zustand zurück dort passiert genau dasselbe,
um ehrlich zu sein, hier Kommen Wir, auch in Kommen Wir auch in Subgraf rein der ist auch noch mit diesem
unteren hier verbunden, wir suchen das Ganze ab, sagen hier ist nichts Backtrain wieder hier raus jetzt sind wir im
interessanten Fall, und zwar wir haben jetzt schon versucht, mehrere Tests daraus abzuleiten Deswegen, der nächste
schritt wäre in der Priorisierung wir haben gesagt, wir gehen von oben nach unten durch die Regeln durch, wäre dieses
hier die nächste Regel, also versuchen wir auf dem ersten Tee, diese Regel anzuwenden, wenn wir dabei nicht zu einem
ziel Führen würden würden, wir es auf den Versuchen auf dem zweiten Tee anzuwenden und so weiter, aber wir haben hier
schon Glück, das ist schon mal auf dem richtigen Weg, wenn man sich das Wort anschaut, wir kommen dem Ziel Näher die,
nächste regel Wäre er hat das t verdoppeln, das funktioniert nicht bis t zu dem Abc weiterleiten, das funktioniert
wieder nicht, da werden wir wieder zu groß, jetzt sind wir richtig, wir wollen das t als nächstes zu dem A ableiten,
einfach weil es von der Priorisierung her das nächste ist genau hier kommen jetzt irgendwie unglaublich viele
Vertauschungen, die Ausprobiert werden aber, dass hier nichts anderes mehr zum Ableiten gibt, außer diese Vertauschungen
beziehungsweise dann, wenn wir alle Vertauschungen Ausprobiert haben, würde der Algorithmus darauf kommen. Ja, dann
müssen wir bei jeder Vertauschung jetzt mal noch die Terminaldinger machen Irgendwann Irgendwann kommen wir zu
diesem Wort und Bisher Zeigt uns dann dieses Wort wir sehen also der Algorithmus funktioniert, man muss einfach
nur diese , Ableitung, Priorisieren, Und, an der ersten Stelle, die wir noch nicht so abgeleitet haben,
weitermachen , Wir, Sehen, aber auch wir hatten hier sogar so ein bisschen Glück, dass wir hier dann relativ zügig
zu Hier In diesen ersten Weg abgestiegen sind.
Dieser Algorithmus hat im Allgemeinen eine ziemlich lange Laufzeit Also exponentiell, in der Wortgröße auf jeden
Fall mal , Genau, Aber, ich, wollte einfach mal, dass es dazu ein Beispiel gab, dass man eben sieht, wie dieser
Suchraum abgearbeitet wird, Weil Später, in dem theoretischen Teil, was dann auch um Thüringmaschinen und alles
geht, dann soll die Konstruktion auf jeden Fall helfen mal gesehen zu haben gut Gut da machen Wir weiter mit
einer Potenzmengenkonstruktion, , Das, Will, auch öfter kommen er ist auch auf dem zweiten Übungsblatt, das wir
gestern Hochgeladen haben, zwei oder drei, wieviel haben wir darauf gemacht, wie viele Potenzen werden Konstruktionen
auf dem Blatt, ja, aber im Studium kommen da auch noch mehr, also , Wollte Ich einfach mal eine durchrechnen
Um Das nochmal zu zeigen also das ist unser nichtdeterministischer Automat, der eine total unsinnige Sprache erkennt
Hat Vier zustände im Haufen übergänge ein Haufen Mehrfach belegte, übergänge Zustand S eins her kann mit einem b
sowohl in s eins bleiben als auch nach als Null oder s drei gehen zum Beispiel S Null kann Mit sowohl mit a und
also auch mit b nach s eins oder nach s drei gehen , , Also, Wollen, Wir, einfach mal diese diese Tabelle
durchrechnen?
ich habe ja rechts nochmal den Automaten hingemacht und wir fangen beim Startzustand an, also hier links in der Tabelle
ist immer eine Zustandsmenge der aktiven Zustände am Anfang ist natürlich nur der einzige Startzustand aktiv, deswegen
ist es die Menge, die nur s Null enthält und , Mir, Schauen, wir mal an Wo Man, mit einem a jetzt überall
hinkommt, und das sind die Zustände S. Eins und es drei und mit einem B ist das gleiche, jetzt haben wir hier auf der
rechten Seite in der Tabelle eine neue Zustandsmenge S Eins drei. Deswegen betrachten wir die jetzt als nächstes und
schauen, wenn man in dem Zustand erst einzelner Ist drei ist und ein a liest, wo man dann so überall hinkommen kann,
sonst gibt es hier keine Übergänge und von s drei jetzt Auch noch erst zwei sonst gibt es wieder keine Übergänge,
also geht es mit dem A hier nun nach S zwei und mit dem B Geht Es überall hin fast man kann in das eins bleiben,
in nach s? drei gehen oder nach s? Null gehen und das drei gibt es keine Übergänge mit einem B, also braucht man das
nicht weiter betrachten, also gibt es jetzt s? Null, das eins ist drei, das sind jetzt wieder zwei neue Zustände, immer
Betrachten Müssen fangen Wir Mal an mit s zwei, das vielleicht einfacher, da kommt man mit einem A wieder
nach s zwei und mit einem b zurück nach S. Null, das ist schön, einfach und in anderen Zustand, die wir neu betrachten
müssen, ist hier dieser S? Null S. Eins ist drei.
Hier können wir uns jetzt ganz viel Arbeit sparen, indem wir auf die oberen beiden Tabellenzeilen zurückgucken, da haben
wir das Ganze nämlich schon mal einmal für S. Null gemacht und einmal fürs Einzelnes drei Die Übergänge für S Null
ist eins ist drei ist Genau Die vereinigung der übergänge Von S Null und von S. Eins und das drei, damit können
wir diese Zeile ganz einfach ausfüllen haben wieder einen neuen Zustand, da kann man jetzt den gleichen Trick wieder
anwenden, indem man einfach nur diese zwei Zeilen betrachten und haben die Tabelle fertig?
ja, jetzt stellt sich noch die Frage, welche der Zustände in dem neuen Automaten akzeptierend sind, und es sind
natürlich genau alle, die die s zwei beinhalten, denn es zwei war vorher unser Endzustand, und er akzeptiert, der
Automat akzeptiert ja genau dann, wenn er in das zwei landen kann.
Also es sind Hier S zwei und s eins ist zwei s drei, die neuen Endzustände, wenn man das jetzt zeichnet, sieht der
Automat so aus, ja, ist vielleicht auch nicht so viel Hübscher als der nicht deterministische, die Sprache, die da
erkennt, ist auch ausgesprochen, hässlich, wir haben da mal einen regulären Ausdruck für gebaut, der war so lang
Ja, Aber, das, ist eben auch dann nochmal ein gutes Zeichen dafür, dass der Algorithmus euch hilft, auch wenn ihr den
Graf überhaupt nicht versteht. Also dieser erste Graf der Wir Hatten ja keine Ahnung was der für eine Sprache
erzeugt, und trotzdem liefert uns die Potenz neuen Konstruktionen immer einen Graf, ja, also immer ein Automat, der das
gut erkennt, der das Deterministisch erkennt, das kann man ganz stupide einmal durchkreuzen diese tabelle , Und
Es Auch in der Klausur dann Sehr Einfach damit Punkte zu Machen wenn wir sowas dran bringen? ja. Also
so eine Aufgabe kommt nicht nur garantiert auf mindestens einem Übungsblatt und in mindestens einem Tutorium dran, die
kommt auch zu.
Also ich habe lange Zeitklausuren zurückverfolgt. Es sind mindestens neunzig Prozent dass, so eine aufgabe Drankommt was
natürlich heisst, bei uns kommt es jetzt nicht dran, aber ist okay,