Grammatik & Automaten: Chomsky & Regularität

Aber kein gutes Vorzeichen. Also ich unterstelle jetzt mal, dass ihr einfach sehr, sehr schüchtern. Aber das auch nicht. Aber wenn eine Befürchtung stimmt und ihr wisst es an mich, dann ist das keine gute Vorbereitung. Wollen wir jetzt die Präsentaufgabe bearbeiten? Die erste Frage ist, wir sollen die Grammatiken widerstehen, sollen wir die Schaumsk-Hierarchie ein sortieren? Wir haben 45 Minuten, das heißt, im besten Fall kann ich da durchrasen. Wenn ihr dann also noch nicht wisst, was die einzelnen Stufen der Schoenskirarchie sind,

dann werdet ihr nicht verstehen, warum wir bei der einen sagen, dass das kontextfrei ist, bei der anderen nicht. Das wird da nicht gut funktionieren. Also die Vorbereitung, die Term, also ich schreibe die Begriffe, die da oben drauf stehen, die schreibe ich deswegen hin, damit ihr die vorher nochmal anschaut. Alles andere dann auch umherkommen, wenn man die Begriffe nicht drauf bringt. Das macht keinen Sinn. Das ist so, als würde man zu einem C1 Deutschkurs gehen und hat aber vorher...

wo man mal so jemand an ein Deutsch reden gehört. Also man hat schon mal auf der Straße jemand ein Deutsch reden gehört, also kann man ja nicht kennen die Sprache. Und jetzt geht man kürzlich in den C1-Kurs und will dort Deutsch reden. Das funktioniert nicht. Okay. Deswegen, es gibt ja keine Anwesenheitspflicht. Zwängt euch nicht hierher, wenn ihr danach am Ende rausgeht und enttäuscht seid. Oder noch besser, also ich will jetzt auch keine Werbung machen, dafür, dass es nicht kommt, aber noch besser.

Guckt euch abends nochmal kurz, zwischen zwei Folgen Netflix oder was auch mal ihr guckt. Guckt hier nochmal kurz auf die Folien und guckt hier auf den Gesetzabwehr. Was sollt ihr hier? Frikuläre Sprache, Schomsky, Rechie nochmal die Folien durchlesen. Und dann seid ihr vielleicht ein bisschen vorwärts. Das ist sozusagen das Minimum. Okay. Paya Zimmern.

Wenn man sich nicht vorbereitet, dann ist auch klar, dass man am Anfang keine Fragen macht. Typisch ist eigentlich, wenn man sich mit den Themen auseinandersetzt, die mit einer Vorlesung behandelt werden, dann ist eigentlich Fragen der Normalfall. Wenn ich also jetzt sage, gibt es irgendwelche Fragen, keine meldet sich, dann ist das für mich eine ganz große Red Flag, würde man heute sagen, die ausdrücken, die haben nichts gemacht. Das geht jetzt da auf jeden Fall. Diese Vorlesung hat jetzt gemütlich gestartet. Wir sind irgendwie...

dritten woche haben wir haben zwei wochen an vorlesungen gehabt aber die wird jetzt den nächsten tempo aufnehmen das wird ein riesiger begriffewerk ganz unten sind die formalen sprachen grammatiken und dann kommt ein begriff nach dem anderen oben drauf und irgendwann stehen auch so ein riesiges haus von begriffen man kann die sachen oben nur verstehen wenn man die sachen unten verstanden hat wenn ihr also jetzt verloren geht dann könnt ihr die vorlesung eines direkt nächste zeit verhoben ich verstehe seid ihr auch die wirtschaftsinformatik

Das ist ein Haupt- und Lehramt. Lehramt und Wirtschaft. Das ist nichts, außer dass ich weiß, dass die Ausbildung in solchen Null-Sprechern geteilt ist. Ihr müsst euch ja auch noch mit anderen Sachen beschäftigen. Das heißt, ihr kriegt nicht so eine starke Mathematikausbildung wie ein Bachelor-Informat. und ist bei euch reduziert.

Einfach weil auch Zeit für das andere Fach da ist. Das heißt, eure Vorbedingungen sind auch schon, also ihr habt sozusagen schon schlechtere Vorbedingungen. Die Folge sind für euch nochmal einen Tick anspruchsvoll. Im Schnitt. Ich will überhaupt nicht irgendwelche Vorurteile äußern oder so, sondern es ist einfach nur eine Erfahrung, dass Wirtschaftsinformatiker und Lehr-Arzt-Sidenzen diese Vorlesung eventuell ein bisschen schwerer machen könnte.

Ich will euch einfach nur davor bewahren, dass nächstes Jahr noch mal ausgesprochen wird. Mein Angriff ist, hier so viele Leute wie möglich durchzuführen. Aber, das heißt, ihr müsst die Angebote und die Tipps, die ich euch gebe, müsst ihr irgendwie umsetzen. Und das mit diesen Begriffen hier oben auf den Präsenzaufgaben ist neu. Ich überlege das Projekt mal aus. Dass ich explizit schreibe, diese Begriffe, wenn ihr die könnt, dann könnt ihr die Übung verstehen.

Und deswegen würde ich mich freuen, wenn ihr euch nicht noch am Abend davor oder morgens, ich weiß ja nicht, ob ihr was für den Typ schläfer ihr sollt. Und dann, je nachdem, wird die Drittredigzeitung noch zu. Okay, Moralprädigzeitung ist vorbei. Lasst uns in die bearbeitende Präsenzaufgabe gehen. Das wird jetzt wahrscheinlich auch ganz toll.

In der aktuellen Serie geht es darum, wir wollen noch einmal mit Grammatiken, also die werden uns das ganze Semester beschäftigen, aber wir wollen mit den verschiedenen Stufen der Choms-Tree-Hirarchie noch ein bisschen arbeiten, das ist die Aufgabe 1 und danach geht es darum, ein Gefühl für etliche Automaten zu bekommen. Das sind die anderen Aufgaben. Und dann ist der Kernpunkt, wenn wir den Punkt anschauen, ist das auch der richtige Teil. Deswegen lasst uns schnell durch Aufnahme 1 durchrasen.

Frage? So, was war das? Achso, genau, ja, dann machen wir das doch. Schauen wir uns doch mal Aufgabe 1i an. Was ist das für eine Grammatik?

Ich habe mich so ganz verstanden, sorry. Der Tipp ist kontextfrei. Schon mal ein sehr guter Tipp. Und die Begründung war: Auf der linken Seite sind nur nicht terminal. Schon mal wichtig. Und was war der zweite?

in the 10-year-old office.

Das ist verboten. Wir dürfen auf der rechten Seite nicht einfach nur ein einzelnes Nicht-Terminal haben. Das wäre bei regulären Grammatiken verboten. Und man sieht es auch an der unteren Regel. Auf der rechten Seite ist eine Folge von Terminal, Nicht-Terminal, Terminal. Und auch das ist bei regulären Grammatiken verboten. Das heißt, das ist eine kontextfreie Grammatik. So, fertig.

2 also 12 ja kann da ein tipp abgeben was für eine dramatik ist

in der Schomsky-Hierarchie bei dieser Grammatik? Die Schomsky-Hierarchie, die ist von oben enthalten. Alle Sprachen sind vom Typ 0. Die Frage ist, ist es Typ 1 oder ist es sogar Typ 2 oder ist es sogar Typ 3? Also alle Sprachen sind vom Typ 0. Alle kontextsensitiven Sprachen, also auch alles, was da drunter ist, auch alle regulären und alle Kontextkontrollen sind auch alle kontextsensitiven. Das ist eine enthaltene Sägensrelation nach unten.

Also jede kontextfreie Sprache ist regulär, aber nicht jede reguläre Sprache ist kontextfreie. So. Das heißt, es geht darum, wie weit runter können wir in der Hierarchie gehen. Ganz sicher ist es eine Typ Null Sprache. Das sind alle Sprachen von Typ Null. Also alle Grammatiken. Entschuldigung, ich bin selber für uns in der Kategorie. Alle Grammatiken sind vom Typ Null.

ist es vielleicht sogar mit 1 kontextsensitive. Ja? Richtig, die ist sogar kontextfrei. Warum? Weil wir auf der Seite mehr Kontinuierung haben, aber ganz wichtig.

Grund, warum es nicht regulär ist. Sehr schön. Also wir haben wieder den Kontext bei Grammatik. Eigentlich wollte ich eine reguläre Grammatik schreiben, habe ich auch nicht einen Taifung gemacht, der mir nicht aufgefallen ist. Eigentlich sollte hinter dem A noch ein Symbol stehen. Irgendwie ist das abhandengekommen. Also links in dem A. Die oberste Regel sagt, der S geht direkt nach A. Da sollte irgendwie 1A oder 0A oder sowas sollte das stehen. Und irgendwie ist das Terminal da abhandengekommen.

Wenn man mal an, da würde ein Terminal stehen, würde ich mit deiner Einschätzung dann ändern. Dann wäre es regulär. Regulär bedeutet, auf der linken Seite sind immer Nicht-Terminale, einzelne Nicht-Terminale. Und auf der rechten Seite, das hatte ich vorhin schon richtig gesagt, ist entweder das leere Wort, Entschuldigung, ein einzelnes Terminal oder eine Folge aus Terminal und Nicht-Terminal. Und das hätten wir. Wenn ich den Teil nicht gemacht hätte,

Dann wird's. Okay. Frage, wie ist das denn mit Optionen jetzt? Genau, weil die Spätigen vorgesungen nicht verkürzen, wenn man es nicht verkürzt hat, wenn man es immer zu kürzen. Na, wenn die Länge nicht klein wird. Also ich würde jetzt nicht mal nicht in der Mathe umschreiben, sondern die Wort verkürzt, wenn das das ist, was du meinst. Na zum Beispiel

Dann könnten wir eine Grammatik haben.

- Okay, I'm gonna...

eine Regel, wo mehr als nur ein Nicht-Terminal steht. Bestenfalls context-sensitive sein. Um jetzt die Frage zu beantworten, ob diese Grammatik context-sensitive ist, müssen wir uns fragen, sind denn alle Regeln nicht verkürzend? Dafür müssen wir uns die linke Seite und die rechte Seite der Länge anschauen. Hier haben wir ein Zeichen auf der linken Seite, zwei auf der rechten Seite. Das ist ja nicht verkürzend. Hier ähnlich.

Die letzte Regel, da ist auf der linken Seite ein Zeichen, das ist auch nicht verkürzend. Das ist zwar auch nicht verlängert, aber live ist ja auch nicht verkürzend. Aus einem Zeichen wird ein Zeichen, dadurch wird es nicht kürzer. Aber diese Regel hier, die hat auf der linken Seite zwei Zeichen und auf der rechten Seite nur ein Zeichen. Damit ist die rechte Seite kürzer als die linke Seite. Und damit ist diese Regel verkürzend. Bei ihr?

auch in der Ableitung. Wenn wir ein Wort daraus ableiten, dann kann es passieren, dass wir erst ein langes Wort haben und dann kriegen wir wieder ein kürzeres Wort. Und darum geht es eigentlich. Die Wörter, die man ableitet, die sollen, jeder Ableitungsschritt soll das Wort im schlimmsten Fall höchst gleich langen, idealerweise sogar verlängern. Das haben wir hier nicht. Wir könnten zum Beispiel Ableitung, S geht nach AA. Jetzt nehmen wir das erste Ableitung auch nach AA.

Und jetzt könnten wir die zweiten beiden A's in einem B ableiten. Jetzt kommt am Ende kein Wort raus. Obwohl, ich kann jetzt wieder A, A, B machen. Ich könnte dann daraus B, B machen. Und jetzt in zwei Schritten daraus 0, 0 machen. Das würde gehen. Das wäre eine Ableitung. Wer sind wir anleitenden?

haben wir mal Länge 2 mal Länge 3, aber nachdem wir Länge 3 hatten, kommen wir wieder auf Länge 2 zurück. Also die Länge nimmt zu und ab. Wir werden später lernen, dass das nicht gut ist. Also im Sinne von, das macht die Sache schwerer. Schwerer zu erkennen. Wenn die Länge auf und ab geht, dann während der Ableitung die Länge des Wortes mal mehr, mal weniger sein kann, dann wird es schwieriger. Ihr werdet sehen, solange die Länge immer zunimmt,

wenigstens noch herausfinden, ob das geht, ob ein Wort ableitbar ist. Das ist sehr, sehr schwierig, aber es ist zumindest prinzipiell möglich, solange die Länge bei der Ableitung monoton zunehmend ist. Nicht streng monoton, aber monoton zunehmend. Aber Epsilon ist dann eine Ausnahme? Oder wenn wir Epsilon einklicken, ist ja quasi kein Zeichen. Epsilon ist eine Ausnahme, ja. Ich glaube, das steht da auf den Folien nicht ganz korrekt. Ich habe aber bisher auch noch nicht die Energie gehabt.

nachzuprüfen. Ich muss noch mal genau gucken, ob die Epsilon-Regel überall gelaufen ist, bei Kontext-Sensitive oder nur aus dem Staatssymbol. Dann muss ich mich noch mal beschäftigen, weil ich will auch kein Lexikon. Das müsste dann auch noch mal nachlesen. Mein Gefühl sagt, es muss eine Ausnahme sein, die nur vom Staatssymbol aus. Aber das ist mein Gefühl jetzt. Also beim Lernen ist wichtig,

Die Grenzen sind keine Rorta, die Sachen einfach, ich bleibe da, sondern wir lernen mit Gefühl. Wir können nicht einfach was lesen, gefühllos oder überrieseln lassen, ohne dabei irgendwie teile zu nehmen emotional und dann glauben, dass wir das danach wiedergeben oder auch nur bestanden. Wir müssen uns dadurch quälen, wir müssen mit den Sachen arbeiten, um ein Gefühl dafür zu bekommen, erst dann fangen die Dinge an, von uns zu tun.

Ich habe ein starkes Gefühl, dass die Epsilon-Regel dort auf dem Flur hin etwas zu allgemein kommen wird. Aber es spielt auch erstmal keine Rolle. Und kontextsensitiv geht es erstmal nicht. So, da war noch eine Meldung. Ja, die zweite. Was steht denn auf der Folie?

Da steht glaube ich nur eins. Also, das ist so ein Lehrding. Also die regulären Grammatiken, wie wir sie hier definieren, das ist unser Spielfeld so, wie wir das definieren. Es gibt andere Lehrbücher, da werden die regulären Grammatiken anders definiert. Und deswegen warne ich immer davor, YouTube-Videos zu gucken, oder im schlimmsten Fall sogar Bücher zu gucken. Es gibt natürlich immer Literatur, die man lesen kann und alles so viel. Aber ich würde immer sagen, geht lieber zur Vorlesung, heilt euch an die Vorlesungsfolien, schreibt mit, was in der Vorlesung gesagt wird, heilt euch an die Übungen.

Und das, was dort gesagt wird, das ist die Wahrheit, auf die es in der Klausur nachher auch ankommt. Wenn man ein Buch liest, dort steht vielleicht eine andere Deklinition für reguläre Grammatik. Und aus Studierenden-Sicht ist das erstmal merkwürdig. Und warum sollte dann ein Buch reguläre Grammatik anders durchliegen? Das macht doch gar keinen Sinn, dann ist das ja gar nicht vergleichbar. Der Stoff, den wir hier in Rostock lernen, ist ein anderer Stoff, als den man vielleicht in Berkeley oder Berlin

in den Uniswerden oder in Hongkong. Das kommt erst mal merkwürdig vor. Wenn man nachher das Thema schon beherrscht, sieht man, ah, Moment mal, die Definitionen sind gleich. Das läuft auf das Gleiche hinaus. Die Definitionen sind zwar unterschiedlich, aber sie beschreiben das Gleiche. Die Semantik, die Bedeutung ist die Gleiche. Deswegen ist es okay, dass die einen das so machen, die anderen das so machen. Sie beschreiben trotzdem alle das gleiche Konzept, aber auch nicht.

aber das sieht man erst, wenn man schon ein bisschen Erfahrung hat. Und jetzt weiß ich es nicht, vielleicht hast du es irgendwo gesehen, es gibt Definitionen für reguläre Grammatik, wo die Regeln auch so sind, man hat ein Lichtterminal auf der linken Seite und auf der rechten Seite hat man eine Folge von Terminalen und dann ein einzelnes Lichtterminal am Ende. Das ist wahrscheinlich nicht so wie auf den Folien, die habe ich jetzt auch nicht im Kopf, Ich habe kein fotografisches Gericht.

das wäre also eine andere Definition, aber sie führt zu dem gleichen Begriff. Also kurze Antwort, meiner Meinung nach ist das nicht erlaubt, wenn man nach unseren Folien geht. Lange Antwort, das macht keinen Unterschied. Die Sprachen, die man damit beschreibt, sind die gleichen wie mit dem Regeln. Warum? Das wäre jetzt eine Sache, die man in der Vorlesung oder dann ab in Kürze hoffentlich in dem Homework-Klappen Ich habe es nicht mehr, ich habe es nicht mehr, ich habe es nicht mehr, ich habe es nicht mehr.

So, gehen wir in die dritte Grammatik. Da sehen wir, das sieht so ähnlich aus wie dort. Also ich habe mit Absicht bei der dritten Grammatik, ich habe selber regulär hingeschrieben, weil ich ganz fest meine Meinung war, dass ich da so ein Zeichen hingeschrieben habe. Das war offensichtlich ein Typo. Achso, die hatten wir einfach.

Also genau gesagt, habe ich die auch gerade kopiert von meinem Kollegen. Der hat hier offensichtlich eine andere Definition, das muss ich nochmal verarbeiten. Das gefällt mir tatsächlich. Also ich würde sagen, hier muss es jetzt. Aber voraussetzung ist es bei einem Reiz oder so. Das hier ist Quatsch. Dann war es gar nicht ich, der den Fehler gemacht hat. Gut zu wissen. Ja, ich bin, ich habe die...

jetzt die Aufgabe hier, die Übung zu begleiten, übernommen von meinem Kollegen, der letztes Jahr gegangen ist. Und ich habe einfach einen großen Satz von seinen Aufgaben übernommen und das ist offensichtlich einer von denen, die ich übernommen habe. So, schauen wir uns G3 an. Ja, und da sehen wir das, worüber wir gerade gesprochen haben. Außer, die ist nicht verkürzt. Wenn wir uns alle Regeln angucken, hier ein Symbol, das ist okay. Wie gesagt, die Epsilon-Regel habe ich da nicht.

Da entmich ich euch stand vorher, wo ich gesagt habe, also Sicherheit habe, schreibe ich die hier zum Startsymbol. Und dann sieht man, also hier darf es auf jeden Fall erlauben, dass man aus dem Startsymbol direkt das leere Wort ableiten kann. Da ist diese Sonderregel auf jeden Fall erlaubt. Ansonsten können wir alle Regeln durchgehen. Hier sind zwei Symbolen, drei ist okay, zwei, zwei ist okay, drei und drei. Ist zwar nicht verlängert, aber ist auch nicht verkürzt. Das ist okay. Im Zweifels auch nicht verkürzt, wunderbar. Also, das ist eine kontextsensitive Grammatik. Gut. So, das sind jetzt keine Fragen. So stehen jetzt schon mal die Erechnung.

Dann lasst uns zu den Autobahnen übergehen.

Da frage ich erstmal, was ist denn die Probeurte sind die Hut dieser Automaten? Oder vielleicht etwas von früher, was ist die akzeptierte Sprache eines retimulistischen, endlichen Automaten? Wie ist das definiert? Ja? Im Privatsphal, wenn wir mit so einem Nachmitteln, der regelt ab ist. Ja, das war eine Intuition, die ich gegeben habe. Was das so ist, das müssen wir erst mal beweisen, dann werdet ihr euch heute und morgen in der Vorlesung gestellt haben.

Machen wir das ganz, ganz genau. Wir werden sehen, jeder deterministische, endliche Automat beschreibt eine reguläre Sprache, weil ich aus dem Automaten eine reguläre Grammatik anleiten kann. In die andere Richtung ist das nicht so einfach. Aber auch das werden wir machen. Wir werden zeigen, jede reguläre Sprache hat auch einen deterministischen, endlichen Automaten, der sie akzeptiert. Aber es beantwortet nicht die Frage, was ist überhaupt die akzeptierte Schufaffung.

und detenierst es endlich auf den Kopf. Was meinen wir mit akzeptiertes Waffen?

- Thank you.

Fassen wir das mal zusammen. Die akzeptierte Sprache eines ähnlichen Automats ist die Menge aller Wörter, die von dem Automat akzeptiert werden. Fällt sich ein bisschen an wie eine Tautologie. Die Menge der Pollys ist die Menge aller Fälle, die an Pollys sind. Hört sich erstmal so an, aber wir wissen trotzdem mehr. Die Sprache, Menge von Wörtern ist schon mal gut. Und wir haben jetzt den Begriff, das muss vom Automaten akzeptiert werden. Was bedeutet denn akzeptiert? Wann akzeptieren ein Automaten?

Wenn es in einem akzeptierenden Zustand endet, also wie die im Doppelkreis sind. Ja, endet. Was meinst du mit endet? Was endet denn dort? Also das ist jetzt zum Beispiel auch in der Übungsaufgabe, da ist ja auch eine Steigung mit A und B, dass es quasi von diesem Zustand nicht mehr weggeht. Ja, aber was endet denn dort? Das Wort endet dort? Das Wort endet dort? Nein, das Wort endet im letzten Zeichen.

Wenn ich das Wort Hallo habe, ich habe von mir aus mal diesen ganz einfachen Automaten,

Wo endet das Wort? Hier. Das Wort Halt endet hier. Was soll das mit dem Automaten so tun? Nichts. Das ist ein Automat, das ist ein Wort. Das Wort endet hier. Das Wort endet nicht im Q1. Was endet im Q1?

Die Berechnung. Was war die Berechnung eines Automaten? Das ging, ne, auf dem Präsenzzettel stand vorne deterministische endliche Automaten. Da gehören natürlich die Begriffe dazu, die sowas wie die Berechnung. Das ist die Berechnung eines deterministischen endlichen Automaten. Was ist damit gemeint? Wenn wir geben dem Automaten ein Wort, zum Beispiel das Wort Hallo, Dann macht er eine Berechnung. Was ist die Berechnung?

ポリ。

Jetzt mal die Florentritte.

I'm sorry.

auf den Folien, wenn ich so doofen Fragen stelle. Ich stelle ja keine Fragen, die ihr nicht hypothetisch zumindest wissen könnt. Das wäre gemein. Ich versuche eigentlich nicht so gemein zu sein. Deswegen stelle ich immer nur Fragen, die man im Prinzip nachlesen kann. Es ist auch eine gute Idee, die neben den Präsenzaufgaben oder Hausaufgaben auf seinen Bildschirmen auch

irgendwo hinten den aktuellen Foliensatz offen zu haben, um mal schnell nachlesen zu können. Würde ich auch einmal empfehlen. Die Berechnung ist eine Zustandsfolge. Welche denn? Wie kriege ich die? Wie rechnet der Automat, wenn er das Wort Hallo bekommt? Wie rechnet der Automat? Das ist eine Melder? Ja. Wie rechnet der Automat? Also er liest ja ein Zeichen ein. Welches?

Fängt ja in der Mitte an, tut das eben einfach das L. Ja, das erste Zeichen vom Wort, das liest dann halt ein und wechselt dann abhängig davon, welches Zeichen das eben ist, seinen Zustand. Und das macht er dann halt die ganze Zeit. Genau, dann liest sich das erste Zeichen und je nachdem, in welchem Zustand er ist, sorgt das dafür, dass er einen bestimmten Zustandsübergang macht. Das hört sich sehr hofftrabend ein, heißt einfach nur, der geht in den anderen Zustand. Das kann auch der gleiche Zustand wieder sein, aber es ist trotzdem gehen, du hast das vor Schleife genannt.

Also man ist in dem Zustand, man geht los und landet wieder an der gleichen Stelle, ist trotzdem ein Zustandsübergehalt. Und dann nimmt man das nächste Zeichen. Man pflückt die Zeichen sozusagen von vorne ab und jedes Zeichen sorgt dafür, dass man einen Wechsel des Zustands macht. Und zwar abhängig davon, in welchem Zustand man nicht gerade ist. Das heißt, wenn man alle Zeichen abgepflückt hat, ist man auch in einem Zustand. Das ist der sogenannte Endzustand. Das ist das, was du meintest mit Enden. Man endet also nicht...

Nicht das Wort endet in einem Endzustand, sondern die Berechnung auf dem Wort endet in einem Endzustand. Dieser Zustand, der ist entweder akzeptieren oder nicht. Wenn er nicht akzeptieren ist, dann ist das Wort auch nicht akzeptiert. Dann kommt es in die Tonne. Wenn der Endzustand aber ein akzeptierender Zustand ist, dann kommt das Wort mit in die Menge der Wörter, die der automatisch akzeptiert. Also dann ist es ein Teil,

akzeptierten Sprachen. Wir sehen ja, Hallo ist so ein Wort. Wir sind in Q0, wir lesen H, gehen auf die Reise, landen wieder in Q0, wir lesen A, wir landen wieder in Q0, wir lesen L, unsere Reise führt uns weiter nach Q0, wir lesen nochmal L, und jetzt O, das letzte Zeichen, wir landen in dem Zustand Q1 und haben das Wort Hallo gelesen, das Wort ist zu Ende, die Berechnung ist auch zu Ende und

Wir sind in einem akzeptierenden Zustand, also das Wort Hallo wird akzeptiert. Okay, jetzt sollen wir das ein bisschen beamen und ein Gefühl dafür bekommen, was Automaten so für Sprachen akzeptieren können. Wir gucken uns mal hier diesen Automaten an. Das ist jetzt die zweite Aufgabe. Wir sollten uns also Gedanken darüber machen, welche Sprachen er akzeptiert. Wenn man rein systematisch vorgehen wollte, müsste man also alle und endlich vielen Bürger nehmen.

gucken, ob der Automat die akzeptiert oder nicht. Das wäre das systematische Vorgehen, das ist für uns Menschen aber unpraktikabel, da unser Leben endlich ist und wir es nicht schaffen, in unserer Lebenszeit alle unendlich vielen Wörter durchzugehen und so die akzeptierte Sprache herauszufinden. Deswegen muss man ein bisschen schlauer sein und typischerweise reicht ist, wenn man einfach ein paar Wörter nimmt. So 40, 50 Wörter und schaut die 40, 50 Wörter eigentlich auf den Automaten. Überlegen.

Und dann kriegt man ein ganz gutes Gefühl dafür, was dieser Automat eigentlich genau macht. Dafür haben wir jetzt in der Übung aber auch keine Zeit, deswegen werde ich ein bisschen zielgerichteter vorgehen. Und die Erkenntnisse, die man aus den Tests, den 40, 50 Tests bekommen kann, die werden wir jetzt einfach mal direkt sehen, diese Ablagerung. Also wir sehen, dass die Wörter sind über dem Alphabet B hier. Das heißt, unsere Sprache ist auch eine Sprache mit dem Alphabet A und B.

Wenn man jetzt experimentieren würde, dann würde man sehen, dass während man Buchstaben durch die Wörter durchgeht, dass wenn man immer mal ein B liest, solange man noch nicht in dem Endzustand war, landet man nach dem Lesen eines Bs immer wieder in dem Zustand Q0. Das ist eine Beobachtung, die man nach einer Weile machen würde. Also ich gehe das Wort durch, wenn ich in dem Endzustand lande, naja, okay, sobald wir im Endzustand sind, werden wir sehen, kommen wir auch nicht mehr raus.

wenn wir mal ein Board haben, das uns in den Endzustand führt, dann werden wir sehen, okay, jetzt kann eigentlich kommen, was will, auf dem Endzustand kommen wir nicht mehr raus. Das ist so ein ganz typisches Pattern bei endlichen Automaten. Solche Automaten, die am Endzustand hier so eine Is-wir-do-egal-Schleife haben, also danach wird einfach alles akzeptiert, die versuchen irgendwie eine Eigenschaft in dem Board zu finden und sobald die Eigenschaft festgestellt wurde, wird gesagt, okay, wir sind fertig und dann bleiben wir in diesem Zustand, in dem akzeptierenden Zustand.

da kommt man dann nicht mehr raus. So, wenn wir Wörter ausprobieren, die uns noch nicht in den Endzustand gebracht haben, während wir die Ausführung, werden wir merken, okay, solange ich Bs lese, bleibe ich hier vorne, selbst wenn ich mal ein A lese, wenn ich danach wieder ein B lese, bin ich immer wieder hier vorne. Also was bedeutet der erste Zustand? Bedeutet sowas wie, also Q1 meine ich, bedeutet sowas wie, ich habe gerade ein B gelesen. Das letzte Zeichen, was ich gelesen habe, war ein B. Was ist Q1? Q1 ist ein bisschen schwieriger zu verstehen, aber Q1 bedeutet, ich habe ein B genießen und danach ein A.

Also es gab irgendwie, oder sagen wir mal, ich habe etwas gelesen, das kein A war und dann habe ich ein A gelesen. Und das hat mich nach Q1 gemacht. Also es ist in Q1 unmöglich, dass ich zwei As hintereinander hatte oder fünf As oder so. Und Q1 bedeutet immer, die letzten Zeichen, die ich gelesen habe, das letzte Zeichen, das ich gelesen habe, waren A, aber davor war kein A. Was bedeutet Q1? Und das werde ich dann checken. Also nach 30, 40 Wörtern, glaube ich.

habe ich das gesehen. Da bin ich mir ziemlich sicher, dass ich hier wieder gesehen habe. Na ja, was heißt zu zwei? Na ja, die letzten beiden Zeichen, die ich in denen habe, waren A. Das ist ja genau das, was die Sprache ist, die dazu gehört. Die Sprache, die zu dem Automaten gehört ist, das sind die Menge aller Wörter über dem Alphabet AB, in denen das Wort zwei aufeinandervolle Ars enthält. Irgendwo in dem Wort kommen zwei aufeinandervolle Ars vor. Das ist der Automat. Solange wir auch anfangen, fangen wir an.

Solange wir in diesem Zustand Q0 sind, heißt das, das letzte Zeichen, das wir gesehen haben, war ein B. Solange wir noch nicht hier sind, heißt das, wir hatten in dem Wort auch nicht zwei aufeinanderfolgende A. Hier vorne heißt B, B, B. So, jetzt ist es dann A. Okay, jetzt wird es gefährlich. Sie müssen aufpassen. Unser Aufpasszustand, der zählt nämlich. Der hat gezählt. Wir haben ein A gesehen. Genau ein A. Davor war kein A, aber dann kam eins. Wenn jetzt wieder ein B kommt, naja, Fehlerler. Dann kommen wir zurück. Das ist das letzte Zeichen, wie ein B. Aber wenn jetzt ein A kommt, dann haben wir zwei aufeinanderfolgende A gesehen.

dann sind wir im Endzustand und das heißt, das Wort enthielt ja zwei As. Und wenn es jetzt das Wort irgendwie weitergeht, ist es uns ja egal. Das Wort enthielt zwei As. Das heißt, wir können aus dem Endzustand nicht verlust. Was wir an diesem Automaten lernen können, ist, Automaten können zählen. Die können zählen und sie können diese Zahl, diese zählen, speichern. Aber die einzige Form, mit der sie etwas merken können, mit dem sie etwas speichern können, ist in ihren Zuständen selber. Also der Zustand Q0

Das bedeutet, ich habe bisher kein A gesehen und das letzte Zeichen, was ich gesehen habe, war ein B. Das ist die Semantik von Q0. Damit speichert Q0 eine Information darüber, über das Wort, was es bisher gesehen hat. Das Wort, das bisher akzeptiert wurde. Wenn wir ein Wort nehmen und dieses Wort durchgehen, und wir sind während wir durchgehen mal im Zustand Q0. Wir sind am Anfang in den Zustand Q0, aber wir können immer wieder in den Zustand Q0 kommen. Die Bedeutung von dem Zustand Q0 ist, das Wort, das ich bisher gelesen habe, enthält nicht zwei aufeinanderfolgende As.

das letzte Zeichen von diesem Wort war kein A. Wenn dann ein A kommt, heißt, wir sind dann im Zustand Q1 und die Bedeutung von dem Zustand Q1 ist, das Wort, das ich bisher gelesen habe, enthält keine zwei A's, die aufeinander folgen, aber das letzte Zeichen war ein A und das Zeichen davor war kein A. Das ist die Information, die gespeichert wird, dadurch, dass wir in den Zustand Q1 sind. Okay, gucken wir uns mal diesen Automaten an, der ist furchtbar.

zu sehen was man macht. Da weiß ich ob 30, 40 Wörter reichen, dass man checkt was da eigentlich abläuft. Und wir haben hier die Zeit nicht. Genauer gesagt muss ich eigentlich gleich die Übung beenden. 11:15 Uhr die Vorlesung wird, aber ihr braucht nur 5 Minuten darüber. Ich werde ein paar Minuten überziehen, um euch noch ein paar Infos mitzugeben, wie er gehen will geht. Ich will kurz erklären, hier in diesem Automaten wird das Konzept von Speichern ein bisschen weiter gefahren. Und um zu erklären was hier passiert, gucken wir uns mal zuerst die Lösung an.

gehen wir mal jetzt einen Schritt weiter und dann sehen wir, dass dieser Automat akzeptiert, ist die Menge aller Wörter über den Alphabet AB, in dem die Anzahl der As, das ist das Hashtag, bedeutet Anzahl, also die Anzahl von A in dem Wort B und die Anzahl der Bs in dem Wort B, wenn man diese beiden Anzahlen durch 3 dividiert, das ist das Mod 3 hier, ergeben den gleichen Rest. Schwierig, ne? Oh Gott, erstmal da durchsteigen. Aber ein Beispiel, wenn das Wort zum Beispiel AABBB ist,

2 a's und dann 5 b's, das wäre so ein Wort, was dort reinkommt, weil die Anzahl der a's in dem Wort ist 2 und die Anzahl b's in dem Wort ist 5. Und wenn ich 2 durch 3 dividiere, bleibt ein Rest von 2. Wenn ich 5 durch 3 dividiere, bleibt auch ein Rest von 2. Das heißt, der Rest bei der Divisiung durch 3 ist der gleiche, nämlich 2. Das ist das, was diese Sprache hier darstellt. Jetzt gucken wir uns mal an, wie er das realisiert.

Wir sehen, der Automat hat neun Zustände, die aber mit Absicht, mit der Zeichnung, auch in dieser quadratischen Form, genau auf diese Weise dargestellt werden. Denn die einzelnen Zeilen sind dafür da, die Anzahl der As zu zählen. Aber nur Mono-Lud-3. Mono-Lud-3-Zählen heißt, ich fange bei 0 an. Wenn dann ein A kommt, bin ich bei 1. Wenn dann ein A kommt, bin ich bei 2. Aber wenn dann ein A kommt, bin ich nicht bei 3, sondern wieder bei 0. Und wir können ja mal die erste Spalte angucken, da sehen wir das. Das hier ist 0, dieser ist 0.

Das Zustand steht für Anzahl 0. Jetzt kommt ein A, dann komme ich in diese Zeile. Diese Zeile steht für Anzahl von A, es ist 1. Und egal von wo ich hier weitergehe, ich komme in die nächste Zeile. Mit A. Wie ich mit A weitergehe. Dann komme ich in die nächste Zeile und diese Zeile steht für A. Anzahl A ist gleich 2. So, wenn jetzt ein A kommt, dann zählen wir nicht 3, sondern wir zählen ja Modulo 3. Also wir zählen nur den Divisionsrest. Dann kommen wir wieder nach 0 zurück. Das A führt uns in jedem Schritt wieder nach 0 zurück.

Das heißt, die erste Zeile besteht für den Divisionsrest, die Anzahl der As. Wenn ich die durch 3 integriere, ist der Rest 0, hier ist der Rest 1 und hier ist der Rest 2. Wir müssen aber auch die Bs gleichzeitig zählen. Dafür haben wir die Spalte. Die erste Spalte steht für die Division der Bs. Die Anzahl der Bs ergibt einen Rest von 0, die erste Spalte Rest von 1 und die dritte Spalte Rest von 2. Und wenn ich dann hier will, komme ich wieder in die erste Spalte zu.

So führt uns das Lesen von A und Bs, ein Lesen von A lässt uns in der gleichen Spalte, führt uns aber eine Zeile weiter nach unten und ein Lesen von B lässt uns in der gleichen Zeile, führt uns aber in der Spalte ein Spalte nach rechts. Durch die Wörter, die die Anzahl der A und die Anzahl der B bei der Division wird fallen, weil wir rechts hinterlassen, die finden wir auf der Diagonalen, deswegen sind das die Achse drin. Die Verletzungen sind in ihrer eigenen Köln.

Jetzt fehlt einfach die Zeit. Tut mir leid, aber hättet ihr ja mal schnell den Register besorgen müssen. Jetzt geht es in Aufgabe 3 darum, selber das Gefühl, dass wir jetzt für Automaten und was die Zustände zählen und so weiter, da haben wir jetzt ein bisschen Gefühl, jetzt sollten wir mal selber Automaten entwerfen und da geht es um folgende Sprache. Wir sollen für diese Sprache hier ein Automaten entwerfen. Na ja, wir wollen alle Wörter über Sigma Sternen. Sigma ist jetzt nicht A und B, sondern 0 und 1.

das W nicht auf 0,0 endet. Das ist so ähnlich wie das enthält A, A. Bevor wir über akzeptierende Zustände oder sowas nachdenken, müssen wir überlegen bei dem Entwurf, und ich würde hier gerne auf dem Kapier machen, aber es dauert zu lange, deswegen zeige ich euch gleich den Automaten, aber wir müssen irgendwie dieses Zählen realisieren. So ähnlich wie eben, da hatte ich ja gesagt, naja, das letzte war ein W und dann hatten wir ein A, aber davor kein A. Und sowas ähnliches müssen wir jetzt auch realisieren und das müssen Jetzt müssen wir den Zustände packen und ich zeige mal den Automaten hier.

Wir brauchen wieder einen Zustand, der so etwas sagt wie: "Das letzte war keine Null." Das letzte, das ich gesehen habe, war keine Null. Das ist der Zustand von Null. Solange wir 1 sehen, bleibt das ja auch wichtig. Solange wir 1 sehen, ist es okay, wir haben das Letzte, keine Null. Wenn wir dann aber mal eine Null sehen, dann brauchen wir einen Zustand, der sagt: "Das letzte, was ich gesehen habe, war eine Null, aber davor war keine Null."

was ist das, was der Zustand Q1 realisiert? Der Zustand Q1 sagt, okay, ich habe als letztes eine Null gezählt, aber davor war keine, das war die erste Null, die aufgetreten ist. Und wenn dann eine 1 kommt, dann sind wir direkt wieder zurück. Fehle an, diese Null, die führt uns wieder in den Zustand zurück, der davor. Aber wenn wir dann eine Null sehen, das heißt, wenn wir von hier nach hier gehen, heißt das, wir haben gerade zwei Nullen gesehen. Wir brauchen also einen neuen Zustand, der sagt, das letzte, was ich gesehen habe, waren wenigstens zwei Apeinanderträubende Nullen. Das waren davor noch mehr Nullen, das ist mir egal, aber die letzten beiden Zeichen waren nur Nullen. Dafür steht der Zustand Q2.

Wenn wir den Punktzustand Q2 auch noch eine Null sehen, dann waren die letzten beiden Zeichen ja auch eine Null. Sicherlich davor ist noch eine, aber noch beliebig viele. Aber insbesondere die letzten beiden sind dann auch wieder eine Null. Aber sobald ich eine 1 sehe, ist das 4-Grade wieder zu Ende. Und das letzte Zeichen, das ich gesehen habe, war eine 1. Und wir gehen direkt wieder in den Zustand, der sagt, das letzte Zeichen war keine Null. Also hier ist die Anzahl der letzten Nullen war 0,0 am Ende, eine Null am Ende, mindestens zwei Nullen am Ende. Was sind die Bedeutungen dieser drei Zustände?

Mit dieser Bedeutung können wir jetzt den Automaten fertig machen, indem wir die richtigen Zustände zu Endzuständen machen. Wir wollen ja gerade, dass am Ende des Wortes keine zwei Nullen stehen. Das heißt, der Zustand U2 darf kein Endzustand sein. Der sagt ja, am Ende waren zwei Nullen, mindestens. Ich weiß noch mehr davor, aber die letzten beiden Zeichen waren nur Nullen. Das ist gerade das, was wir nicht akzeptieren wollen. Also kein akzeptierender Endzustand. Und der ist aber akzeptierend.

Der sagte nur, am Ende war eine Null, aber davor war keine Null. Und der sagt, am Ende waren gar keine Null. Das heißt, die beiden nicht so. Okay. Gehen wir nochmal die Sprache aus. Die zweite Sprache. Das haben wir schon gesehen. Die Anzahl der Nullen und die Anzahl der Einsen soll bei der Divisie durch drei Nr. der erste hinterlassen. Da habe ich einfach mal gedacht, wenn ihr das eine gelöst habt, könnt ihr das auch. Das heißt, wir können da direkt den Automaten nehmen, den wir schon gesehen haben. Nur wir müssen A durch eins, der durch null und B durch eins.

So wird der letzte Automat und damit bin ich auch durch. Da wollen wir einen Automaten bauen, der die Sprache akzeptiert U1V1W, wobei U-Formen beliebige Wörter sein können. Naja, das ist die Sprache, die sagt, das Wort enthält mindestens zwei Einsen. Wir müssen also wieder zählen, brauchen wieder einen Automaten, der zählt. Wir brauchen einen Automaten mit einem Zustand. Der erste Zustand sagt, bisher habe ich gar keine Eins gesehen. Die Anzahl der Einsen bisher war Null. Der sagt, die Anteil der Einflüge, die ich hergesehen habe, war 1.

Der sagt, die Anzahl der Einsen, die ich bisher gesehen habe, ist auch mindestens 2. So, ja, und dann muss man noch ein Teil entsprechen. Wie wir hier 0 sehen, haben wir weiter die 1 gesehen. Sobald keine 1 sehen, sind wir im D-Zustand. Die 0 führen hier auch nicht raus, aber die 1 führt dann im D-Zustand. Das sind ja die Pattern. Sobald die hier in den End-Siequenz sind, heißt das, wir haben zwei 1 gesehen. Das ist 2 und 3. Schönes Bild. Gut. Damit bin ich ruhig.