Guten Morgen, ich werde erst mal mit einer Wiederholung anfangen.
Am Montag haben wir sehr viel über organisatorische Sachen gesprochen.
Ich möchte nur kurz sagen, dass die Vorlesung bis Ende Dezember
montags und mittwochs stattfinden und ab Januar wird die Vorlesung nur
montags in der Regel stattfinden.
Und der Grund dafür ist, dass diese Vorlesung dreistündige Vorlesung
ist, aber wir vor Weihnachten vierstündige Vorlesungen haben und
danach, nach Weihnachten, haben wir zweistündige.
Gut, so, wir hatten organisatorische Sachen, aber dann haben wir auch
noch angefangen mit so Einführung, formelle Modelle der Informatik und
dann haben wir über Automaten und Sprachen gesprochen.
Diese Automaten, Sprachen, die werden uns beschäftigen bis ein paar
Vorlesungen und dann habe ich ein Video gezeigt, wie zum Beispiel ein
Automat aussehen kann für Ampelsteuerung.
Dann habe ich auch erzählt, dass es nicht nur Ampelsteuerung ist oder
es nicht nur für Programmiersprachen verwendet werden kann, sondern
kann auch für andere Diszipline sein und so weiter.
Und dann sind wir hier und wir wollen heute mit formalen Sprachen und
Grammatiken anfangen, aber vorher möchten wir kurz wichtige Begriffe
und Notationen noch hier besprechen.
So, wir haben Alphabeten und Sie können, vielleicht denken Sie, ich
weiß, was Alphabeten sind, aber das brauchen wir, um formale Sprachen
zu definieren, um Grammatiken und Regeln zu definieren.
Aus diesem Grund, wir beschreiben ein Alphabet formal und formal ist
es einfach eine ähnliche Menge oder ähnliche Folge von Zeichen.
Das ist ein Wort, sorry.
Das ist eine ähnliche, nicht leere Menge von Zeichen.
So, Sie können zum Beispiel A bis Z diese Buchstaben haben oder 0 bis
9 oder 0 und 1 oder, was ich auch als Beispiel geschrieben habe,
Alphabet A oben B oder Sie können zum Beispiel andere Art von
Alphabets haben, abhängig von Sprache, das Sie definieren wollen.
Zum Beispiel, Sie können schreiben M1 und M2 und Sie können dann Worte
aus diesem Alphabet und Buchstaben haben, zum Beispiel M1, M2, M2, M1.
Das wird ein Wort aus diesem Alphabet sein.
So, jetzt, ich habe über Worte gesprochen.
Ein Wort ist eine ähnliche Folge von Zeichen von A und wir schreiben
das normalerweise so B.
Wort B ist eine ähnliche Folge von Zeichen.
Zum Beispiel, wenn wir Alphabet A bis Z nehmen, da können wir
Informatik schreiben.
Das ist ein Wort aus dieser ähnlichen Menge, das wir definiert haben.
Oder ein Wort kann sein 1, 2, 3.
Das ist aus der Sprache, also aus Alphabeten 0 bis 9.
Oder eine binäre Kette, das ist auch ein Wort und die Alphabet, die
wir dort haben, diese 0 und 1.
Dann, für diese Worte können wir auch die Länge definieren.
Die Länge schreiben wir immer so.
So, Länge von Wort Informatik, es ist 10.
Warum?
Weil ich 10 Alphabet oder 10 Buchstaben hier habe und deswegen die
Länge ist 10.
Die Länge von Wort 1, 2, 3 ist 3, weil ich drei Buchstaben drin habe.
Oder Länge von Wort 0, 1, 0, 0, 1 und so weiter ist es 8, weil ich
einfach acht Buchstaben oder Alphabets drin habe.
Ich kann auch eine Sprache haben, die die Musiker sind.
Zum Beispiel, sie haben noch ihre eigenen Alphabets.
So A, B, C, D oder Do, Re, Mi, Fa und so weiter.
Das ist auch Menge, ähnliche Menge von Buchstaben.
Das ist dann ein Alphabet für bestimmte Sprache.
Und da kann man Worte draus machen und Länge von Worten kann man auch
berechnen.
Was wir auch noch haben und sie werden sehr häufig dann in dieser
Vorlesung verwenden, ist ein leeres Wort.
Das heißt, es ist nichts drin.
Es ist ein leeres Wort und da schreiben wir das mit Lambda.
Lambda hat auch Länge 0.
Das sollen Sie merken, wenn wir dann mit Grammatik anfangen, wir
sagen, wir haben ein Wort Länge 0, dann wäre dann ein leeres Wort.
Dann können wir mit dieser Alphabet, so mit A, können wir was anderes
machen.
Das können wir schreiben A hoch N und da gibt uns Menge der Worte der
Länge N.
Ja, so alle Worte aus einem Alphabet, die Länge N haben, die sind so
in dieser Menge geschrieben.
Zum Beispiel, wenn wir N gleich 3 haben und Alphabet 0 und 1, dann A
hoch 3, es ist dann die Menge aller Worte, die Länge 3 haben.
So, A hoch 2 wäre Menge von Worten, die alle Länge 2 haben.
Dann haben wir A-Stern und es ist auch noch mal was, so ein anderes
Begriff, dass sie auch noch mal sehr viel verwenden.
Es ist eine Menge aller Worte über A, die diese Union von allen
Worten, die Länge N haben, größer als 0.
Das heißt, so A 0 über ein gleiches Alphabet 0 und 1 wäre erstmal ein
leeres Wort.
Dann haben wir Worte mit Länge 1, dann Worte mit Länge 2, dann mit
Länge 3, mit Länge 4, 5, 6, bis was auch immer wir haben unendlich.
Alle Worte aus einer Sprache, alle Kombinationen aus einer Sprache.
Dann haben wir A-Plus.
Diese Plus und Stern, bitte beachten Sie.
Dann haben wir Plus und Plus ist es Menge aller nicht leere Worte über
A.
Das heißt, das Gleiche wie oben, nur Lambda gibt es nicht drin.
Ja und dann, wenn wir diese Worte und diese Definitionen haben, da
können wir eine Sprache definieren und Sprache ist L.
L ist für Language.
L über A, so wir müssen eine Sprache über bestimmte Alphabet
definieren und dann ist es L, es ist dann eine Sprache, die alle
Kombinationen von Alphabet A drin hat.
Das heißt, A-Stern, alle Wörter, die wir damit machen können.
Leeres Wort und so weiter.
Und dann können wir sagen, L heißt formale Sprache, falls L durch ein
ähnliches formales System vollständig beschreibbar ist.
Das heißt, wir haben hier auch jetzt irgendwie ein formales System
definiert.
Und wie ist das ein Beispiel?
So ein Wort von Alphabet 0 und 1 und Stern, das heißt alle
Kombinationen, diese Sprache ist alle Worte aus 0 und 1.
Das Anzahl der Einzelnen in W ist gerade.
Das heißt, ein Wort aus dieser Sprache kann nur so sein, 011 zum
Beispiel 0.
Die Anzahl von Einzelnen ist gerade.
Oder 0111 oder 11 oder Lambda.
Aber so ein Wort gehört dieser Sprache nicht.
Oder das ist nicht drin.
Oder das ist auch nicht drin.
Gut, die sind wichtige Begriffe.
Wir haben einmal jetzt definiert.
Und wenn wir sagen Stern oder Plus, Sie sollen dann wissen, was wir
damit meinen.
Ich sehe, hier gibt es eine Frage.
Okay, gibt es nichts.
Gut, dann machen wir weiter mit Klassifizierung formale Sprachen.
So, die formalen Sprachen können wir charakterisieren und
klassifizieren.
Und da haben wir drei Formen davon.
Und Sie werden alle diese drei Formen lernen.
Erstmal ein formales System zur Beschreibung einer formalen Sprache.
So, wir haben eine formale Sprache, wie wir vorhin hatten.
So, Wörter, die Anzahl von Einzelnen gerade sind.
Und das ist eine formale Sprache.
Und dann, es ist erzeugend, falls jedes Wort durch Verwendung dieses
System in vielen ähnlichen Schritten erzeugt werden kann.
Das heißt, wir haben ein System und in diesem System, in diesem System
können wir, dieses erzeugende System ist es, da können wir, wenn wir
dieses System verwenden, da können wir viele Wörter aus bestimmter
Sprache erzeugen.
Was ist dann ein Beispiel davon, ist es eine Grammatik.
So, so ein System können wir Grammatik nennen.
Grammatik, werde ich gleich erzählen, Grammatik ist nichts anderes als
eine Menge von Regeln.
Was heißt das?
Das heißt, eine Grammatik ist ein erzeugendes System, dass wir ein
paar Alphabets reinschauen und Wörter bestimmter Sprache rauskommen.
Dann haben wir analysierende Systeme.
Analysierende Systeme sind Systeme, die, wir geben einige Wörter zu
diese Systeme und die sagen, ob diese Wörter zu dieser Sprache,
bestimmter Sprache gehören oder nicht.
Und da sollen wir auch immer sehen, dass wir ähnlich viele Schritte
verwenden können, bei all diesen Systemen.
Analysierende Systeme sind zum Beispiel wie Automaten.
Wir haben bestimmte Automaten, Sie werden auch sehen, in Next Capital,
wir haben Automaten und mit Automaten können wir sehen, ob ein Wort zu
bestimmter Sprache gehört oder nicht.
Und da sind dann ein Beispiel davon, das schreibe ich hier, Automat.
Und dann haben wir auch ein System, das operationell ist, falls wir
eine bestimmte Sprache durch einen Term aus definierten Basismengen
und Operationen beschreiben können.
Und das ist auch so, wenn wir zwei Grammatiken haben, zwei Sprachen
haben, so Sprache 1 und Sprache 2 und wir aus beiden dieser Sprachen
irgendwie eine Kombination machen können, dass wir eine neue Sprache
erzeugen können, dann haben wir ein operationelles System.
Ein Beispiel davon wäre dann, Sie werden sehen, gleich reguläre
Sprachen.
Diese regulären Sprachen können wir aus Kombinationen mehrerer
Sprachen erzeugen.
Gut, im Folgenden wollen wir erstmal mit erzeugenden und
analysierenden Systemen uns beschäftigen.
Und erstmal wollen wir über Grammatiken sprechen und danach auch
Automaten.
So, nochmal hier eine Frage.
Wo gibt es Camtasia kostenlos?
Ich glaube, Sie müssen googeln.
Ich weiß es nicht.
Ich glaube aber, Camtasia Recorder gibt es nicht kostenlos.
Camtasia Player muss es kostenlos geben.
Ich habe selber Camtasia Recorder.
Ich denke, Sie sollen einfach googeln und Sie finden das.
Es gibt es aber schon.
Gut, dann möchten wir über Grammatiken sprechen und da ist es ein Bild
von Chomsky.
Er ist ein Wissenschaftler, der sich mit Sprachen beschäftigt hat.
Und dann hat er diese Chomsky-Sprache definiert.
Er ist ein Sprachwissenschaftler.
Er hat sich mit natürlichen Sprachen beschäftigt, das heißt mit
normalen Sprachen, Deutsch, Französisch, Englisch und so.
Und er hat versucht, diese Sprachen formal zu definieren.
Genauso, was wir jetzt machen zum Beispiel Menge, Alla, Alphabet und
so und so.
Und wir wollen das genauer jetzt schauen, aber vorher wollen wir ein
einführendes Beispiel erklären.
So, das ist diese Bacchus-Pnauer-Form.
BNF, das ist eine Sprache, das ist von zwei skandinavischen
Wissenschaftlern, ich glaube, vor vielen Jahren so gemacht worden.
Und die haben diese Sprache Algol geschrieben.
Das ist nicht meine Generation.
Algol ist ein bisschen älter als sogar meine Generation.
Das heißt, sie wissen das nicht, aber nur zur Information, wer Bacchus
-Pnauer ist.
Okay, so, das ist Namen in höhere Programmiersprachen wie Java und
Pascal.
So, wenn sie im Programmier eins hatten, sie wissen, dass sie können
Namen definieren in dieser Programmiersprache.
Sie können Namen schreiben.
Vielleicht jetzt können sie sich daran erinnern, zum Beispiel, sie
können nicht einen Namen haben, das zum Beispiel 100 und Apple heißt.
Aber sie können einen Namen haben, dass es zum Beispiel Apple 100 ist.
Das heißt, in diese höheren Sprachen, sie können Namen haben, die am
Anfang Buchstaben haben, aber kein Ziffer.
Und genau das, was sie hier sehen, das beschreibt, wie wir Namen in
solche höheren Programmiersprachen definieren können.
So, ein Name besteht aus erst mal Buchstaben und da sehen sie hier
zwei Klammen.
Und diese Klammen heißt Wiederholung.
Das heißt, sie können Wiederholung von Buchstaben oder Ziffer haben.
So, und dann haben wir hier Buchstaben definiert.
Buchstaben sind A oder B.
Also diese Zeichen hier bedeutet oder.
So, Buchstaben können A bis Z sein und Ziffer kann zwischen 0 und 9
sein.
So, hier nochmal ein bisschen Definition.
Namen, Buchstaben und Ziffer.
Wenn ich schreibe Name oder Buchstabe oder Ziffer in der Form, wir
reden von Variablen.
Sie können Buchstaben sagen, okay A oder Z oder D oder L, was auch
immer.
Das ist ein Variable.
Sie können dann selber dann mit bestimmten Buchstaben oder bestimmten
Namen das dann weiter genauer weg beschreiben.
Deswegen, wir nennen diese Variablen Non-Terminal-Symbols.
Diese Non-Terminal-Symbols, sie werden N als N bezeichnet.
Sie werden das sehr häufig verwenden.
Deswegen, was ist ein Non-Terminal-Symbol?
Das ist ein Symbol, das wir einfach als Variable nehmen.
Dann haben wir, okay, dieses Zeichen hier.
Dieses Zeichen ist nichts anderes als, symbolisiert eine Überführung
oder eine Ersetzung von Namen durch Buchstaben und dann Wiederholung
von Buchstaben und Ziffer und so weiter.
Und dann haben wir A, B und Z, 0 bis 9 und die heißen Terminal
-Symbole.
Das sind die Symbole, die wir im Terminal haben, auf unserem Keyboard
haben und die können wir eingeben.
Deswegen vielleicht die heißen Terminal-Symbole.
Dann haben wir diese zwei andere Zeichen, das habe ich auch gesagt,
die sind Sonderzeichen, heißt oder, so Ausfall unter Alternativen und
diese Klammen, die heißen Wiederholung.
Das heißt, ich kann eine Buchstabe, also hier die Beispiele, die ich
hier oben geschrieben habe, das erste Wort gehört nicht zu dieser
Sprache.
Warum?
Weil ich kann hier mit dieser Sprache nur Namen erzeugen, die erstmal
mit einem Buchstabe anfangen.
Zum Beispiel Buchstabe M und dann kann danach entweder eine Buchstabe
kommen oder eine Ziffer.
So, wenn Buchstabe, dann wäre da nochmal, was weiß ich, L und dann
nochmal L und dann Ziffer 0 und kann nochmal Ziffer kommen, was weiß
ich, 9.
Kann ein Name aus, so einen Namen können wir in Java oder C oder
Pascal oder so in solche Programmiersprachen definieren.
Und diese Grammatik sagt, wie wir solche Namen erzeugen können.
Es ist sehr einfach, sie sagen, ach so einfach, aber es ist erstmal
formal hier so beschrieben.
Jetzt wollen wir über Chomsky'sche Grammatik sprechen.
Ich muss schauen, wo das hier ist.
Ah, wer das geschrieben hat, hat sehr gut gedacht.
Die Frage geht zurück.
So, jemand hat gesagt, sehr gut beobachtet, sehr gut.
Wir haben hier eine Sprache definiert.
So, hier.
Und da habe ich gesagt, Anzahl der Einzelnen in W ist gerade.
Und ich habe gesagt, 000 gehört nicht zu dieser Sprache.
Das ist falsch.
Warum ist es falsch?
Weil ich kein Einsen habe.
Und wenn ich kein Eins drin habe, das ist auch gerade Anzahl von
Einsen.
Richtig?
Richtig.
So, das heißt, das Wort gehört nicht zu dieser Sprache, weil es nur
ein Eins drin ist.
Aber 0000 kann zu dieser Sprache gehören, weil wir hier einen Stern
haben.
Und alle Worte, die...oder ich muss noch überlegen.
Ah, ich weiß es jetzt wirklich nicht.
Ich muss es noch nachdenken.
Aber das ist eine sehr gute Frage.
Wer das gefragt hat, hat sehr gut beobachtet.
Gehört zu Sprache 0000?
Ja?
Sicher?
Okay.
Okay, dann gehört es so.
Hier bekomme ich Feedback von Frau Pfeiffer, dass es zu Sprache
gehört.
Gut.
Aber wir können das Double-Checking machen.
Sehr gut beobachtet.
Aber das sind genau diese Fragen, die in Klausuren sehr tricky sind.
Und sie sollen dann sehr gut denken.
Ich habe es nicht so im Bewusstsein gehabt.
Sehr gute Frage.
Ich schaue, wer noch hier was geschrieben hat.
Vielleicht bringt uns was.
Ja, okay.
Es ist das Gleiche, wahrscheinlich.
Okay, gut.
Wir sollen wirklich weitermachen, sonst...
Gut.
Diese Pakusnawa-Form haben Sie gesehen.
Es ist irgendwie eine Beschreibung, ein System, eine Grammatik, wie
wir diese Namen mit Java beschreiben können.
Jetzt wollen wir das mit Chomsky machen, weil diese Chomsky-Grammatik,
wie gesagt, wir wollen uns damit beschäftigen in dieser Vorlesung.
Und da gibt es eine Definition.
Diese Definition ist eine Definition von einer Grammatik.
Genau das, was wir gerade eben hatten.
Wir wollen das genauer beschreiben.
So, eine Chomsky-Grammatik ist ein Tuple.
Was ist ein Tuple?
Ein Tuple schreibt man so.
Das ist ein Tuple G und besteht aus mehreren Sachen.
N für Non-Terminal-Symbole.
Das haben wir gerade eben gehabt, was ein Non-Terminal-Symbol ist.
T für Terminal-Symbole.
P für eine Menge von Regeln, die wir genau beschreiben, was sind diese
Menge von Regeln und wie wir das beschreiben können.
Und S, es ist dann Start-Symbol oder diese Anfang-Buchstabe, das wir
hatten in dem Beispiel.
Aber hier kann alles so Start-Symbol, das ist eine größere, so eine,
vielleicht viel genereller als normale Bakusnawa-Sprachen, sondern das
ist jetzt hier komplett Chomsky-Grammatik und sehr allgemein.
So, N und T habe ich schon mal erzählt.
Was ist P?
P ist eine Regelmenge über N-Vereinigung-T.
Sie sehen hier, dass wir zwei Termen haben und die sind beide N
-Vereinigung -T.
Und einmal haben wir hier Plus.
Plus war so, dass wir kein leeres Wort hatten drin.
Und Stern, es ist alle Kombinationen auch mit leerem Wort.
P können wir auch anders schreiben, das ist jetzt so geschrieben, so
mit einer Multiplikation, aber sehr einfacher können wir so sehen,
dass P, es ist eine Submenge von dieser Menge hier, geschrieben durch
Phi, erzeugt Worte, C, C-Worte, so Phi und C.
Und dann Phi, es sind alle Worte, die Kombinationen von Nicht-Non
-Terminal -Symbolen und Terminal-Symbolen sind, ohne leeres Wort.
Und dann C sind die, alle Worte, alle Kombinationen auch mit leerem
Wort.
Das heißt, ich kann von Phi, Phi kann irgendein Wort sein, eine
Kombination, nur nicht leeres Wort, kann Kombination sein, von
Beispiel, das wir vorhin hatten, A, A, B, B.
Oder kann auch ein Non-Terminal-Symbol sein, zum Beispiel, wir können
hier einen Buchstaben haben, der ein anderes Wort erzeugt, C.
Und diese C kann auch zum Beispiel A, A, B, B sein und statt
Buchstaben kann ich dann was anderes haben, zum Beispiel Buchstabe,
das war diese Wiederholung, ich erkläre es jetzt gleich weiter, aber
nur, dass Sie sehen, dass ich Regeln haben kann.
Es ist eine Regel von Phi, von einem bestimmten Wort, die Terminal
-Symbole und Non-Terminal-Symbole hat, zu anderen Worten erzeugen
kann.
Es ist eine Regel.
Und S ist unser Start-Symbol.
Jetzt machen wir ein Beispiel, dass Sie sehen, wie das funktioniert.
Hier oben, ich bringe es hier runter, hier sehen Sie diese Bakusnauer
-Form und das Gleiche werde ich hier genauer in Chomsky-Grammatik-Form
schreiben.
So, wir schreiben N als Non-Terminal-Symbol, die Menge, Name,
Buchstabe und Ziffer.
Das hatten wir auch vorher bei Bakusnauer.
So, das war Name, Buchstabe, Ziffer hatten wir anders, aber hier
definieren wir als Menge von Non-Terminal-Symbolen.
Dann Terminal-Symbole, die sind dann halt Buchstaben und Ziffer, die
wir dort hatten.
Anfang Buchstabe, es ist dann Name, weil wir bei Bakusnauer gesagt
haben, wir können nur mit Namen anfangen.
So, das ist dann ein Name, Anfang Buchstabe, das kann nicht leer sein.
Und dann schreiben wir Regen.
Von Namen können wir, das ist ein Non-Terminal-Symbol, können wir
Buchstaben erzeugen.
Oder ein Buchstabe kann Namen ersetzen.
Ein Name kann auch durch Namen und Buchstaben ersetzt werden.
Was wir hier beachten sollen, ist es in diesem Beispiel, dass wir
immer mit einem Buchstabe anfangen dürfen.
Das heißt, wir können nicht schreiben, Name kann ersetzt werden durch
Ziffer, geht nicht.
Warum?
Weil wir müssen immer beachten, dass wir erstmal einen Anfang
Buchstaben brauchen.
Deswegen Name kann nur durch Buchstabe ersetzt werden.
Name kann durch Name und Buchstabe ersetzt werden.
Name kann durch Name und Ziffer ersetzt werden.
Und so können wir mit dieser allerersten Regel, wir stellen das fest,
das Name kann nur durch Buchstabe ersetzt werden.
Das erste Symbol kann nur ein Buchstabe sein.
Dann haben wir Buchstaben, das ist A bis C, da können wir alles
definieren.
Da müssen wir sehr viele Regeln schreiben, um vier Ziffer.
Da müssen wir mindestens zehn Regeln schreiben, dass wir die Ziffer
durch 0 oder 1, 1 bis 2, 3, 4 bis 9 ersetzen können.
Dann, so haben Sie das Beispiel verstanden, das ist eine sehr einfache
Grammatik.
Dann haben wir Überführbarkeit.
So, Definition gegeben, Regelmenge P. Was war Regelmenge P?
Das waren diese Regeln.
Und dann zwei Wörter.
Und diese zwei Wörter, die sind Wörter aus dieser N-Vereinigung T.
Non-Terminal-Symbole, Vereinigung Terminal-Symbole, Stern.
Das sind alle Kombinationen von Wörtern, die wir haben.
Und W heißt durch P unmittelbar überführbar in W.
Und wir schreiben das so.
Das heißt, wenn ich zwei Wörter habe, W und V und W.
Sorry, ich habe es auf Englisch gesagt, aber das ist so.
Wir haben einmal V und dann haben wir einmal W.
Das sind zwei Wörter zum A, A, B, B, C, C oder M, M, L, L, was auch
immer.
Wörter aus einem bestimmten Alphabet.
So, und dann V heißt unmittelbar überführbar in W.
Und wir schreiben das so.
Genau dann, wenn es U und Z gibt.
So, was heißt U und Z?
Sie sind auch eine Menge von N-Vereinigung T, Stern.
Und dann V und C gibt aus P mit V in diesem Form und W in diesem Form.
Das bedeutet, dass V hat einen Teil, das sieht so aus wie U und hat
einen Teil, das sieht so aus wie Z.
Und genau diese Teile, genau gleiche Wörter hat auch ein W.
So, hier hat U und hier hat auch Z.
Okay, und das bleibt in der Mitte.
Hier oben V und hier wir haben C.
Und dann, wir haben eine Regel hier.
Diese Regel sagt, dass wir V durch C ersetzen können.
Und dann heißt das, dass B unmittelbar überführbar in W ist.
Und V unmittelbar überführbar in W ist.
Da schreiben wir das so.
Ein Beispiel davon.
Wir hatten, so hier habe ich auch ein Beispiel, da kann ich dann
genauer schreiben.
Wir können zum Beispiel zwei Regeln haben.
Wir haben hier Name, nochmal Name und dann hier Buchstabe.
So, ich schreibe es nur BU und das heißt Buchstabe.
Und dann habe ich noch, das ist mein V, kann ein Wort sein.
Dann habe ich ein W und das ist auch Name.
Und dann hier in der Mitte Buchstabe.
Und dann hier auch nochmal Buchstabe.
Das heißt, wenn ich dann genau schaue, da kann ich sagen, das ist mein
U.
Hier ist U, für beide gleich muss sein.
Und hier ist Z, für beide ist es gleich.
Und dann habe ich dann hier eine Regel, das sagt mir, Name kann durch
Buchstaben ersetzt werden.
Und diese zwei Wörter, die zu dieser bestimmten Sprache gehören, die
können wir sagen, okay, V unmittelbar überführbar in W ist.
Wir werden Beispiele schauen, wie können wir aus kleinen Worten
größere Worte erzeugen und wie können wir dann die Wörter durch andere
Wörter ersetzen.
So, dann können wir das nicht nur einmal machen, sondern können wir
sehr häufig das machen.
Und dann haben wir eine reflexiv-transitive Hülle.
Aber das Wort ist ein bisschen kompliziert und Sie sagen, ach was soll
das, aber die Idee dahinter ist sehr einfach.
So, das Gleiche, ich kann hier in der Mitte statt Buchstaben was
anderes schreiben.
Wenn wir diese Regelmengen vorhin gesehen, so hier kann ich da zum
Beispiel Name, Buchstaben, da war ein einfaches Beispiel, das ich dann
genommen hatte.
Aber wir können zum Beispiel ein einfaches Beispiel nehmen, ein
bisschen komplizierter Beispiel nehmen.
Dann kann ich hier ein W schreiben, V und W.
Dann kann ich hier Name und hier Name und Buchstaben.
Aber ich kann dann W ein bisschen komplizierter schreiben und hier in
diesem Teil ist es U.
Und hier in der Mitte, ich kann dann noch ein bisschen länger
schreiben.
Zum Beispiel, ich kann schreiben Name, Buchstabe,
Ziffer und dann Buchstabe.
Okay, dieser Teil hat mir gesagt, das war Z wie oben.
Hier ist es auch Z und jetzt hier ist es V und das ist hier C.
Okay, wie ist es, so V kann durch C nicht so direkt ersetzt werden.
Warum nicht?
Weil das, was ich gerade geschrieben habe, das gehört jetzt nicht
gerade in unsere Regelmenge.
Wir hatten nicht Name, Buchstabe, Ziffer.
Okay, aber was
ich hier habe, so hier haben wir einen Namen.
Und diesen Namen kann ich dann, ich kann dann das andere Wort
erzeugen.
Aber ich kann es nicht direkt machen, sondern ich kann mehrere
Schritte machen.
Und wie sind diese mehrere Schritte?
Ich kann von Name, so von V, ich kann erst mal Name erzeugen und
Buchstabe.
Und von dieser Name, Buchstabe kann ich, ich muss auch selber schauen,
das ist ein bisschen tricky hier.
So, von Name kann ich ein Buchstabe machen oder ich kann von Name,
Name, Buchstabe und von Name, Name, Ziffer machen.
Okay, jetzt habe ich es gefunden.
So, ich kann von diesem Namen, Name, Ziffer erzeugen.
So, von Name kann ich Name und Ziffer erzeugen.
Das ist laut Regeln, das wir auf der letzten Folie hatten.
Und dann von diesem Namen kann ich nochmal ein Namen, Buchstaben
machen.
Das heißt, durch dreimal Regeln kann ich dann C erzeugen.
Das heißt, hier nochmal kommt es noch etwas dazwischen und da kommt C.
Ich sehe, dass es ja ein bisschen durcheinander ist und der Grund
dafür ist, dass ich bin nicht daran gewöhnt, so kleine, enge Folien
haben mit so viel Text nicht so viel Platz zum Schreiben haben.
Ich glaube, kommt aber ein Beispiel.
So, was bedeutet das?
Ich möchte, dass Sie die Bedeutung verstehen.
Das bedeutet, wir können V durch W ersetzen.
Wir können von V ein Wort erzeugen, mit Verwendung nur einer Regel.
Das war dann diese Orden, die wir hatten.
Aber wir können mehrere Regeln.
Wir haben V und dafür verwenden wir mehrere Regeln, bis wir dann W
erzeugen.
Und das ist dann, was hier steht mit diesem Form.
V kann ersetzt werden durch W, hier mit diesem Stern.
Dieser Stern haben wir gesagt, dass es immer mehrere bedeutet.
Das heißt, sehr häufig verwenden oder mehrere Kombinationen oder
sowas.
Aber hier bedeutet, dass wir diese Pfeile häufiger verwenden können,
bis wir W erzeugen können.
Ich glaube, wir haben gleich ein Beispiel.
Das kann ich vielleicht noch mal genauer beschreiben.
So, ich schaue, ob wir ein Beispiel haben.
Ja, genau.
So, und was bedeutet reflexiv-transitive Hülle?
Weißt ihr, was reflexiv-transitive Hülle bedeutet?
Okay, reflexiv.
Reflexiv haben sie schon mal gehabt.
Reflexiv heißt, dass ich, wenn ich zum Beispiel ein Wort V habe, kann
ich mit Verwendung bestimmter Regeln das gleiche Wort erzeugen.
Das ist reflexiv.
V kann durch V ersetzt werden.
Und transitiv heißt, dass ich, wenn ich ein V habe und von V so ein
Wort erzeuge, der so heißt, sage ich mal, etwas nicht V und C, nicht Z
und U.
Schau, ob ich das hier habe.
Irgendein Wort V' und V', dann habe ich etwas wie V'', oder W.
Dann kann ich schreiben, anhand von diesen zwei Dingen kann ich
schreiben V'B.
Das heißt transitiv.
Und diese beiden können wir dann hier verwenden.
Deswegen heißt reflexiv-transitive Hülle.
Jetzt kommen wir zum Beispiel.
Ich sehe hier, die Folie ist ein bisschen voll.
Aber erstmal sage ich, das war eine Grammatik.
Wir haben eine Grammatik.
Sagt uns, wie wir Wörter erzeugen können.
Und da können wir sagen, was eine Sprache ist.
Wir sagen, wenn wir eine Grammatik haben, dass es ein Tuple ist von N,
T, P und S, da können wir die Sprache L von G definieren.
Damals so auf dieser Folie, wo die Frage war, haben wir gesagt, L ist
die Anzahl von Einzelgeraden.
Hier können wir sagen, die Wörter aus T, Stern, das sind alle Wörter,
damit diese Terminals und Modeln erzeugt werden können, sind Wörter
dieser Sprache, so dass, wenn wir von S anfangen, dann nach mehreren
Schritten können wir das Wort erzeugen.
Und das ist eine Chomsky-Grammatik oder Sprache eine Chomsky
-Grammatik.
Das heißt, so hier sehen Sie nochmal diese Stern, das heißt von S, S
war ein Non-Terminal-Symbol, von S fangen wir an, dann ersetzen wir S
durch ein Wort, U1, dann ersetzen wir U1 durch U2 und so weiter und so
weiter, bis wir Wer erzeugen und dann haben wir ein Wort aus dieser
Sprache.
Das nennen wir Ableitung.
W ist ableitbar aus S.
Diese Pfeile nennen wir Ableitung.
Und diese Folge, dass wir von irgendeinem Wort anfangen und dann durch
mehrere Schritte ein Wort erzeugen, das heißt Ableitungsfolge.
Hier ist ein Beispiel, dass Sie ein bisschen besser das verstehen.
Das ist unsere Grammatik.
Das ist Chomsky-Grammatik.
Das kennen wir schon.
Und dann können wir eine Ableitung schreiben.
Wir fangen mit S.
Das ist das Anfang.
So, Terminal-Symbol.
So, Non-Terminal-Symbol hier.
Haben wir selber gesagt hier.
Wir fangen mit S an.
Es ist ein Name.
Wir können nur mit Namen anfangen, weil wir so definiert haben.
Und dann können wir sagen, Name kann ersetzt werden durch Name und
Ziffer.
Warum?
Weil wir hier eine Regel haben, die das uns sagt.
Und dann kann ich nochmal sagen, Name, so das hier, genau diese Name
-Ziffer, kann ersetzt werden durch Name, Ziffer, Ziffer.
Warum?
Weil ich genau die gleiche Regel nochmal verwendet habe auf diesen
Namen.
Dieser Name ist jetzt Name-Ziffer und die Ziffer dort ist direkt hier
runtergekommen.
Und dann kann ich das Gleiche nochmal weiter, so diese Ableitungsfolge
kann ich noch haben.
Da kann ich schreiben, Name, haben wir oben gehabt, Name kann durch
Buchstabe ersetzt werden.
Dann habe ich hier Buchstabe, Ziffer, Ziffer.
Kann ich letzte Ziffer mit 2 ersetzen.
Warum?
Weil ein Ziffer kann durch hier 2 ersetzt werden.
Dann habe ich nochmal hier eine andere Ziffer, da kann ich auch durch
eine beliebige Ziffer ersetzen.
Und Buchstabe kann ich auch durch Buchstabe hier 1 ersetzen.
Und so habe ich eine Ableitungsfolge von dieser Ableitung und habe ich
dann ein Wort erzeugt.
So haben Sie verstanden, wie das funktioniert.
Das heißt, Sie sollen nicht so konzentrieren, was reflexive,
transitive Hülle heißt, sondern denken Sie, wie Sie aus einer
Grammatik Worte erzeugen können.
Und das ist nichts anderes, als wir hier einen Namen, ein Anfang
-Alphabet haben oder Anfang-Non-Terminal-Symbol haben.
Und da können wir davon Worte erzeugen.
Wir können mit diesen Regeln beliebige Worte erzeugen.
Nur Eigenschaft ist es so, dass wir nur am Anfang einen Buchstaben
haben dürfen.
So, wir haben hier einige Vereinbarungen.
So, erstmal Non-Terminal-Symbole wollen wir mit großen Buchstaben
schreiben.
So, alles was groß ist, groß geschrieben wird, A, B, N, was auch
immer, es ist ein Non-Terminal-Symbol.
Kleine Zeichen sind Terminal-Symbole, wie A, B, C, was auch immer.
Worte schreiben wir wie U, V, W, Phi, C, Tau und so weiter.
Und statt so zu schreiben, Phi kann durch C1 ersetzt werden, und so
weiter, und so weiter, schreiben wir diese Zeichen dazwischen.
Und dann haben wir das, was wir auch beim Bakusnawa-Form hatten, das
heißt, das bedeutet genau das hier oben.
Das ist ein bisschen kompakter.
Gut, Sie haben gesehen, dass was wir gerade als Chomsky-Grammatik
hatten, ist sehr allgemein.
Wir können beliebige Worte erzeugen, beliebig, ich meine, fast alles.
Aber es gibt eine Problematik hier, und das ist dann die Motivation,
warum wir in den nächsten Folien uns mit verschiedenen Grammatiken
noch beschäftigen wollen.
Und das Problem ist, dass es in allgemein nicht algorithmisch
entscheidbar ist, ob ein Wort zur Sprache einer vorgegebenen Grammatik
gehört oder nicht.
Das heißt, ich gebe eine Grammatik, irgendeine Grammatik, erfunden von
mir, und ich gebe auch ein Wort.
Und Sie können nicht sagen, ob das Wort einfach so zu dieser Grammatik
gehört.
Es ist schwierig, das zu wissen.
Und diesen Beweis sehen Sie auch später, ich glaube, in Kapitel 2,
wenn Sie Beweis dazu sehen.
Und noch etwas interessanter ist es, dass wir nicht wissen, wie groß
ist der Aufwand.
Wenn ich irgendein Wort gebe, V, und Sie eine Grammatik haben, G, und
ich sage, okay, ob V erstmal mit dieser Grammatik erzeugt werden kann,
Sie sagen, ich weiß es nicht, aber die andere Frage ist, wie viel ist
der Aufwand?
Wie viel Zeit brauchen Sie, oder wie viele Operationen brauchen Sie
überhaupt, um das zu sagen?
Das ist auch nicht einfach, und das ist auch was, was uns
interessiert, in den nächsten Folien.
Wir interessieren uns auch, zu wissen, welche Strukturen durch eine
Grammatik grundsätzlich beschreibbar sind.
So, was für Worte, also wenn ich komplizierte Worte erzeugen würde,
nur diese komplizierten Worte erzeugen möchte, was für Grammatik, wie
kann ich dann diese Struktur von Grammatik haben?
Und das ist auch etwas, das wir gleich sehen werden.
Wir beschränken uns dann allgemein zu Chomsky Grammatik, und wir
werden dann Grammatiktypen von Chomsky dann gleich schauen.
So, dann gibt es diese Hierarchie.
Wir haben Chomsky Grammatik, genau, G, ein Tupel von N, T, P und S.
So, ich weiß nicht, wie häufig ich die Vorlesung halte.
Ich glaube, vielleicht heute ist es das letzte Mal, oder vielleicht
nächste Woche bin ich einmal dran, aber dann bin ich nicht mehr dran.
Aber was ich sagen möchte, ist, wenn Sie eine Klausuraufgabe bekommen,
wenn Sie eine Grammatik beschreiben wollen, formal beschreiben, sollen
Sie wirklich auch so von vorne so schreiben, ein Tupel, N, T, P und S
und so weiter.
Sie sollen das wirklich schreiben auf den Klausuren.
Das ist ein Fehler, dass ich immer damals, als ich die Vorlesung
betreut habe, habe ich immer gesehen, so Leute, Studenten wissen
eigentlich, was das ist, aber die schreiben das nicht auf, und das ist
auch vielleicht ein Punktenabzug.
Wenn Sie etwas formal beschreiben, sollen Sie von Anfang an alles
richtig formal beschreiben, und das gehört auch dazu.
Deswegen schreiben wir immer, wenn wir eine Definition haben, wir
haben eine Grammatik, G, ein Tupel von N, T, P und S, und das heißt
Tupnul -Grammatik.
Das ist eine Chomsky-Grammatik, es ist eine Tupnul-Grammatik, oder die
sogenannte Phrasenstruktur-Grammatik.
Und P ist beliebig.
P war Regelmenge, und das hatten wir bis jetzt, P war beliebig.
Mit P können wir beliebige Worte erzeugen.
Da machen wir das ein bisschen schwieriger.
Da haben wir Typ 1-Grammatik, und diese Typ 1-Grammatik ist die
sogenannte Kontextsensitive-Grammatik.
Das heißt, wir sind jetzt sensitiv zu Kontext, und diese Grammatik
kann alle Produktionen von dieser Form erzeugen.
Und was bedeutet das?
Das bedeutet, wir haben ein Wort, V, das ist V1, A, V2, und das kann
ich dann...
Und V1 und V2 und C, die sind Non-Terminal-Symbole und mit Stern.
Und da kann ich ein Wort haben, B, das ist V1, C und V2.
Das ist ähnlich, wie was wir vorhin hatten.
Das heißt, wenn ich diese Wörter schreibe, so irgendwie ein Wort, dann
habe ich hier V1, so kann ich dann hier zum Beispiel U schreiben, da
kann ich hier Z schreiben.
Das Gleiche hat hier unten, der erste Teil ist genau gleiche U, weil
es ist V1 und V1, und hier ist es auch Z, das Gleiche.
Und dann hier habe ich irgendwie ein Teil, so hier, was hier ist,
diese A, und hier habe ich C, diese Regeln.
Und das hat nur eine Eigenschaft.
Die Eigenschaft ist es, dass C kein leeres Wort sein kann.
Das bedeutet, dass die Länge von W, weil C kann nicht leer sein, A
kann leer sein.
Weil wenn C nicht leer sein kann, das bedeutet, dass die Länge von W
immer größer oder gleich ist als die Länge von V.
Und wenn ich dann durch eine Ableitungsfolge mehrere Wörter erzeuge,
dann alle Wörter sind so.
Zum Beispiel, wenn ich eine von V, V' und dann V' und dann W erzeuge,
es ist so, dass, weil W kann, hier in der Mitte, C kann kein leeres
Wort haben, dann ist es die Länge von W größer gleich als die Länge
von V' und V'.
Und das sagen wir, dass es eine monotone Grammatik ist.
Weil das ist einfach diese Länge, das ist immer so hier nach so die
Länge, genau.
Das ist dann eine monotone Grammatik.
Gut, dann haben wir jetzt Typ 2 Grammatik, die sogenannte...
Ah, okay, und was wir auch noch auf Typ 1 haben, ist die S,
Startsymbol oder hier Anfang, das kann Lambda sein.
Das heißt, wir können leere Wörter damit erzeugen.
Ja, das ist auch etwas, das wir vielleicht mit anderen Sprachen nicht
haben können.
Das muss ich noch genauer jetzt gleich schauen.
Dann haben wir Typ 2 Grammatik, diese kontextfreie Grammatik.
Und diese P-Regelmenge, es ist anders.
So, wir haben hier diese Regelmenge.
Bei Chomsky Grammatik hatten wir hier oben N, U...
Also, wenn ich dann genau in diesem Formschreiben kann, dann ist es P,
das war so N, U, T plus mal N, U, T, Stern.
Und hier, was wir hier haben, es ist N.
Das heißt, ich kann nur mit Non-Terminal-Symbolen anfangen.
Ich kann keine Terminal-Symbole am Anfang haben.
Und dann kann ich dann beliebig...
So, dann ist es dann gleich wie hier oben bei Chomsky, also diese
allgemeine Chomsky Grammatik.
Das heißt, ich kann alle Produktionen haben, die A durch C ersetzen.
Und A ist das Non-Terminal-Symbol.
Das ist ein feiner Unterschied.
Es ist nicht so viel Unterschied.
Ich meine, da können wir sagen, eigentlich hier das Wort, das wir hier
erzeugen, das kann auch zum Typ 0 gehören, weil das ist eine Submenge
davon.
Gut, dann kann ich noch Typ 3 Grammatik definieren.
Das ist diese rechtslineare Grammatik.
Warum rechtslinear?
Weil wir hier in dieser Produktionsmenge, das ist ähnlich jetzt wie
oben, das ist wie bei Typ 2, da haben wir hier N.
Aber im zweiten Teil ist es ein bisschen komplizierter.
Wir haben T-Vereinigung, T-N.
Und da N auf der rechten Seite kommt, heißt das rechtslinear.
Ich kann eine linkslineare Grammatik haben und linkslineare Grammatik
kann N-T sein.
So hier T-N heißt Non-Terminal-Symbol, kann nur auf die rechte Seite
kommen.
Linkslinear wäre dann andersherum.
Ja, so und das ist auch irgendwie eine Beschränkung, dass wir sagen
so, weil bei rechtslinearen Grammatik können wir Worte erzeugen, die
einfach hier Non-Terminal-Symbole auf die rechte Seite kommen.
Gut, das sind die Definitionen.
Sie werden sich auch im Laufe der Vorlesung sehr viel mit dieser
Definition beschäftigen.
So, Typ I, wenn wir Grammatiken haben, Typ 0, also 1, 2 und 3
Grammatiken haben, dann können wir auch Sprachen definieren, die Typ I
Sprachen sind.
Wir haben E-Grammatik, das heißt ich muss Grammatik Typ 0 nennen und
eine Sprache von dieser Grammatik dann erzeugen haben.
Und das ist auch, dann definieren wir so.
L ist das Language, Sprache von I und E-Stern sind unser Alphabet.
Und das ist eine Chomsky-Sprache von Typ I und I kann 0, 1, 2 und 3
sein.
Falls es eine Grammatik G gibt, auch ein Typ L, genau, N, T, P und S
von Typ I.
Das heißt, wir müssen eine Grammatik aus der letzten Folie nehmen,
dass es Typ I ist und von dieser Grammatik können wir eine Sprache
definieren.
Und das definieren wir auch so, genauso wie es ist so eine Sprache von
Typ I, L, E ist unser Alphabet, dass wir Sprache mit diesem Alphabet
erzeugen können.
Und das ist dann die Sprache, das bezeichnen wir so.
Aber was bedeutet, jetzt ist es formal, aber verstehen wir, was das
bedeutet.
Das bedeutet, dass wir Sprache Typ 0 haben, Sprache Typ 1, Typ 2 und 3
und dann können wir diese Folierung haben.
Wie ich vorhin kurz erwähnt habe, die letzte Folie.
So, eigentlich, wenn Chomsky-Grammatik so allgemein ist, dann alle
diese Grammatiken, die wir bis jetzt definiert haben, Typ 1, Typ 2 und
Typ 3 oder sage ich mal, Typ 2 habe ich gesagt, das ist eigentlich,
weil Typ 0 allgemeiner ist als Typ 2.
Typ 2 kann, so wie wir hier in der nächsten Folie schreiben, jede Typ
3 oder Typ 2 Grammatik, jetzt mache ich so, jede Typ 3 Grammatik ist
offensichtlich von Typ 2 und Typ 1 Grammatik auch von Typ 0.
Ja, weil das ist immer so allgemein und ein bisschen beschränkt und
beschränkt und beschränkt und beschränkt.
Und das gleiche ist es auch so, dann hier Typ 3 kann auch eine Sprache
sein, so eine Grammatik sein von Typ 0.
Nur da hier, wenn wir genaue Definitionen schauen, was hier so ein
bisschen problematisch ist, ist Typ 2.
Typ 2 Grammatik, Grammatiken sind in allgemein nicht von Typ 1.
Und das ist, was wir hier schreiben.
Und warum?
Das heißt, wir können diese allgemeine Regel sagen, jede Sprache von
Typ I ist auch eine Sprache von Typ I minus 1, 1, 2 und 3.
Nur eine Schwierigkeit gibt es hier bei Typ 2 auf Typ 1.
Und wenn ich kurz zurückgehe zu Typ 2 und 1, da sehen wir, bei Typ 1
haben wir gesagt, also diese Regel war, dass C kann nicht leer sein
und dann, es gab noch etwas anderes, das muss ich hier genauer
schauen, da ist das ein Problem mit leerem Wort.
Hier können wir, also hier bei Typ 2 fangen wir mit N an, hat kein
leeres Wort da drin.
Bei Typ 1 können wir im Prinzip diese Stern hier haben und können wir
leere Worte erzeugen.
Das ist nur das.
Und wenn wir auf die nächste Folie schauen hier, diese Schwierigkeit
ist die Behandlung von leeren Worten.
Und wenn wir das, abgesehen davon, da können wir sagen, jede Sprache
von Typ I ist auch von Typ I minus 1.
Es ist ein bisschen so, ich muss auch meine Handzettel schauen, dass
ich alles erkläre.
Das heißt, es ist ein bisschen schwierig, die Sachen zu verstehen,
aber wenn Sie wissen, so diese Chomsky Grammatik ist allgemein und
dann haben wir immer das beschränkt und so weiter bis Typ 3, dann
können wir sagen, ja Typ 3 ist Typ 0, Typ 2 ist wie Typ 0 und so
weiter.
Nur es gibt eine Schwierigkeit da zwischen Typ 2 und Typ 1 und das ist
das, dass wir bei Typ 1 keine leeren Worte haben können.
So, zwei Grammatiken, da haben wir noch eine Definition.
Zwei Grammatiken, G1 und G2 heißen Äquivalent, falls die Sprachen
gleich sind.
Ich sehe, hier gibt es eine Frage, widerspricht Punkt 2 nicht Punkt 3?
Punkt 2, Typ 2 Grammatiken sind allgemein.
Jede Typ 3 Grammatik ist offensichtlich von Typ 2, das ist schon
richtig.
Und jede Typ 1 Grammatik auch von Typ 0.
Richtig.
Und 2 widerspricht das nicht, weil Typ 2 ja nicht von Typ 1 ist.
Ah, danke.
Ja, aber hier haben wir gesehen, okay, wenn wir diese Schwierigkeit
nicht sehen, dann abgesehen davon können wir sagen, jede Sprache von
Typ I ist auch von Typ I-1.
Das widerspricht sich, aber das Problem ist nur das leere Wort.
Und abgesehen davon, das können wir dann so sagen.
Zufrieden?
Nein, nicht.
Einige sagen, schneller.
Nein, das ist ein Fehler vom System.
Gut, ich mache es tatsächlich schneller.
Ich weiß nicht, wie viele Worte wir haben.
Gut, in den nächsten Folien werden wir uns erstmal mit Automaten
beschäftigen.
Automaten nehmen wir, also wir können ein Automat nehmen als System
und wir analysieren, ob ein Wort zu bestimmter Sprache gehört oder
nicht und Grammatik gehört oder nicht.
Und dann fangen wir mit Typ 3 Sprachen an.
So, ich gehe weiter auf den nächsten Folien.
So, die Folien sind schon online.
Ich habe gestern einfach, es ist auch so, dass ich auch keinen Zugriff
auf den VORB habe, wie ihr alle, wie Sie alle.
Und ich habe vergessen, dass ich gestern die Folien, eigentlich könnte
ich letzte Woche schicken, dass die Kollegen die Folien hochladen.
Ich habe keinen Zugriff auf den VORB, genau wie alle anderen.
So, ich kann nur VORB besuchen und ich könnte leider die Folien
gestern Abend nicht hochladen und heute Morgen hat mein Kollege
hochgeladen.
Gut, wir fangen mit Automaten.
Die Automaten sind sehr interessante.
Das ist sehr interessante.
Nein, das ist nicht, was ich suche.
Okay, noch eine Frage.
Pause.
Wollen Sie Pause haben?
Wie viel Pause wollen Sie haben?
So, ich weiß nicht, was ich mit Aufzeichnung machen soll.
Schauen Sie, Pause.
Mit Kapitel 2, ähnliche Automaten.
Und ähm,
ja.
So, ähnliche Automaten oder die sogenannte Finite State Machines, die
sind Automaten mit Ausgaben.
Automaten kennen wir wie Warenautomaten.
Ja, so Kaffeeautomaten, Bahnhof-Ticketautomaten oder Ampelsteuerung,
das hatten wir am Montag.
Und haben Sie sich gefragt, wie sie sind?
So, die sind nicht Computers, die sind kein Universalrechner, sondern
die sind einfachere Systeme und die sogenannten Automaten.
Die haben einen bestimmten definierten Ablauf von Handlungen und was
sie dort haben, sind Eingaben.
Ja, so in Warenautomateingabe ist das Münze, das sie reinwerfen.
Und dann haben wir den Zustand.
Entweder Zustand ist es so, dass Geld drin ist, ist genug Geld drin
oder es ist nicht genug Geld drin und so weiter.
Und dann haben wir eine Ausgabe, das ist entweder Ware kommt raus oder
Geld kommt zurück oder Bankkarte, so eine Fahrkarte kann verkauft
werden.
Und da es bestimmt so eine endliche Menge von Alphabeten oder Input
-Output von Eingaben und Ausgaben gibt und Zustände, deswegen die
heißen endliche Automaten.
Das heißt, es sind vielleicht zehn Schritte, um von Input eine Ausgabe
zu haben.
So, wie sieht das aus?
Wir haben Eingabe E in einem System und drin sind einige Zustände, die
haben dann in dieser Ampelsteuerung gesehen, diese runden Kreisen, die
waren dann die Zustände, die wir gezeigt haben, dann haben wir eine
Ausgabe.
So, die tatsächlich funktioniert drin.
Wenn Sie einen Warenautomat aufmachen, Sie sehen tatsächlich
mindestens die ältere Form davon.
Die waren so zwei, so ein Eingabeband.
Ja, so zack, zack, zack, so für verschiedene Eingaben.
Die Leute haben dann Eingabenband gemacht, so für bestimmte Menge, so
Länge von Eingabenwörtern.
Dann haben wir Ausgabeband und da gibt es etwas, so ein Gerät oben,
dass es dann irgendwie zwei Leseköpfe hat.
Einmal nach oben, einmal nach unten und dann sagt, okay, für diese
Eingabe und diese bestimmte Zustand, zum Beispiel S1, kann irgendwie
eine Ausgabe kommen.
Das funktioniert tatsächlich so.
Und dann gibt es zwei Formen von solchen, also mehrere Formen
wahrscheinlich, aber zwei Formen, die uns interessieren jetzt an
dieser Stelle.
So, eine ist das, die sogenannte Mili-Automat und die andere ist das
Mur -Automat.
Und den Unterschied zwischen den beiden Automaten sehen wir gleich,
aber allgemein hier zu sagen, es ist diese Ausgabe.
So, hier Ausgabe beim Mili-Automaten wird jedes Mal, dass eine Eingabe
kommt, sagt man, okay, Zustand das und Ausgabe so.
Das wird dann definiert.
Und beim Mur-Automaten, Ausgabe ist im Zustand.
Das heißt, ich muss nur sagen, Eingabe das führt zu einem bestimmten
Zustand und in diesem Zustand gibt es Ausgabe drin.
Wir werden genau Beispiele sehen, aber jetzt erstmal Definition von
Mili -Automaten.
So, ein Mili-Automat ist ein Tupel, genau nochmal Tupel und diese
Tupel besteht jetzt aus mehreren Dingen.
Bei Grammatik hatten wir weniger Elemente drin, aber jetzt hier haben
wir mehrere.
Erstmal hier E für Eingabe-Alphabet, dann haben wir S Zustandmenge,
dann A für Ausgabe-Alphabet, dann haben wir zwei Funktionen.
Eine ist es Delta, sagt mir, wenn ich einen Zustand, einen bestimmten
Zustand habe, so ich bin im Zustand zum Beispiel, eine Münze Euro ist
richtig im Warenautomat und diese eine Münze ist Alphabet, so für
bestimmte Eingabe und Zustand führt mich zum nächsten Zustand.
Und Gamma, es ist dann Ausgabe-Funktion und Ausgabe-Funktion sagt, für
bestimmte Zustand und Eingabe-Alphabet, da habe ich bestimmte Ausgabe.
Und oben ist es dann diese Überführungsfunktion, das heißt, für
bestimmte Eingabe und Zustand, dann sagt mir, in welchem Zustand ich
landen werde und nochmal, wie ich dann weiter machen kann.
Anfangszustand, das haben wir hier, da müssen wir immer in diese
Tüpfel schreiben, bitte beachten Sie das und das ist dann S Null, das
ist auch ein Element aus Menge S und S ist Zustandmenge.
So, hier, vielleicht ist das ein bisschen zu viel Text hier, aber wie
allgemein diese Automaten funktionieren, wenn wir wirklich diese
Warenautomaten aufmachen, wie funktioniert das?
Es ist in Programmiersprache oder in Pseudocode geschrieben.
Erstmal müssen wir M in Zustand S Null bringen.
M ist es dann unser Milliautomaten.
Das heißt, jedes Mal, dass wir ein Warenautomaten kaufen wollen, das
muss das Gerät erstmal in S Null sein oder jemand muss das in S Null
gebracht haben.
Okay, und dann Lesekopf über das linkste Zeichen des Eingabewortes
lassen.
So, hier, wir schauen hier, wir haben diese Eingaben oben, das ist
Lesekopf und da müssen wir schauen, dass wir auf dem linkesten hier so
Lesekopf dann lassen.
Da wollen wir Eingabealphabets, so Eingabewort lesen, eins nach dem
anderen, die Buchstaben drin oder die Zeichen drin.
Dann gehen wir in eine Schleife, diese Weil-Schleife, kennen Sie Weil
auch von Programmieren.
So, falls wir ein Zeichen unter Lesekopf haben, das heißt so lange,
dass wir Eingabe haben, dann schreiben wir gemäß dieser
Ausgabefunktion ein Zeichen auf das Ausgabeband.
So, wir schauen hier, was Eingabe ist, ob zum Beispiel Warenautomat
ein Euro Münze ist drin, so ein Euro rein, Eingabe rein.
Und dann schauen wir mal hier, was für Zustand wir schon vorher
definiert haben für diese Münze, was auch immer.
Und dann kommen wir hier auf diese Ausgabe.
Oder wir gehen, so dann finden wir erstmal Ausgabe und dann finden wir
auch, in was für Zustand führt uns.
Ob ein Euro zum Beispiel, wenn wir in Ware kaufen, dass es zum
Beispiel ein Euro kostet und wir zwei Euro reintun.
Zwei Euro rein, dann Zustand wechseln, Ware ausgegeben.
Und dann müssen wir nochmal zu Zustand kommen, dass dieser Zustand
sagt, jetzt gibt ein Euro zurück.
Das ist dann für sich auch noch ein Ablauf.
Deswegen sind wir hier, dass wir schauen, in welchem Zustand wir
landen, ob es Endzustand ist oder noch andere Ablauffolgen, die wir
noch brauchen.
Dann Lesekopf müssen wir noch, ein Feld nach rechts.
Oder eigentlich, was da passiert ist, das Lesekopf ist fest in dem
Gerät.
Was passiert, diese Eingabe-Band bewegt sich im Automaten.
Und nochmal Schreibkopf müssen wir auch so, das heißt diese Eingabe-
und Ausgabebänder müssen einmal gedreht werden.
Und dann sind wir beim nächsten Alphabeten.
Und das wird dann so lange durchgeführt, dass wir dann fertig sind mit
diesem Ablauf.
Das war nur ein Beispiel von diesem Automaten.
Ich muss es immer für mich noch veranschaulichen, wie das alles ist.
Und deswegen habe ich das Beispiel gesagt.
Wir haben noch andere Beispiele gleich.
Wir sehen, wie das ungefähr funktioniert.
So, wenn wir das jetzt darstellen wollen.
Wie ist das?
Wir haben diese E1 bis ER, die sind unser Eingabe-Alphabet.
Dann haben wir diese Zustände, S0 bis SN, die sind diese Zustände.
Was wir noch hier haben, das ist für Eingabe-EI.
Und falls wir in Zustand SJ sind, so wir sind jetzt in Zustand SJ,
kommt EI rein.
Dann wechsle ich zu Zustand K und gebe ich Ausgabe H.
So funktioniert es.
Zeile sagt mir Zustand des Automaten.
Ich befinde mich gerade zum Beispiel in SJ.
Spalte sagt mir, was für Eingabe ich habe.
Kann sein von gleicher Eingabe, aber in Zustand zum Beispiel SJ-1.
Ich was anderes.
Ich gehe irgendwo anders hier.
Das wird sich ändern.
Wir müssen diese Tabelle definieren, wie wir unsere Automaten
programmieren wollen.
Und Spalte sagt uns, was für Eingabezeichen wir haben.
Und Feldeintrag ist das, was ich genau erzählt habe.
Erstes Zeichen, neue Zustand.
Das heißt, ich muss dann in den neuen Zustand SK zum Beispiel gehen.
Und zweites Zeichen ist Zeugeausgabe A, zum Beispiel AHI.
Gut, das können wir mit solcher Darstellung, so Zustandsdiagramm
gerichtete Graf, zeigen.
Das machen wir auch.
Sie werden es auch in Ihren Übungen und allgemein so zeigen.
Auch mit Tabelle, aber auch noch hier so diese Art von
Zustandsdiagramm.
Und das hier sehen Sie, Sie sind in Zustand SJ.
Kommt Eingabealphabet EI, Sie gehen zu Zustand SK.
Das heißt, in diesen Kreisen, wir schreiben nur Zustände.
Hier sehen Sie zwei Zustände.
Und hier ist es Eingabe EI, geben wir Ausgabe AH.
Und das schreiben wir formal so.
Das ist Überführungsfunktion für Input, wenn wir in SJ sind.
Und wenn wir EI haben, dann gehen wir zu SK.
Und Ausgabefunktion wäre dann SJ und Alphabet EI.
Dann Ausgabe ist AH.
So, Knoten, wie ich vorhin erwähnt habe, interner Zustand des
Automaten.
Nur Zustände werden dort so präsentiert und Kanten sind
Zustandsübergänge.
Das haben wir hier diese Übergangfunktion so beschrieben.
Kantenbeschriftung habe ich auch schon mal erzählt, Eingabe und
Ausgabe.
So, einfachster, ähnlicher Automat, das wir programmieren können.
Es ist ein Mausefalle.
Aber Sie sehen hier mit diesem Beispiel, wie wir das alles dann
darstellen können.
So, wir haben erstmal Eingabealphabet E.
Sagt, Maus kommt im Plus oder Maus kommt nicht im Minus oder Falle
spannen.
Das sind diese drei Eingaben, dass wir mit diesem Automaten haben
können.
Dann haben wir Zustandmengen, entweder Falle ist gespannt, G+, oder
Falle nicht gespannt, G-.
Und Ausgabe ist das, F- oder F+, und F- heißt Maus gefangen oder Maus
frei.
So, wie machen wir das?
Wir machen erstmal eine Zustandstafel.
Wir sagen, okay, wenn Eingabe, so hier hatten wir Eingaben, so hier
Eingaben und hier waren Zustände.
So, wenn Eingabe im Plus ist, das heißt, Maus kommt und Zustand ist G
-.
Das heißt, Falle nicht gespannt.
Was passiert, wenn Falle nicht gespannt ist und Maus kommt?
Ausgang wäre...
Warte mal...
Sorry.
So, hier ist es unser Zustand.
Maus kommt und Falle gespannt.
Was passiert ist das?
Erstmal Ausgabe ist es, dass Maus gefangen.
Ja, Maus kommt, ist gespannt, Maus gefangen.
Und Zustand wechseln wir, weil dieser nächste Zustand wäre, dass Falle
nicht gespannt.
Gut.
Wenn genau diese, so wenn Maus kommt und Falle nicht gespannt ist, was
passiert ist das?
Ausgabe ist es, dass Maus frei ist.
Und Zustand wäre dann G-, heißt Falle bleibt nicht gespannt.
Bis irgendwann jemand geht und das dann noch ändert.
Und das gleiche können wir für M- und SP machen.
Das gleiche kann ich im Zustanddiagramm machen und das möchte ich in
diesem Zustanddiagramm erstmal hier genauer beschreiben.
Ich glaube, das brauchen Sie für die nächsten Folien und nächste
Vorlesungen.
Deswegen werde ich hier erst im Zustanddiagramm das genauer
beschreiben.
So, wir haben gesagt, mit Knoten beschreiben wir die Zustände.
So, was heißt das?
Das heißt G plus.
Wie viele Knoten haben wir?
Nur zwei, weil wir nur zwei Zustände haben.
Entweder Zustand ist es, dass Falle gespannt ist oder Falle nicht
gespannt ist.
Und genau das, was wir in der Tabelle haben, können wir hier haben.
Eigentlich von dieser Tabelle können wir genau dieses Zustanddiagramm
machen.
Oder für solche kleinen, ganz, ganz kleinen Beispiele können wir auch
selber das definieren.
So, wenn hier Zustand G plus ist, das heißt Falle gespannt ist und
Maus kommt nicht, M minus,
was passiert ist, dass ich habe F plus, das heißt Maus ist frei und
bleibt einfach so.
Wenn ich G plus habe und nochmal, das heißt bleibe ich immer noch in
diesem Zustand, so lange, dass das was ändert in der Eingabe Alphabet.
So lange, dass zum Beispiel M plus kommt.
Wenn M plus kommt und ich in G plus bin, was passiert ist, ich bin in
der Falle gespannt und Maus kommt, dann weiß ich, dass ich meinen
Zustand wechseln kann und in G minus kommen kann.
Weil erstmal Ausgabe ist es, dass Maus gefangen ist und dann ich
wechsle meinen Zustand, da bin ich in G minus, das heißt Falle nicht
gespannt.
Und solange das Falle nicht gespannt ist und sich nichts ändert, dann
bleibe ich dort.
Und wenn eine Eingabe kommt, Falle spannen, dann kann ich nochmal zu
diesem Zustand kommen und dann nochmal weitermachen.
Haben Sie das verstanden?
Ich hoffe, dass das Beispiel nicht so einfach war, dass Sie sagen, es
interessiert Ihnen nicht, das zu verstehen oder so.
Ja, haben Sie es verstanden?
Es gibt eine Frage.
Die Aufzeichnung ist an.
Gut, natürliche Fortsetzung und genau, dass wir mit dieser
Ableitungsfolge hatten, dass wir ein Wort durch mehrere Wörter erzeugt
haben, das können wir bei etlichem Automaten machen.
Das ist wirklich eine natürliche Fortsetzung, dass wir sagen, okay,
wir haben diese Überführungsfunktion, diese Delta, das sagt uns, wenn
wir in einem bestimmten Zustand sind und ein bestimmtes
Eingabealphabet haben, dann können wir in einem anderen Zustand
landen.
Eine natürliche Fortsetzung wäre dann, wenn wir nicht nur ein Alphabet
haben, nicht nur ein Buchstabe oder eine Eingabe haben, aber ein Wort
von Eingaben haben.
Das heißt, dann haben wir nicht nur ein E, sondern ein E-Stern.
Das heißt, was wir letzte Folie gesehen hatten, da hatten wir nur ein
E1 oder EI.
Aber jetzt möchte ich etwas haben, so ein Eingabewort haben, das dann
mehrere Elemente hat.
So, was passiert?
Es ist einfach, dieser Lesekopf liest erstmal linkes Eingabealphabet.
Und ich bin in Zustand Null.
Neuer Zustand wäre dann, ich bin mit dieser Überführungsfunktion, ich
bin in Zustand Null, ich habe das erste Alphabet gelesen, da fange ich
hier am ersten an und Ausgabe ist es dann durch diese Funktion
definiert.
Allgemein, solange das sich mein Automaten nicht definiert, ich kann
es so einfach so stehen lassen.
Wenn ich das weiß, was für Zustand ist, da kann ich hier schreiben,
zum Beispiel Zustand J oder was auch immer.
Aber wenn ich das nicht weiß, dann lasse ich einfach so und das
bedeutet, dass hier ist es ein Zustand.
Und das ist hier eine Ausgabe.
Dann was mache ich dann?
Dann lese ich dann ein zweites Alphabet, Eingabealphabet.
Das heißt, E1 habe ich schon gelesen, da ist dann der nächste E2 dran.
Und E2 ist es so, das nächste Zustand ist es dann, dass ich diesen
Zustand nehme.
Das, was ich oben hatte.
Ich hatte schon E1 gelesen.
So, ich war in diesem Zustand, das können wir hier so schreiben, das
hatten wir schon.
So, mein neuer Zustand ist es hier.
Von hier, das ist jetziger Zustand.
Und dann hier, neuer Zustand wäre dann diese Überführungsfunktion von
dem, was ich hier als Zustand hatte und Eingabe 2.
Das nenne ich dann Delta-Stern.
Und hier das gleiche wie oben, so hier habe ich, das ist mein jetziger
Zustand und das ist E2 und das ist dann eine Gamma davon.
So, jetzt habe ich E2 gelesen, dann lese ich E3.
Danach E3 lese ich alle Worte, bis ich bis EK komme.
Und diese Delta-Stern sagt mir, dass ich dann diese
Überführungsfunktion auf ein Wort verwendet habe.
Das heißt, das ist nicht nur ein Eingabenalphabet, sondern es ist ein
Wort von diesen Alphabeten und ich lese eins nach dem anderen.
Gut, dann haben wir ein Beispiel Warenautomaten.
Das ist ein Warenautomat, der nur mit 4 Euro, so ein Schokoriegel für
4 Euro ausgibt.
Ist sehr teuer, finde ich, aber das ist ein Beispiel.
Das heißt, kommt eine richtige Ware raus, wenn wir 4 Euro da drin
haben.
Das ist vielleicht unrealistisch, aber das ist ein einfaches Beispiel,
dass Sie sehen, wie wir das implementieren.
So, Eingabealphabet.
So, diese Automaten, wissen Sie, wie das aussieht?
Wir werden sie irgendwo Münze werfen und da kommt irgendwann irgendwie
eine Ware aus.
So sieht das aus.
Daher gibt es auch Knopf.
Und die Eingaben, die Sie geben können, es ist erstmal 1 Euro Münze
werfen, 2 Euro Münze werfen, falsche oder ungültige Münze werfen.
Und Wahltaste, Sie können wählen, was für Ware, so Schokoriegel Sie
haben wollen.
Und dann haben wir eher Rückgabeknopf.
Das sind die Sachen, die Sie wirklich vorne haben, auch bei
Parktickets.
Sie haben nicht so viele Eingabenmöglichkeiten, vielleicht 5 Stück.
So, abbrechen, quitten und so und so.
Hier haben wir definiert, diese 1, 2, 3, 4, 5 Eingaben.
Dann Zustände haben wir auch einige.
Erstmal kein Geld eingeworfen, Zustand Null, das heißt wartet, bis wir
Geld einwerfen.
Das tut nichts, solange wir Geld nicht einwerfen.
Dann haben wir 1 Euro, 2 Euro, 3 Euro, 4 Euro eingeworfen.
Und dann kommt das Ü für Übertrag zu viel Geld eingeworfen.
Und Ausgabealphabet ist es erstmal G für Geldrückgabe, GF für falsche
Münze, WA für Warenausgabe und WÜ und so weiter.
So, Automaten sieht so aus.
Sehen Sie, das ist im Vergleich zu Mausefalle, sieht ein bisschen
komplizierter aus.
Aber ich kann da mindestens einmal das irgendwie veranschaulichen.
Es ist so, dass wenn wir, so wie gesagt, dieser Automat funktioniert
mit 4 Euro.
Das heißt, wenn wir 4 Euro tatsächlich drin haben, da soll eine Ware
ausgegeben werden.
Und das ist auch so, wenn wir eine Eingabe, so hier haben wir gesagt,
da hier sind Eingaben.
M1, M2, M11 und so weiter.
Und hier sind die Zustände.
Und wenn wir in Zustand 4 sind, Zustand 4 sagt, dass wir 4 Euro schon
drin haben.
Was passiert ist, dass dann, und wir sind in Warenausgaben, das haben
wir gewählt.
Dann gehen wir zu Zustand 0, das heißt, fangen wir von vorne an und
wir geben die Ware aus.
Okay, was passiert, wenn wir 1 Euro werfen und wir in Zustand 0 sind.
Zustand 0 hat uns gesagt, kein Geld eingeworfen.
Okay, wir haben jetzt aber 1 Euro geworfen.
Was passiert ist, wir wechseln unseren Zustand zum Zustand 1 Euro
drin.
Und Ausgabe haben wir noch nicht, weil mit 1 Euro können wir kein
Schokoriegel kaufen.
Wir mussten mit diesem Automaten mindestens 4 Euro haben.
Und das gleiche können wir mit diesem Zustanddiagramm zeigen.
Das ist zum Beispiel, wir bleiben so lange in Zustand 0, dass
mindestens ein Input kommt.
So, wenn wir Hutgabe oder Ware oder MF haben, diese Inputs haben, da
bleiben wir immer noch drin.
Solange, dass wir irgendeinen Input haben, dass wir dann unseren
Zustand wechseln können.
Dass wir dann zum Beispiel, wenn wir 1 Euro geworfen haben, da
wechseln wir zu Zustand 1 und so weiter.
Wenn wir 2 Euro werfen, dann wechseln wir zu Zustand 2.
Gut, ich werde jetzt mit der Vorlesung aufhören.
Vielen Dank für Ihre Aufmerksamkeit.
Nächste Woche wird Herr Schmeck dann die Vorlesung halten.