So, einen schönen guten Morgen.
Dann geht es mit der Übung los.
Die Übung heißt Berechenbarkeit.
Letztes Mal hieß es Turing-Maschinen.
Da habe ich vom Aufbau und Arbeitsweise von einer Turing-Maschine
geredet.
Die hat Zustände, die hat ein Band.
Man kann die Funktionsweise der Turing-Maschine mit einer
Zustandsüberführungsfunktion definieren.
Dann haben wir uns überlegt, wie arbeitet so und so.
Dann haben wir ein Dekrame-Zustand.
Der Kopf steht da, dann bewegt er sich nach rechts usw.
Das alles im Detail analysiert.
Hier machen wir einen Schritt zurück.
Hier geht es nicht mehr um die Details bei den Turing-Maschinen.
Sondern es ist eine globale Sicht.
Ich habe die Turing-Maschine als Rechner-Modell.
Das ist ein vernünftiges Modell, das ich verwende.
Dann frage ich mich, welche Probleme kann ich damit lösen?
Welche Funktionen kann ich damit berechnen?
Gibt es Funktionen, die ich damit nicht berechnen kann?
Wenn ich die Definition ein bisschen herumspiele, wenn die Definition
etwas anders ist bei der Turing-Maschine, sagen wir mal, das Band ist
nur an einer Seite unendlich, an der anderen Seite hört es auf, sind
die Antworten auf diese Fragen immer noch die gleichen?
Oder nicht?
Da kann man sich das alles überlegen.
Und das Gebiet, das sich mit diesen Fragen umfasst, das heißt
Berechenbarkeitstheorie.
Daher der Name.
Wir brauchen etwas Vokabular.
Letztes Mal hatte ich schon fast eine Nebenbemerkung.
Eine Turing-Maschine akzeptiert eine Sprache, genauso wie bei
ähnlichen Akzeptoren.
Wenn sie mit der Verarbeitung von einem solchen Eingabewort zum Ende
kommt und in einem akzeptierenden Zustand anhält, dann wird sie
akzeptieren.
Dann definiert sie automatisch eine Menge von Wörtern, das ist eine
Sprache.
Und diese Menge, es gibt nur eine Bedingung, die für die Wörter in
dieser Sprache gelten soll.
Für die Wörter, die nicht in der Sprache sind, da gibt es zwei
Möglichkeiten, nicht wie bei ähnlichen Akzeptoren.
Es gibt zwei Möglichkeiten, entweder die Turing-Maschine hält nicht
an, oder sie hält an und akzeptiert nicht.
Bei den ähnlichen Akzeptoren haben wir nur diese zweite Möglichkeit.
Der ähnliche Akzeptor hält immer an, der wird aber nicht akzeptieren,
wenn ein Wort nicht in seiner Sprache liegt.
Deswegen ist das Ganze ein bisschen komplexer.
Deswegen hat man zusätzliche Begriffe.
Wenn die Sprache so ist, dass ich eine Turing-Maschine habe, die diese
Sprache akzeptiert,
dann heißt diese Sprache aufzählbar.
Das heißt, diese Turing-Maschine wird die Wörter dieser Sprache
akzeptieren, deswegen heißt diese Turing-Maschine ein Akzeptor.
Das ist ein vernünftiger Name dafür.
Und zusätzlich, wenn die Turing-Maschine, das ist eine Bedingung für
die Wörter, die nicht in der Sprache sind, wenn es so ist, dass die
Turing -Maschine auch für diese Wörter anhält und dann nicht
akzeptiert, dann heißt diese Turing-Maschine sogar ein Entscheider.
Das ist ein stärkerer Begriff.
Und dann heißt die Sprache dann entscheidbar, weil ich dann sie
entscheiden kann.
Und Sie haben ja in der Vorlesung gesehen, es gibt Sprachen, die man
nicht entscheiden kann.
Es gibt Probleme, die man nicht lösen kann.
Und es gibt viele davon.
Und in einer bestimmten Hinsicht sind das die meisten Probleme.
Ich lasse das nicht so formal stehen, weil es kommt mehr jetzt.
Das sehen Sie später, wenn Sie zum Beispiel theoretische Grundlagen
der Informatik hören.
Bachelor Informatik drittes Semester, dann werden Sie mehr davon
erzählt bekommen.
Deswegen mache ich jetzt nur eine Folge von Bemerkungen, die
interessant sind.
Und wenn Sie jetzt tiefer gehen möchten, beziehungsweise gehen werden,
dann in dieser Vorlesung, TGI oder ähnliche Vorlesungen.
Ja.
Die erste Bemerkung ist jetzt zum Beweis von der Unentscheidbarkeit
des Halteproblems.
Das macht man mit einer Beweistechnik, die jetzt nicht nur für
Unentscheidbarkeit von Sprachen damit zu tun hat.
Das nennt man Diagonalisierung.
Das hat Cantor schon im 19.
Jahrhundert, glaube ich, mal gemacht.
Und jetzt hier ein anderes Beispiel, für was man jetzt mit
Diagonalisierung zeigen kann.
Und ich habe eine Menge M.
Das darf auch unendlich sein.
Und ich habe eine Art Bildung, die jetzt von M zu der Potenzmenge von
M, mit diesem Definitions- und Zielbereich arbeitet.
Und dann kann ich zeigen, egal wie dieses F aussieht, egal wie diese M
aussieht, das hängt jetzt nicht von den Elementen, die neben sind,
oder von dem F ab, das F darf nicht so etikt sein.
Wie kann ich das zeigen?
Man muss sich zuerst ein geschicktes Element aus der Potenzmenge von M
aussuchen.
Das ist nämlich diese Menge Q.
Das sind dann alle Elemente aus M, also die müssen Elemente aus M
sein, weil das Q ist in der Potenzmenge von M, deswegen rede ich jetzt
über Elemente in M.
Und das enthält dann eben alle Elementen, die nicht in der Menge sind,
die diese Elemente abbilden.
Also das F von X, das X wird auch von der Menge abgebildet, das F von
X heißt.
Und wenn dieses X nicht in dieser Menge ist, dann ist es in meiner
Menge Q.
Dann kann man sich überlegen, ich habe ein Element X, wird das in
dieser Q nicht sein?
Dann gibt es zwei Fälle, es gibt nur zwei Möglichkeiten.
Und wenn das X in dem Q liegt, dann darf das F von X nicht in dem F
von X liegen.
Das heißt, es liegt in der einen Menge und liegt nicht in der anderen.
Die zwei Mengen dürfen jetzt nicht gleich sein.
Das F von X darf nicht gleich dem Q sein.
Und andersherum, wenn das X nicht in Q liegt, dann verletzt es diese
Bedingung, X ist nicht in F von X.
Das heißt, es muss X in F von X gelten.
Und ich habe immer noch die gleiche Situation,
für jedes X aus M, wird das F von X nicht gleich dem Q sein.
Das heißt, diese Abbildung kann nicht so etiv sein.
Und wo ist die Diagonalisierung jetzt?
Man kann zum Beispiel eine Tabelle zeichnen,
wo ich in den Zeilen und Spalten dann die Elemente aus M habe.
Und dann in den Einträgen habe ich, ob das X, das zur Zeile gehört,
dann in der Menge von M, also dem F von dem Element liegt, wo das zur
Spalte gehört, dann habe ich Einträge 1 und 0 da.
Also ja oder nein, liegt es in der Menge oder nicht.
Wenn ich eine Diagonale sehe und alles umdrehe, dann komme ich zu
diesem Q.
Das ist, wie man zu diesem Q kommt, da benutze ich die
Diagonalisierung sozusagen.
Das ist eine Nebenbemerkung.
Was auch interessant ist, zurück zu Turing-Maschinen.
Eine ganz wichtige Idee, die man jetzt in Fragen zur Berechenbarkeit
braucht, ist die Simulation.
Wir brauchen zuerst eine Voraussetzung.
Wir müssen die Turing-Maschinen irgendwie kodieren.
Ich habe eine Turing-Maschine, das ist irgendwas, ein Objekt.
Und wenn eine Turing-Maschine mit einer anderen Turing-Maschine
arbeiten soll, dann soll diese Maschine irgendwie repräsentiert sein.
Deswegen muss das Ganze kodiert sein.
Und man kann das sogar definieren, dass das Ganze sehr schön ist, dass
ich die ganzen Zustände und die ganze Überführungsfunktion kodiert
habe.
Das haben Sie auch in der Vorlesung gesehen.
Und das Wesentliche, warum das überhaupt gehen kann, ist, dass es ein
ähnliches Objekt ist.
Ähnlich viele Zustände, ähnlich viele Bandsymbole und so weiter.
Das kann man alles ähnlich beschreiben.
Und wenn ich das jetzt habe, eine Kodierung für die Turing-Maschine T
sozusagen, dann kann ich mit einer anderen Turing-Maschine darauf
arbeiten und ich kann es besonders mit der Turing-Maschine simulieren.
Ich kann von einer Anfangskonfiguration aus, dann lese ich in der
Kodierung, was der nächste Zustand sein wird, wenn es eins gibt.
Dann kann ich diese Konfiguration dann aktualisieren, dann habe ich
eine nächste Konfiguration, dann lese ich weiter in der Kodierung, was
soll denn jetzt geschehen, wenn der Kopf in der Position ist und so
weiter.
Dann kann ich das alles machen.
Und sogar weiter, ich kann eine abstrakte Maschine haben, die eine
beliebige Kodierung für eine Turing-Maschine bekommt.
Und dann diese Turing-Maschine auf eine beliebige Eingabe simuliert.
Dann nennt man das universelle Turing-Maschine.
Weil ich brauche jetzt nicht eine bestimmte Turing-Maschine zu kennen,
ich bekomme beides als Eingabe.
Turing-Maschine bekomme ich als Eingabe.
Ja, dann hat man das alles.
Dann darf ich von der ersten, vielleicht der ersten interessante
Bemerkung erzählen.
Warum heißen diese Wörter, diese Sprachen aufzählbar?
Warum heißt es nicht akzeptierbar oder etwas ganz Einfaches?
Na ja, weil es auch den Begriff von einem Aufzähler gibt.
Das ist sozusagen eine Turing-Maschine, die in einem Drucker
angeschlossen ist.
Und diese Turing-Maschine kann so lange, wie sie wollt.
Man muss nicht anhalten.
Und als sie arbeitet, dann spuckt sie immer wieder und wieder manche
Wörter aus.
Das wird dann gegebenenfalls eine unendliche Liste von Wörtern sein.
Weil ich nicht die Bedingung habe, dass der Aufzähler anhalten muss.
Und die müssen auch nicht
in willkürlichen Bereichen vorkommen.
Ist das Ganze erlaubt.
Und ich kann zeigen, dass das äquivalent dazu ist, zu dem Konzept von
einer Turing-Maschine.
Von dieser Definition zur Aufzählbarkeit.
Es gibt eine Turing-Maschine, die diese Sprache akzeptiert.
Na ja, wie kann man das zeigen?
Dann kann ich immer für meine Turing-Maschine diesen Aufzähler
simulieren.
Auf meinen Angabenfort.
Entweder der Aufzähler wird irgendwann dieses Wort ausdrücken, dann
akzeptiere ich.
Oder dieses Wort wird nie ausgedrückt.
Das heißt, es liegt nicht in der Sprache.
Dann darf ich weiter und weiter berechnen.
Ich muss nichts machen.
Umgekehrt, ich habe dann eine Turing-Maschine,
will ich jetzt diese Sprache aufzählen.
Gegebenenfalls ist sie unendlich.
Und ich habe unendlich viele Eingabewörter.
Deswegen muss ich das Ganze geschickt machen.
Ich fange mit dem ersten Eingabenwort.
Und dann die Turing-Maschine wird vielleicht dieses Wort gar nicht
akzeptieren.
Und darf unendlich laufen.
Ich merke das gar nicht, weil das Problem unentscheidbar ist.
Da muss ich aufpassen, dass ich meine Berechnung auf die ganzen
Eingabewörter verteile.
Das kann man z.B.
so machen.
Ich habe diese ganzen Eingaben als unendliche Liste.
Und ich habe Schritte für die Turing-Maschine, die ich simuliere.
Ich mache mehrere Durchgänge.
Ich gehe mehrere Runden durch.
Und in der 1.
Runde mache ich einen Schritt bei den ersten Eingaben.
Bei der 1.
Runde mache ich einen Schritt bei der 1.
Eingabe.
Bei der 2.
Runde mache ich einen Simulationsschritt bei der 2.
und bei der 1.
Eingabe.
Dann habe ich diese ganzen Diagonalen da.
Das sind die Durchgänge bei den Runden.
Und wenn ich es so mache, dann wird es so sein, dass wenn die Turing
-Maschine vielleicht da und da akzeptiert, in diesen markierten
Stellen, dann kann ich diese Wörter ausdrucken.
Ich bin der Aufzähler.
Ich muss diese Dinge ausdrucken.
Und ich bin mir jetzt sicher, dass wenn die Turing-Maschine anhält,
dann wird es eine Zahl geben, sodass ich in dieser Runde
dann anfasse, wo die Turing-Maschine anhält und akzeptiert.
Wenn die, sagen wir mal zum B, da eine Inhaltsscheife ist, dann werde
ich das so nennlich mal aktualisieren.
Aber ich habe auch andere Eingaben.
Ich muss nur dafür sorgen, dass die Eingaben, die akzeptiert werden,
dann auch ausgedruckt werden.
Für die anderen muss nichts passieren.
Aber wenn die Eingabe akzeptiert ist, dann wird das auch von diesem
Aufzähler irgendwann mal gefunden und dann ausgedruckt.
Das war, was ich machen sollte.
Dann habe ich bis jetzt immer so geredet, Turing-Maschinen sind
komplexer als ähnliche Akzeptoren usw.
Man müsste sich noch die Frage stellen, können die Turing-Maschinen
alles, was die ähnlichen Akzeptoren können?
Das heißt, gibt es dann für einen ähnlichen Akzeptor auch eine Turing
-Maschine, die dieselbe Sprache akzeptiert wie der ähnliche Akzeptor?
Und das gibt es tatsächlich.
Und es gibt sogar eine Turing-Maschine, die immer anhält.
Und das Ganze ist ganz einfach, weil ich darf jetzt die Zustände von
dem A wieder nehmen.
Also in einem gewissen Sinne simuliere ich diesen Akzeptor.
Ich habe diese gleichen Zustände, ich darf sogar die gleichen Zustände
von der Turing-Maschine nehmen.
Weil ich eine Turing-Maschine bin, muss ich sagen, was in dem Band
geschrieben wird und wie der Kopf sich bewegt.
Der Kopf bewegt sich immer einen Schritt nach rechts, wenn ich ein
Eingabesymbol lese.
Und dann ist das so wie unten.
Das ist einfach ein Zeichen nach dem anderen gelesen.
Genauso wie bei ähnlichen Akzeptoren.
Ich bin in einem Blank gelandet und dann halte ich an, weil kein
Zustandsübergang dafür definiert ist.
Und in diesem Fall werde ich akzeptieren, weil ich in einem
akzeptierenden Zustand bin.
Das ist eben was passiert.
Und hier ist es auch interessant, weil ich das Band fast gar nicht
gebraucht habe.
Ich habe nur die Symbole da gelesen.
Ich musste gar nicht schreiben.
Ich habe gar keinen Speicher gebraucht.
Das kann man auch zeigen, dass jede Sprache, die regulär ist, also von
einem ähnlichen Akzeptor akzeptiert wird, dann auch von einer Turing
-Maschine entscheidet werden kann, wie hier.
Und die verbraucht gar keinen Speicher.
Das ist genau das.
Dann immer noch im Kontext von ähnlichen Akzeptoren habe ich in der
Übung letztes Mal zu Akzeptoren dann eine Konstruktion gezeigt, wenn
man jetzt auch die Sprache...
ich habe einen Akzeptor A, der entscheidet eine Sprache L von A, dann
darf ich auch einen Akzeptor A zu dem Komplement von dieser Sprache
haben.
Indem ich einfach die Zustände, die akzeptierend sind, umkehre.
Also jeder akzeptierende Zustand wird nicht akzeptierend sein.
Und jeder Zustand, der nicht akzeptierend war, wird akzeptieren.
Dann habe ich automatisch so einen ähnlichen Akzeptor für das
Komplement.
Und jetzt darf man sich fragen, ist bei Turing-Maschinen das Gleiche
ähnlich?
Ja, das ist das Gleiche.
Aber ich werde nicht immer glücklich, weil dieses A muss jetzt nicht
für die Eingabe anhalten.
Wenn das A jetzt in eine Endlosschleife gerät, dann wird mein B auch
nie anhalten.
Es wird auch nie dieses Wort akzeptieren.
Obwohl ich das akzeptieren wollte.
Das A akzeptiert das nicht, deswegen wollte ich das akzeptieren.
Das heißt, das Ganze gilt nur, wenn ich jetzt annehme, dass das A
immer anhält.
Wenn die Sprache entscheidbar ist, zum Beispiel, und das A ein
Entscheider ist, dann wird das gelten.
Und das ist ganz schön.
Man kann aber zeigen, dass das Komplement von einer aufzählbaren
Sprache nicht immer auch aufzählbar ist.
Es gibt Sprachen, zum Beispiel das Halteproblem, wobei das Komplement
gar nicht aufzählbar ist.
Das Halteproblem ist aufzählbar, aber nicht entscheidbar.
Das Komplement dazu ist etwas noch Schlimmeres.
Und das ist eigentlich ganz interessant, wie man das zeigt.
Ich kann das ganz allgemein vorführen.
Wenn ich eine entscheidbare Sprache habe, dann wird es genau der Fall
sein, dass die entscheidbar ist, wenn ich jetzt Aufzähler für die
Sprache und ihr Komplement finde.
Wie geht das?
Wenn ich eine entscheidbare Sprache habe, dann habe ich einen
Entscheider.
Dann muss ich jetzt Aufzähler für diese Sprache und für das Komplement
finden.
Für die Sprache selber kann ich den gleichen Entscheider nehmen.
Der wird nur anhalten.
Er wird nicht in der Sprache liegen.
Für das Komplement wird der Entscheider immer halten.
Dann darf ich diese Konstruktion von vorher, die akzeptierende
Zustände, umtauschen.
Dann werde ich das Komplement akzeptieren.
Und umgekehrt, wenn ich solche Akzeptoren habe, für das Komplement von
L, dann darf ich die jetzt parallel simulieren.
Also einen Schritt hier und einen Schritt da.
Immer abwechseln.
Dann ist es garantiert, dass eines davon anhalten wird.
Jedes Wort muss entweder in L oder im Komplement von L sein.
Jedes Akzeptieren muss anhalten.
Dann darf ich sagen, das liegt in L oder das liegt nicht in L.
Dann habe ich einen Entscheider dafür.
Und wenn man weiß, das Halteproblem ist aufzählbar und nicht
entscheidbar, das heißt, es muss dann das Komplement von dem
Halteproblem gewesen sein, das nicht aufzählbar ist.
Eine andere Möglichkeit gibt es eben da nicht.
Dann ist es das mit der Zeit.
Ich höre jetzt auf.
Es gibt noch eine weitere Bemerkung am Ende, aber das ist auch nicht
so ganz wichtig.
Vielen Dank für die Aufmerksamkeit und schöne Vorlesung.
Schönen guten Tag.
Wir sind im vorletzten Kapitel und das werden wir heute auch bestimmt
fertig kriegen.
Es geht aktuell jetzt hier um sogenannte reguläre Ausdrücke.
Generell der Plan ist, hier in diesem Kapitel noch mal ein bisschen
ein Gefühl dafür zu kriegen, was können ämtliche Akzeptoren, welche
formalen Sprachen kann man damit beschreiben.
Und eine Möglichkeit sind eben reguläre Ausdrücke.
Das ist etwas, das wird Ihnen noch ganz oft über den Weg laufen, in
etwas verallgemeinerter etwas bequemer zu benutzenden Notationen als
sogenannte Regular Expressions.
Wir beschränken uns hier auf den ganz einfachen Fall.
Also was darf man bei regulären Ausdrücken hinschreiben?
Erstens so einzelne Symbole aus dem Alphabet, das einen eigentlich
interessiert.
Und dann darf man zwischen reguläre Ausdrücke so einen senkrechten
Strich machen oder was heißt Bedeutung?
Jeder reguläre Ausdruck beschreibt eine formale Sprache.
Also wenn R der reguläre Ausdruck ist, R in spitzen Klammern ist die
beschriebene formale Sprache.
Und wenn Sie was haben mit dem senkrechten Strich, dann bedeutet das
Vereinigung der Sprachen, die durch die Teile links und rechts davon
beschrieben werden.
Und ein A bedeutet die formale Sprache, die das Wort A enthält und
analog für B und so.
Also A senkrecht, der Strich B,
wie Sie so sehen wollen, A und B.
Und man darf auch, wenn man einen regulären Ausdruck hat, noch einen
Stern dahinter machen.
Und das bedeutet dann Konkatenationsabschluss, so wie wir das kennen.
Also beliebig viele Faktoren, auch 0 ist erlaubt, 0, 1, 2, 3, viele
Faktoren.
Und jeder stammt aus dem, was vor dem Stern steht.
Und also sowas wie A senkrechter Strich B Stern, das ist dann einfach
die Menge aller Wörter, mehr oder weniger offensichtlich aus A´s und
B´s.
Das hier ist auch ein regulärer Ausdruck, A Stern, B Stern, das Ganze
in Klammern und da ein Stern dran.
Und da haben wir das letzte Mal so ein bisschen drüber nachgedacht.
Ach ja, das beschreibt ja die gleiche Menge von Wörtern.
Also das sind auch alle.
Also so wie Sie das gleiche Problem mit unterschiedlichen Programmen,
unterschiedlichen Algorithmen lösen können, können Sie halt auch zum
Beispiel die gleiche formale Sprache mit regulären Ausdrücken
beschreiben.
Und dann stellt sich sozusagen für einen Informatiker gleich die
Frage, ja, also jetzt in dem einen Beispiel mit scharfem Hinsehen
haben wir gemerkt, ach, die beiden regulären Ausdrücke beschreiben ja
das Gleiche.
Wie ist das denn im Allgemeinen?
Kann man das immer rauskriegen?
Und zwar im Zweifelsfall lieber automatisch per Algorithmus
rauskriegen lassen, statt selber lange nachzudenken.
Das ist die eine Frage und die andere ist, okay, welche formalen
Sprachen kann man denn durch reguläre Ausdrücke beschreiben?
Zu der Frage der Äquivalenz.
Die Lage ist besser als bei Turing-Maschinen oder Java-Algorithmen, da
können Sie Äquivalenz nicht entscheiden.
Bei regulären Ausdrücken können Sie es entscheiden.
Also es gibt ein Programm, das gibt als Eingabe zwei reguläre
Ausdrücke ungarantiert nach endlich vielen Schritten.
Sie bekommen immer die Antwort, die beschreiben die gleiche formale
Sprache oder die beschreiben verschiedene formale Sprachen.
Das kann man algorithmisch rauskriegen.
Und von der Idee her ist das noch nicht mal absurd kompliziert.
So eine Andeutung sehen wir dann später noch.
Allerdings hat dieses Problem eine gewisse Eigenschaft.
Also erstens, es ist in PSPACE, das hatten wir sogar definiert.
Das heißt, Sie können einen Algorithmus hinschreiben, der das Problem
löst.
Und der Platzbedarf des Algorithmus ist beschränkt durch ein Polynom
von Länge dieser regulären Ausdrücke.
Das sagt aber leider nicht so sehr viel über den Zeitbedarf.
Und beim Zeitbedarf für dieses Problem Äquivalenz regulärer Ausdrücke
ist die Situation leider etwas unübersichtlich.
Beobachtung, alle Algorithmen, die man kennt, die dieses Problem
lösen, sind langsam.
Also langsam im Sinne von Laufzeit ist nicht mehr polynomiell.
Also irgendwie sowas wie 2 hoch n Quadrat oder weiß der Geier was.
So sind alle Algorithmen, die man kennt.
Und man weiß jetzt nicht genau, liegt das daran, dass es halt nur so
langsame Algorithmen gibt oder war man bisher einfach nur zu doof,
schnellere zu finden.
Ein offenes Problem.
Also dieses Problem Äquivalenz regulärer Ausdrücke ist, wie man sagt,
vollständig.
Was das ist, lernen Sie im dritten Semester, denke ich, in
theoretische Grundlagen.
Und man kennt nichts, was im Allgemeinen richtig schnell ist.
Jedenfalls bis jetzt nicht.
Und wahrscheinlich die meisten Leute, die Komplexitätstheoretiker,
wenn sie die Fragen würden, vermuten, na wahrscheinlich gibt es keinen
schnellen Algorithmus für ein informelles wahrscheinlich.
Aber es ist offen.
Gut.
Das nur so am Rande.
Ja, so als kleine Andeutung von was kommt dann in so in der Praxis
verwendeten Regular Expressions unter anderem noch dazu.
Also nehmen Sie diesen regulären Ausdruck hier A, B und dann nochmal
in runden Klammern A, B, Stern dahinter.
Was bedeutet das?
Das sind also alle Wörter von der Bauart.
Da kommt erstmal vorne ein Faktor, der ist garantiert immer A, B.
Und dann noch 0, 1, 2, 3, beliebig viele Faktoren, die alle auch
nochmal jeder A, B ist.
Und das heißt insgesamt, Sie haben also mindestens einen Faktor A, B
oder vielleicht auch mehr.
Das heißt so bei den formalen Sprachen haben wir für sowas dieses A, B
und dann oben ein Pluszeichen eingeführt gehabt.
Mindestens ein Faktor, 0 sind verboten.
Das leere Wort ist da jetzt nicht mehr dabei.
A, B und beliebig viele davon.
Sowas will man manchmal ausdrücken.
Und man könnte natürlich immer, egal wie groß der reguläre Ausdruck
ist, dann immer hinschreiben R und dann R in runden Klammern Stern
dahinter.
Dann hat man das ausgedrückt, mindestens ein Faktor und jeder wird
durch R beschrieben.
Aber weil man dann halt den gleichen regulären Ausdruck zweimal
hinschreiben muss, ist das, wenn der reguläre Ausdruck länger wird,
entlästig.
Und deswegen gibt es dann manche Tools, da dürfen Sie auch das
Pluszeichen in einen regulären Ausdruck reinschreiben und es bedeutet
das, was Sie jetzt denken.
Das andere, was man in der Praxis öfter mal hat, ist das hier
sozusagen.
Nehmen Sie den regulären Ausdruck A, B, C, senkrechter Strich, 0
durchgestrichen Stern.
Was bedeutet das?
Der Stern bindet ja ganz stark, der klebt nur an der durchgestrichenen
Null.
Das heißt, im Wesentlichen steht hier, das ist die Vereinigung von der
Sprache, die nur das Wort A, B, C enthält und der Sprache, die durch 0
Stern beschrieben wird.
Das ist leere Menge Konkordinationsabschluss davon.
Diese formale Sprache enthält genau ein Wort, nämlich das leere Wort.
Das ist per Definition immer drin in L-Stern, egal was L ist, aber
nichts anderes offensichtlich.
Also das ist die formale Sprache, die enthält A, B, C und das leere
Wort.
Und das heißt mit anderen Worten, wenn Sie einen großen regulären
Ausdruck haben und dann an einer Stelle dieses Ding da als Teil
regulären Ausdruck, dann drückt das aus.
Also an dieser Stelle darf stehen A, B, C oder das leere Wort.
Oder ein bisschen anders formuliert, da darf A, B, C stehen, aber es
darf auch fehlen.
Das ist optional, das kann man damit einfügen, aber es darf auch weg
sein.
Das will man auch manchmal ausdrücken.
Und deswegen gibt es da bei manchen Tools dann so die Möglichkeit
hinzuschreiben.
R mit einem Fragezeichen dahinter zum Beispiel.
Und das bedeutet dann hier etwas aus R oder nichts.
Also es ist mit anderen Worten eine Abkürzung für R, senkrechter
Strich, durchgestrichene 0 Stern, aber ein bisschen schöner zu lesen.
Und dann gibt es noch mehr bequeme Abkürzungen für Dinge, die man
gerne hinschreiben will.
Stellen Sie sich vor, Sie wollen regulären Ausdruck hinschreiben für
alle Kleinbuchstaben im Deutschen.
Da würden Sie jetzt mit dem, was wir haben, hinschreiben müssen A,
senkrechter Strich, B, senkrechter Strich, C oder D oder E oder F oder
G.
Müssen Sie ein ganz langes Ding hinschreiben, bedeutet es etwas völlig
harmloses, das will kein Mensch.
Dafür gibt es dann natürlich Abkürzungen.
Also in der Praxis macht man sich da natürlich noch ein bisschen
bequemer.
Das machen wir hier nicht, weil es so ist, je restriktiver die
Definition ist, umso bequemer ist es natürlich dafür, etwas zu
beweisen.
Da muss man für wenige Fälle etwas beweisen, wenn es weniger Fälle in
der Definition gibt.
So.
Ja, vielleicht so am Rande.
Es gibt den RFC, der festlegt, wie sieht eine E-Mail aus und da steht
auch irgendwo drin, wie sieht der Header aus mit der Datumsanzeige
oder Zeit.
Da muss also stehen Date, Doppelpunkt und dann etwas.
Hier ist ein Beispiel.
Mittwoch, 29.
Januar, 10.31 Uhr, 47 Sekunden, Zeitzone plus eins.
Da habe ich mich jetzt irgendwie um zehn Minuten vertan beim Raten.
Das ist also offiziell so eine legale Datums- und Zeitangabe in E
-Mails.
Und wenn Sie mal nachgucken, das ist tatsächlich definiert, was da
stehen darf.
Und wenn Sie sich das angucken, dann sehen Sie, dass da etwas Notation
benutzt wird, die heißt Augmented Bacchus-Nauer-Form.
Die Herren Bacchus und Nauer waren Informatiker, wichtige
Informatiker.
Bacchus ein Amerikaner, Nauer ein Däne.
Und im Allgemeinen mit Bacchus-Nauer-Form, mit solchen Gebilden können
Sie mehr, deutlich mehr ausdrücken als mit regulären Ausdrücken.
Aber hier in dem Fall kann man sagen, das ist doch ungefähr so etwas
Ähnliches wie reguläre Ausdrücke.
Nur damit Sie sowas auch mal gesehen haben.
Da steht zum Beispiel in Abschnitt 3.3, also fast wörtlich, ich habe
nochmal nachgeguckt, so ein paar kleine Vereinfachungen habe ich
vorgenommen.
Und ich erzähle auch gar nicht alles, also was FWS in eckigen Klammern
bedeutet hier in der zweiten Zeile, keine Ahnung.
Das wird irgendwas mit Whitespace wahrscheinlich zu tun haben, ich
weiß es nicht.
Jedenfalls, was Sie da sehen, ist so eine lange Liste, da steht immer
auf der linken Seite ein Name und auf der rechten Seite etwas.
Und das ist für uns jetzt mal sowas Ähnliches wie ein regulärer
Ausdruck.
Und mit anderen Worten, man gibt hier also regulären Ausdrücken
irgendwelche Namen und dann in komplizierteren regulären Ausdrücken,
statt das ganze Ding hinzuschreiben, steht da eben der symbolische
Name, damit man weiß, hier soll eine Zeitangabe stehen.
Das ist einfacher als das lange Ding.
Und dann ist zum Beispiel irgendwo definiert, tatsächlich explizit
aufgeführt 0 oder 1 oder 2 oder 3 oder 4 oder 9.
Das ist ein regulärer Ausdruck, der kriegt den Namen Digit.
Und irgendwo wird gesagt, 2 Digit ist eine Abkürzung für Digidigit.
Und was wird dann durch diese reguläre Sprache beschrieben?
Achso, also durch ein Digit, durch den regulären Ausdruck wird
natürlich beschrieben die formale Sprache, die die Wörter 0 bis 9
enthält.
Und dann 2 Digit enthält also diese formale Sprache, konkateniert mit
der gleichen Sprache nochmal.
Das sind also alle Wörter von 00 bis 99.
Und dann steht irgendwo in der Definition, zum Beispiel Our ist der
Name für den regulären Ausdruck.
2 Digits und mit anderen Worten der reguläre Ausdruck Our beschreibt
diese formale Sprache, die alle Wörter von 00 bis 99 enthalten.
Das steht da wirklich so.
Also 00 bis 99 sind legale Stundenangaben.
Und alle sind zweistellig.
Und dann oben bei Time of Day, da steht dann etwas in Gänsefüßchen,
der Doppelpunkt, wenn irgendwas mit Gänsefüßchen umgeben ist, heißt
das, das muss wörtlich so dastehen.
Und dann Minute, das ist genauso definiert wie Our, 2 Digits.
Und dann kommt was in eckigen Klammern und die eckigen Klammern hier
bedeuten jetzt sowas wie das, was wir gerade eben mit dem Fragezeichen
und so.
Hier kann das stehen, aber es ist optional, es darf auch fehlen.
Also hier dieses Doppelpunkt Second, das kann da noch stehen, aber es
darf auch weg sein.
Mit anderen Worten, das ist so eine Abkürzung für Time of Day ist
entweder Our Doppelpunkt Minute oder Our Doppelpunkt Minute
Doppelpunkt Second.
Und das heißt sowas wie 09 Doppelpunkt 50 ist eine legale Zeitangabe
oder hintendran noch irgendwie Sekunden.
Aber es ist halt nicht korrekt, da nur die 9 ohne die führende 0
hinzuschreiben.
Es müssen immer zwei Digit sein.
Das ist das, was der Standard vorschreibt hier.
Also 09 Doppelpunkt 50 wäre syntaktisch falsch.
Auf der anderen Seite 39 Doppelpunkt 71 ist eine syntaktisch korrekte
Zeitangabe, sagt der Standard.
Das ist so.
Das steht dann wahrscheinlich irgendwo anders noch, dass man das nicht
gerne sehen will, aber legal wäre es.
Also manchmal sehen Sie auch Dinge, das sind noch andere Formalismen,
um irgendwas zu beschreiben und Teile davon können Sie aber verstehen
mit dem, was Sie wissen von regulären Ausdrücken.
Nicht alles, aber Teile.
So, ja und die Motivation für dieses Kapitel war ja, wir wollen noch
irgendwo hin, um zu sehen, so ein bisschen den Eindruck zu kriegen,
was kann man mit endlichen Akzeptoren und in die Richtung bewegen wir
uns jetzt.
Mitteilungen, das werden wir hier nicht beweisen, das sehen Sie in
einem Jahr dann in theoretische Grundlagen.
Wenn Sie irgendeine formale Sprache haben, dann drei Aussagen sind
äquivalent.
Also wenn die eine gilt, die beiden anderen gelten garantiert auch und
wenn eine nicht gilt, die beiden anderen gelten garantiert auch nicht.
Nämlich erstens, die formale Sprache wird von einem endlichen Akzeptor
erkannt.
Zweitens, Sie können die formale Sprache durch einen regulären
Ausdruck beschreiben.
Und drittens, Sie können die formale Sprache mithilfe einer
sogenannten rechtslinearen Grammatik erzeugen.
Was das ist, sehen wir gleich noch.
Das ist ein echter Spezialfall von kontextfreien Grammatiken.
Also Mitteilungen für jede formale Sprache.
Entweder es geht alles drei, endlichen Automaten hinschreiben,
regulären Ausdruck hinschreiben, kontextfreie Grammatik hinschreiben,
die das Gewünschte tun oder es geht nichts von allen dreien.
Das sind gleichmächtige Beschreibungsmittel, aber manchmal ist die
eine Methode bequemer, manchmal die andere.
Diese sogenannten rechtslinearen Grammatiken und erstmal eine formale
Sprache, die diese Eigenschaften hat, die nennt man auch regulär.
Also reguläre Sprachen sind die, die das alles erlauben.
Diese Mitteilungen, das sind so die harmlosen Sprachen.
Da kann man noch alles Mögliche und Unmögliche entscheiden.
Alles ist schön.
Die Theorie ist in zwei dicken Büchern aus den 60er Jahren sehr
umfangreich beschrieben.
Alles ist gut.
Diese rechtslinearen Grammatiken, die wir gleich noch kennenlernen
werden, das ist ein Spezialfall von kontextfreien Grammatiken, die wir
schon gesehen haben.
Und mit anderen Worten, jede reguläre Sprache kann man dann mit einer
kontextfreien Grammatik, nämlich sogar mit einer speziellen, erzeugen.
Also jede reguläre Sprache ist kontextfrei.
Aber die Umkehrung gilt nicht.
Das ist ein echter Spezialfall.
Im Allgemeinen, kontextfreie Sprachen sind nicht regulär.
Ein Beispiel werden wir dann gleich nochmal sehen, das haben wir schon
gemacht.
Wie beweist man das?
Eine Möglichkeit ist zu beweisen, wenn ich eine formale Sprache habe,
die erstens erfüllt, dann erfüllt sie auch zweitens.
Und wenn eine formale zweitens erfüllt, dann erfüllt sie auch
drittens.
Und wenn sie drittens erfüllt, dann erfüllt sie auch erstens.
Beweist man so drei Implikationen und dann sind Sie einmal im Kreis,
dann wissen Sie, Sie kommen von jeder Aussage zu jeder.
Und tatsächlich, alle diese drei Schritte sind so, dass man sieht,
also nicht nur beweisen kann, es ist so, sondern das ist alles
konstruktiv.
Also zum Beispiel gegeben ein endlicher Akzeptor, ein beliebiger, dann
können Sie algorithmisch den Rechner konstruieren lassen, einen
regulären Ausdruck, der genau das beschreibt, was der Akzeptor
akzeptiert.
Und das ist mäßig schwierig, würde ich mal sagen.
Es gibt eine Konstruktion, wenn Sie sich die angucken, dann werden Sie
Ähnlichkeiten entdecken mit dem Algorithmus von Warschall, um die
Wegematrix eines gerichteten Graphen auszurechnen.
Das hatten wir mal im Kapitel, ich weiß nicht mehr wie viel.
Man muss ein bisschen was tun, aber man sieht dann relativ leicht, es
funktioniert.
Allerdings Beobachtung am Rande, die regulären Ausdrücke, die da
rauskommen, will man nicht lesen.
Die sind absolut umfangreich, auch für einfache Automaten.
Das ist nicht schön, aber es geht.
Dann der zweite Schritt, wenn man einen regulären Ausdruck hat, dann
kann man daraus systematisch eine rechtslineare Grammatik bauen, die
genau das erzeugt, was durch den regulären Ausdruck beschrieben ist.
Das ist relativ einfach.
Beweis gucken wir uns hinterher noch an, so andeutungsweise.
Das ist recht leicht.
Der schwierigste Teil ist der dritte.
Wenn Sie eine rechtslineare Grammatik haben, dann systematisch,
automatisch dazu einen endlichen Akzeptor konstruieren, so wie wir ihn
definiert haben, der genau das akzeptiert, was die rechtslineare
Grammatik erzeugt.
Das ist der schwierigste Teil.
Und woran das liegt, das merken Sie später mal.
Die Beobachtung ist, dass man sozusagen bei rechtslinearen Grammatiken
an einer Stelle in einem gewissen Sinne mehr Freiheiten hat als bei
den Akzeptoren, die wir definiert haben.
Und dann zu zeigen, dieses Mehr an Freiheit hilft einem nicht.
Man kann nicht trotzdem auf einmal Dinge erzeugen, die irgendwie zu
kompliziert sind.
Das ist so ein bisschen Arbeit.
Und typischerweise diesen letzten Schritt, den macht man auch noch auf
einem Umweg über eine Variante von anderen endlichen Akzeptoren, die
wir hier noch nicht eingeführt haben.
Und auf diese Art und Weise können Sie zum Beispiel auch aus jedem
Akzeptor eine rechtslineare Grammatik konstruieren.
Das kann man allerdings auch direkt machen, sodass die Grammatik viel
einfacher wird.
Das wäre so im Prinzip die Struktur des Beweises.
Und wie gesagt, für den leichten Teil gucken wir uns das dann am Ende
noch ein bisschen genauer an.
Ja, also damit erstmal haben wir zum Ersten nochmal gesehen, wie
sollen hier diese klassischen regulären Ausdrücke definiert sein.
Und diese klassische Variante, damit können Sie genau das beschreiben,
was Sie mit endlichen Akzeptoren akzeptieren können.
Und Sie können eben so Dinge sagen, wie etwas von dieser Bauart
beliebig oft wiederholt oder etwas von dieser Bauart und etwas von
dieser Bauart hintereinander und sowas wie eine Oder haben Sie.
Und dann halt manchmal kriegt man irgendwie beschriebene formale
Sprache und muss sich dann halt selber einen regulären Ausdruck
überlegen, der genau das Richtige beschreibt oder Sie haben den
regulären Ausdruck und müssen herausfinden, irgendwie anders
charakterisieren, welche Wörter werden denn dadurch beschrieben.
Muss man halt beides so ein bisschen üben.
Apropos üben.
Hatten wir das in einer E-Mail geschrieben auf Elias oder nicht?
Dann sage ich es Ihnen sicherheitshalber nochmal.
Wir haben noch so etwas wie eine Art 13.
Aufgabenblatt gemacht.
Da können Sie keine Punkte mehr gewinnen, aber Sie können noch so ein
paar Sachen üben, die halt jetzt erst zuletzt dran waren in der
Vorlesung.
Das sollten Sie vielleicht tun.
Zur Erinnerung, wenn Sie die Klausur schreiben wollen, Sie müssen sich
anmelden.
Wenn Sie den Übungsschein machen wollen, Sie müssen sich anmelden.
Beim Übungsschein sehe ich überhaupt keinen Grund, sich nicht
anzumelden.
Für einen Übungsschein kann man sich rein theoretisch beliebig oft
anmelden, egal wie lange man braucht, bis man ihn hat.
Bei der Klausur, für die meisten ist Orientierungsprüfung, das darf
man nicht beliebig oft wiederholen.
Was noch wichtig ist für diese Anmeldung, es gibt eine Frist.
Für den Übungsschein können Sie sich anmelden bis 26.
Februar, glaube ich, 23.59 Uhr.
Und für die Klausur können Sie sich online nur anmelden bis 11.
März, 23.59 Uhr.
Bitte versäumen Sie das nicht, melden Sie sich rechtzeitig an.
Abmelden geht, wie gesagt, länger, also bei der Klausur bis 24 Stunden
vor der Klausur online.
Und wenn Sie das verpasst haben, können Sie auch noch direkt vor der
Klausur hier im Hörsaal erscheinen und sich da persönlich abmelden.
So.
Ja, jetzt hatten wir gerade in diesem Satz diese eine
Charakterisierung über rechtslineare Grammatiken oder wie man auch
sagt Typ 3 Grammatiken.
Was ist das?
Sie erinnern sich hoffentlich an kontextfreie Grammatiken.
Hier ist nochmal ein Beispiel hingeschrieben.
Wir haben also nicht Terminalsymbole, Terminalsymbole, ein
Startsymbol.
Das ist ein Nicht-Terminalsymbol, das muss also das X sein, wenn es
keine anderen gibt.
Und Produktionen, hier zum Beispiel X darf ich ersetzen durch A, X, B
oder das leere Wort.
Und diese Grammatik, wenn Sie die anwenden mit X anfangen, wenn Sie da
ein paar mal X ersetzen durch A, X, B, dann entstehen da links und
rechts von dem X A´s und B´s, links die A´s, rechts die B´s, gleich
viele.
Und irgendwann machen Sie das X in der Mitte weg, ersetzen es durch
leere Wort und was Sie ableiten können, sind genau die Wörter der Form
A hoch K, B hoch K.
Und wir haben bewiesen, diese formale Sprache ist nicht regulär.
Für diese formale Sprache gibt es keinen endlichen Akzeptor.
Das heißt, mit beliebigen kontextfreien Grammatiken können Sie Sachen
erzeugen, die sind zu kompliziert für endliche Akzeptoren.
Das ist mehr als das, was man mit endlichen Akzeptoren kann.
Frage, kann man die Grammatiken noch irgendwie einschränken, sodass es
dann gut passt?
Nun ist diese Grammatik ja noch nicht mehr besonders kompliziert.
Was kann man da noch groß einschränken?
Also bei der Anzahl Produktionen zu sagen, ich erlaube nur eine, das
wäre schlecht.
Denn entweder in der einen Produktion kommt noch ein Nicht-Terminal
-Symbol vor, dann können Sie gar nichts ableiten, weil Sie das Nicht
-Terminal -Symbol nicht wegkriegen.
Oder es steht kein Nicht-Terminal-Symbol, dann können Sie nur ein Wort
ableiten.
Das ist vielleicht etwas krass.
Also Alternative irgendwie bei den Längen der rechten Seiten.
Das wäre eine Möglichkeit.
Allerdings, das ist auch nicht das, was wir hier tun werden.
Wo wir uns einschränken werden, ist bei der Position des Nicht
-Terminal -Symbols.
Und wir werden dabei bleiben, wie hier in dem Beispiel, nur eins.
Und dann haben Sie sogenannte rechtslineare Grammatiken.
Zu dem Namen sage ich gleich noch was.
Also das ist eine kontextfreie Grammatik, so wie wir es kennen, wo
zusätzlich die Produktionen der folgenden Einschränkungen genügen.
Also Produktionen, so viele Sie wollen.
Aber bei jeder Produktion, also entweder auf der rechten Seite steht
ein Wort, das besteht nur noch aus Terminal-Symbolen.
Sowas hat man immer, sonst kriegt man die Nicht-Terminal-Symbole nicht
los.
Also das ist erlaubt.
Und alternativ sind erlaubt Produktionen, da stehen erstmal vorne dran
Terminal -Symbole, so viele Sie wollen, meinetwegen auch null.
Und dann am Ende, ganz am Ende rechts, ganz rechts als letztes ein und
auch nur ein Nicht-Terminal-Symbol.
Also diese Grammatik von eben, ich gehe mal zurück, war nicht
rechtslinear, weil das X hier in der Mitte steht und nicht am rechten
Ende bei A, X, B.
Die Grammatik ist nicht rechtslinear.
Bei Rechtslinear, das Nicht-Terminal-Symbol, wenn eins vorkommt, muss
ganz rechts stehen und das Linear sagt, es darf am höchsten eins sein
in jeder Produktion auf der rechten Seite.
Das ist die Einschränkung und Beobachtung, das ist eine echte
Einschränkung.
Gucken wir uns als erstes mal zwei Beispiele an.
Hier X darf ich ersetzen.
Wir haben nur ein Nicht-Terminal-Symbol, es dürfen auch mehrere sein.
Aber wenn Sie nur eins haben, hier zum Beispiel so eine Grammatik X
dürfen Sie ersetzen durch A, B, X oder B, B, A, X oder das leere Wort.
Das ist rechtslinear.
Also wenn da ein Nicht-Terminal-Symbol auf der rechten Seite vorkommt,
es steht immer ganz rechts.
Und es ist auch immer nur eins.
Was kann man mit der Grammatik machen?
Na ja, Sie fangen an mit dem Start-Symbol X und dann können Sie das
ersetzen durch A, B, X.
Dann steht da also einmal A, B und hinten das X.
Dann wenden Sie vielleicht die andere Produktion an, ersetzen das X
durch B, B, A, X und dann vielleicht nochmal das X durch B, B, A, X
und dann vielleicht wieder das X durch A, B, X.
Also bei jedem Ableitungsschritt, Sie haben schon so ein Stück
Terminal -Symbole, erzeugen noch ein bisschen Terminal-Symbole und das
Nicht -Terminal-Symbol bleibt immer am rechten Ende.
Und da können Sie also beliebig oft so Faktoren A, B oder B, B, A in
beliebiger Reihenfolge erzeugen, so viel Sie wollen.
Und am Ende oder auch gleich im ersten Schritt das Nicht-Terminal
-Symbol wegmachen und dann sind Sie fertig.
Und was haben Sie?
Beliebig viele Faktoren und jeder ist A, B oder B, B, A.
Also die erzeugte formale Sprache, die können Sie zum Beispiel durch
diesen regulären Ausdruck beschreiben.
A, B oder B, B, A beliebig oft hintereinander.
Also in diesem Fall durch hingucken.
Wir haben einen regulären Ausdruck gesehen.
Anderes Beispiel, jetzt zwei Nicht-Terminal-Symbole, X und Y.
X ist das Startsymbol, was dürfen Sie tun?
Also X ist das Startsymbol, dürfen Sie ersetzen durch AX oder durch BX
und dann können Sie also erstmal eine beliebige Folge von A's und B's
erzeugen.
A's, B's durcheinander, immer noch X.
Irgendwann will man ja mal das fertig sein.
Das heißt, man muss das Nicht-Terminal-Symbol, die einzige Chance ist
hier Y durch Epsilon zu ersetzen.
Und das heißt, man muss irgendwie zum Y kommen und das heißt, man muss
die Produktion X ersetzen durch A, B, A, B, B, Y anwenden.
Also man erzeugt erstmal A's und B's, beliebig viele, bunt
durcheinander.
Dann ersetzt man X durch A, B, A, B, B, Y.
Und dann kann man mit Y machen, wieder noch ein buntes Mischmasch aus
A's und B's und irgendwann hört man halt auf.
Das heißt, alle Wörter, die Sie da ableiten, sehen so aus, vorne
irgendetwas, dann A, B, A, B, B garantiert und dahinter irgendetwas.
Das können Sie also durch einen regulären Ausdruck so beschreiben,
vorne A oder B Stern, beliebiges Präfix, dann garantiert A, B, A, B, B
und hinten wieder etwas Beliebiges.
Alle Wörter, die irgendwo das Teilwort A, B, A, B, B enthalten und mit
ein bisschen Glück, erinnern Sie sich an das Kapitel über endliche
Akzeptoren, da haben wir uns einen Schritt überlegt, der genau diese
Wörter akzeptiert.
Irgendetwas und dann einmal A, B, A, B, B und dahinter noch
irgendetwas.
Das war das Ergebnis.
Sechs Zustände und allerlei Pfeile, ich will nicht sagen kreuz und
quer, aber es war nicht so komplett naheliegend.
Und wenn Sie das vergleichen mit diesem regulären Ausdruck, ich
glaube, dann können Sie mir zustimmen, der reguläre Ausdruck ist
anschaulicher.
Da sieht man, da steht irgendwo A, B, A, B, B und davor und dahinter
Beliebiges.
Das ist ein Beispiel, da ist ein regulärer Ausdruck einfach viel
bequemer.
Und deswegen beschränkt man sich nicht auf einen Formalismus, sondern
es ist gut, verschiedene Werkzeuge zu haben.
Man will eine Schraube nicht mit dem Hammer in die Wand bohren.
Diese Grammatik, X ersetzen durch A, X, B oder Y, die ist nicht
rechtslinear, habe ich vorhin schon gesagt, weil das X auf der rechten
Seite nicht am rechten Ende steht.
Und wir haben uns überlegt, die formale Sprache, die von der Grammatik
erzeugt wird, die ist gar nicht regulär.
Es gibt keinen endlichen Akzeptor, es gibt keinen regulären Ausdruck,
es gibt gar keine rechtslineare Grammatik.
Das heißt, mit dieser einfachen Grammatik können Sie etwas erzeugen,
was Sie mit keiner rechtslinearen Grammatik erzeugen können.
Und da sehen Sie also diese Einschränkungen, das Nicht-Terminalsymbol
muss am rechten Ende stehen, das ist schon wirklich eine Einschränkung
und es ist vielleicht nicht völlig offensichtlich, dass man sich da
einschränkt.
Aber da sieht man es, also wenn man den Satz vom Anfang glaubt, den
wir hier nicht bewiesen haben.
So, habe ich am Anfang schon gesagt, rechtslineare Grammatiken heißen
auch Typ 3 Grammatiken, normale kontextfreie Grammatiken nennt man
auch Typ 2 Grammatiken und Sie dürfen mal raten, große Überraschung,
es gibt auch Typ 1 Grammatiken und Typ 0 Grammatiken.
Und so wie man mit Typ 2 Grammatiken mehr erzeugen kann als mit Typ 3
Grammatiken, das Beispiel hatten wir da eben, A hoch K, B hoch K, so
können Sie auch mit Typ 1 Grammatiken, wie auch immer die definiert
sein mögen, mehr erzeugen als mit Typ 2 Grammatiken und mit Typ 0
Grammatiken können Sie mehr erzeugen als mit Typ 1 Grammatiken.
Und was Sie mit Typ 0 Grammatiken erzeugen können, sind genau die
regulär aufzählbaren Sprachen.
Also salopp gesagt, das ist jetzt Hände wedeln, aber nicht sehr.
Mit Typ 0 Grammatiken können Sie Turing-Maschinen simulieren.
Und auch nicht mehr.
Das so als Mitteilung, das werden wir hier nicht weiter definieren,
vertiefen.
Achso, und wenn man eine Sprache hat, die von einer Typ I Grammatik
erzeugt wird, dann sagt man auch, das ist eine Typ I Sprache oder die
Sprache ist vom Typ I.
Also reguläre Sprachen sind Typ 3 Sprachen.
Das bedeutet genau das Gleiche.
Nur falls Ihnen das mal irgendwo über den Weg läuft.
Rechtslineare Grammatiken sind manchmal übersichtlicher, genau wie
reguläre Ausdrücke, als endliche Akzeptoren.
Woran das liegt, das werden Sie im dritten Semester merken.
Also salopp gesagt ist es so, Sie können zu jedem endlichen Akzeptor
direkt eine rechtslineare Grammatik bauen und das Nicht-Terminal
-Symbol, das Sie da immer am Ende stehen haben, das ist ziemlich genau
sozusagen der Zustand des endlichen Akzeptors.
Das können Sie eins zu eins nachverfolgen.
Deswegen können Sie leicht aus dem endlichen Akzeptor die
rechtslineare Grammatik bauen.
Aber wenn Sie jetzt diese rechtslinearen Grammatiken mal als so eine
Art Verallgemeinerung von endlichen Automaten sehen wollen, was Sie
bei der rechtslinearen Grammatik haben als Möglichkeit ist, dass man
da hinschreiben kann, ja das X da hinten, das kann ich jetzt ersetzen
durch AY oder durch AZ.
Also wenn Sie X, also so etwas wie den Zustand haben und Sie wollen
jetzt ein A als nächstes haben, dann hinterher, es ist nicht mehr
klar, was ist der nächste Zustand sozusagen.
Und diese Verallgemeinerung, die macht es halt bequemer manchmal.
Und dass das aber nur eine syntaktische Verallgemeinerung ist, dass
Ihnen das nicht die Möglichkeit gibt, mehr Sprachen zu erzeugen, ja
das ist halt die nicht ganz naheliegende Konstruktion und das sehen
Sie dann halt im dritten Semester.
So.
Und jetzt wollen wir das, was wir bis hierher gesehen haben, noch mal
als ein Beispiel nehmen, um letzten Endes nochmal so eine klein
bisschen allgemeinere Version von vollständiger Induktion anzugucken.
Das ist kein Hexenwerk, aber man soll es halt mal gesehen haben.
Und wir gehen nochmal zurück zu der einen Teilaussage von dem Satz von
vorhin, nämlich Behauptung zu jedem regulären Ausdruck gibt es eine
rechtslineare Grammatik, die genau das erzeugt, was durch den
regulären Ausdruck beschrieben wird.
Das war so einer von den drei Teilen, wo ich gesagt habe, also bei der
Beweisidee, das ist der leichteste Teil und da wollen wir uns das so
ein kleines bisschen genauer angucken.
Das ist wirklich relativ simpel, werden Sie gleich merken.
Allerdings, na gut, also es wird relativ kurz, weil wir an der
entscheidenden Stelle sagen, ja beweisen tun wir das jetzt nicht
genau, aber man kann es auch relativ einfach beweisen.
Stellen Sie sich vor, man muss das beweisen, dann müssen Sie also
Aussage für jeden regulären Ausdruck etwas.
Wie kann man sowas tun?
Naja, also die einfachste Methode, solche Aussagen zu beweisen, ist zu
sagen, ja ich nehme einen beliebigen her und dann versuche ich
irgendetwas zu tun ad hoc.
Eine strukturierte Möglichkeit ist irgendeine Art von Induktion.
Das nennt man dann im Allgemeinen irgendwie strukturelle Induktion,
was das ist, werden Sie gleich merken.
Da redet man zumindest nicht mehr so ganz explizit über natürliche
Zahlen, aber wenn man es ein paar Mal gemacht hat, merkt man so
implizit, naja das ist schon irgendwie immer noch mit dabei.
So und damit wir also diese Aussage da oben in dem Lemma zumindest den
Beweis andeuten können, machen wir jetzt das folgende.
Als erstes malen wir reguläre Ausdrücke ein bisschen anders hin.
Das ist aber im Wesentlichen nur dazu da, jetzt für uns, um es
hinterher ein bisschen anschaulicher zu machen.
Also stellen Sie sich vor, Sie haben so einen regulären Ausdruck wie
hier hingeschrieben, B oder nichts, dahinter ein A und hinter dem
Ganzen nochmal B-Stern.
Dann können Sie diesen regulären Ausdruck und analoges können Sie für
arithmetische Ausdrücke oder so machen, als Baum hinmalen, indem Sie
an den Blättern irgendwie die atomaren regulären Ausdrücke, die
atomaren Werte oder was auch immer hinschreiben und für jeden Operator
sozusagen, der hier in dem regulären Ausdruck vorkommt, also für den
senkrechten Stern und für dieses Hintereinander von B oder Null und A
und das Hintereinander von dem ersten Teil und dem B-Stern, für jeden
Operator, auch wenn man hier sozusagen den Punkt nicht sieht oder
keinen hinschreibt, haben Sie einen inneren Knoten in dem Baum.
Also das ist nicht irgendwie der Ableitungsbaum von irgendeiner
kontextfreien Grammatik für den regulären Ausdruck, aber etwas, was
den regulären Ausdruck auch irgendwie repräsentiert.
Also die Wurzel steht sozusagen für hier der ganze reguläre Ausdruck
und übrigens so im Großen und Ganzen habe ich hier so einen kleinen
Punkt in die Wurzel gemalt, das ist Konkatenation von zwei regulären
Ausdrücken und der linke ist auch wieder eine Konkatenation und hat
auch wieder zwei Nachfolger und der linke Nachfolger hier ist ein Oder
und zwar ein Oder von B und durchgestrichener Null.
Der rechte Faktor der inneren Konkatenation ist A und der rechte
Faktor von der äußeren ist Abschluss von B und dann kriegen Sie
irgendwie so einen Baum und das wollen wir jetzt mal einfach einen
Regexbaum nennen.
Das ist einfach so ein bisschen grafisch eine Repräsentation von so
einem Ausdruck.
Und wenn Sie statt der Operatoren hier irgendwie Plus Minus Mal durch
und an den Blättern Zahlen vorstellen, dann haben Sie einen
arithmetischen Ausdruck repräsentiert und den könnten Sie auch
irgendwie auswerten und so.
Und auch wenn das kein Ableitungsbaum ist, tatsächlich was ein
Compiler macht, wenn Sie dem so ein Java Programm geben und Sie haben
da irgendwie arithmetische Ausdrücke drin stehen oder auch
kompliziertere Dinge, so Kontrollfluss.
Also erstmal versucht er ja sowas wie einen Ableitungsbaum in der Java
Grammatik zu finden und dann, ich rede jetzt mal so, als würde das
hinterher passieren, macht er aus dem Ableitungsbaum genau sowas.
Also insbesondere für arithmetische Ausdrücke wird der Compiler sowas
generieren und wenn da keine Variablen vorkommen, nur Konstanten, wird
das vielleicht sogar gleich auswerten, der Compiler, noch bevor das
Programm überhaupt läuft.
Aber das nur so am Rande.
So, also jetzt habe ich hier so Hände wedelnd an einem Beispiel
gesagt, das sind Regexbäume.
Wenn man es ordentlich definieren will, naja, hat man halt wieder eine
induktive Definition.
Und was gibt es?
Es gibt die ganz simplen Bäume, da ist die Wurzel schon das Blatt, da
ist einfach nur ein Knoten, gar keine Kanten.
Es ist sehr niedrig, dieser Baum.
Und zwar, es gibt halt per Definition die Regexbäume, wie man dann
sagt, der Höhe 0, nämlich für die durchgestrichene 0 und für jedes
Symbol aus dem zugrunde liegenden Alphabet, das einen interessiert.
Und alternativ, wenn man schon kleine Regexbäume hat, kann man daraus
größere konstruieren.
Eine Möglichkeit ist, Sie nehmen einen Regexbaum und verpassen dem
oben drüber eine neue Wurzel, wo ein Stern drinsteht und ein Pfeil
nach unten zur bisherigen Wurzel.
Oder Sie nehmen eine neue Wurzel und schreiben da ein senkrechtes
Strich rein für das Oder oder ein Pünktchen für die Konkatenation und
Sie machen zwei Pfeile zu den Wurzeln von zwei Regexbäumen und deren
bisherige Wurzeln sind halt dann nicht mehr Wurzeln, sondern innere
Knoten.
Also das sind die Regeln aus atomaren Bäumchen und diesen Operationen
größere Regexbäume zusammensetzen.
Und was Sie dann bauen können, sind halt genau die Bäume, wo Sie
offensichtlich sagen werden, ja zu jedem Baum kann ich eindeutig
hinschreiben, wie sieht der reguläre Ausdruck aus.
Das könnten Sie natürlich machen, kriegen Sie alle hin.
Also große Bäume sind aus kleinen zusammengesetzt und die Art und
Weise jedenfalls hier war jetzt immer eindeutig.
Sie können nicht auf verschiedene Arten durch verschiedene
Reihenfolgen von Operationen irgendwie am Ende zu dem gleichen Baum
kommen.
Und Sie haben so eine offensichtliche Bijektion von solchen Bäumen und
den normalen regulären Ausdrücken.
Und für Bäume kann man definieren, was ist ihre Höhe.
Ich weiß gar nicht, ob wir das irgendwo in der Vorlesung oder in der
großen Übung schon mal hatten.
Ich glaube schon, aber falls nicht, die Höhe eines Baumes, wo die
Wurzel gleich das Blatt ist, ist per Definition im Null.
Und ansonsten ist die Höhe 1 plus Maximum der Höhen der Unterbäume.
Mit anderen Worten, die Höhe eines Baumes, das ist die Länge der
längsten Pfade von der Wurzel bis zu einem Blatt.
Sie zählen, wie viele Kanten kann ich da maximal nach unten gehen, bis
ich bei einem Blatt bin.
Das ist die Höhe.
Und wenn man jetzt also irgendetwas beweisen will für alle regulären
Ausdrücke, also zum Beispiel zu jedem regulären Ausdruck, es gibt eine
rechtslineare Grammatik, blablabla, dann können Sie sagen, wegen
dieser Bijektion, ich beweise das für alle Regex-Bäume.
Und wie können Sie was beweisen für alle Regex-Bäume?
Sie können zum Beispiel sagen, ja, ich mache vollständige Induktion
und beweise für jede Höhe und dann, Höhe ist eine nicht negative ganze
Zahl, durch Induktion über die Höhen, für jede Höhe gilt, für alle
Bäume dieser Höhe gilt, das, was ich möchte.
Also Sie gruppieren die Bäume nach Höhe und sagen dann, für jede Höhe,
es klappt immer.
So.
Und ganz naive Induktion, wie wir sie ganz, ganz, ganz am Anfang
gemacht haben, war ja so, im Induktionsschritt, wenn Sie für den Fall
N plus 1 was beweisen wollen, Sie benutzen, dass die Aussage für N
schon gilt, als Voraussetzung.
Und dann haben wir uns aber ziemlich schnell klargemacht, es ist nicht
schlimm, wenn Sie im Induktionsschritt, wenn Sie für N plus 1 was
beweisen wollen, nicht nur die Aussage für den Fall N schon benutzen,
sondern für die kleineren Zahlen, das können Sie auch mit benutzen.
Das macht den Beweis nicht falsch.
Es ist immer noch nur ein bisschen umgeschrieben, eine ganz normale,
vollständige Induktion.
Also wenn Sie für N plus 1 was beweisen wollen, Sie können als
Induktionsvoraussetzung die Gültigkeit der Aussage für alle kleineren
Werte annehmen.
Und das heißt jetzt hier, wenn Sie durch vollständige Induktion über
die Baumhöhe irgendwas beweisen wollen, wenn Sie jetzt für Bäume der
Höhe N plus 1 was beweisen wollen, Sie haben als
Induktionsvoraussetzung die Aussage gilt für alle Bäume, die eine
kleinere Höhe haben.
I kleiner gleich N.
Nicht nur N, sondern auch N minus 1, N minus 2.
Dann kann man tatsächlich das beweisen, was wir jetzt hier beweisen
wollen zu jedem regulären Ausdruck.
Es gibt eine rechtslineare Grammatik, die genau das erzeugt, was der
reguläre Ausdruck beschreibt.
Induktionsanfang, man hat einen Regexbaum der Höhe 0, das heißt, da
kann nur stehen ein einzelnes Symbol, so ein kleines A oder sowas,
oder die durchgestrichene 0.
Und dann muss ich für diese regulären Ausdrücke ein einzelnes A oder
die durchgestrichene 0 beweisen.
Es gibt rechtslineare Grammatiken, die das erzeugen, was durch die
Dinger beschrieben wird.
Wenn da ein einzelnes A steht, dann müssen Sie eine rechtslineare
Grammatik hinschreiben, die genau das eine Wort erzeugt, A.
Das ist einfach, da schreiben Sie die eine Produktion hin, X erzeugt
A.
Fertig für den Startsymbol X.
Und dann brauchen Sie noch eine rechtslineare Grammatik, die das
erzeugt, was durch den regulären Ausdruck durchgestrichene 0
beschrieben wird.
Das ist die leere Menge.
Da brauchen Sie eine rechtslineare Grammatik, die gar keine Wörter
erzeugt.
Ja, das geht auch.
Primitivstmöglichkeit, die Menge der Produktionen ist leer, dann
können Sie nichts ableiten.
Da haben Sie immer das Startsymbol stehen und aus ist.
Also das geht auch.
Also Induktionsanfang ist erledigt und dann kommt halt der
Induktionsschritt von irgendeinem n nach n plus 1.
Induktionsvoraussetzung für alle i kleiner gleich, jetzt nicht nur
gleich, sondern kleiner gleich n gilt.
Für jeden Regexbaum der Höhe i kann ich eine rechtslineare Grammatik
hinschreiben, sodass er genau das erzeugt, was durch den Baum
beschrieben wird.
Und dann muss ich zeigen, ja, für Bäume der Höhe n plus 1 gilt das
auch.
Ja, und dann muss man sich halt Bäume der Höhe n plus 1 angucken.
Bäume der Höhe n plus 1 können nicht Höhe 0 haben, zumindestens 1.
Und wie sehen solche Bäume aus?
Na ja, da gibt es drei Möglichkeiten.
Sternchen, ein Nachfolger oder Konkordination mit zwei oder oder mit
zwei Nachfolgern.
Und diese Unterbäume r' r1' r2' haben jedenfalls eine Höhe kleiner
gleich n.
Die müssen nicht gleich hoch sein, ja, manche können auch ganz niedrig
sein.
Und jetzt haben sie also als Induktionsvoraussetzung für diese r' r1'
r2' es gibt rechtslineare Grammatiken, die das Gewünschte erzeugen und
dann müssen sie eben dann jetzt für das große Ding auch eine
rechtslineare Grammatik bauen.
Da haben sie hier drei Fälle zu betrachten und dann mache ich es mir
mal ganz bequem und nehme den Fall für das oder.
Also Induktionsvoraussetzung, also sie haben einen regulären Ausdruck
dieser Bauart r1 oder r2.
Induktionsvoraussetzung, sie haben eine rechtslineare Grammatik, die
erzeugt das, was durch r1 beschrieben wird und sie haben eine
rechtslineare Grammatik, die erzeugt das, was durch r2 beschrieben
wird.
Aufgabe, man baue eine rechtslineare Grammatik, die das erzeugt, was
durch r1 oder r2 beschrieben wird, die also die Vereinigung von den
beiden Sprachen erzeugt.
Also gut, wir haben eine Grammatik g1, die erzeugt das, was durch r1
beschrieben wird und eine Grammatik g2, die erzeugt das, was durch r2
beschrieben wird.
Jede Grammatik hat so ein paar Nicht-Terminalsymbole, die gleichen
Terminalsymbole, jede Grammatik hat ein Startsymbol und ein paar
Produktionen.
Und jetzt brauchen wir eine Grammatik, die die Vereinigung erzeugt.
Was ist die grobe Idee?
Wir nehmen ein neues Startsymbol und im ersten Schritt können wir dann
das ableiten zu dem Startsymbol der einen Grammatik und andere
Möglichkeit ableiten zu dem Startsymbol der anderen Grammatik und dann
nimmt man halt die Produktionen von der einen oder der anderen
Grammatik und erzeugt das, was die erzeugen kann.
Man möchte also gerne die Produktionen von den beiden Grammatiken in
einen Topf schmeißen.
Und dann muss man jetzt aber aufpassen, dass man jetzt nicht auf
einmal Produktionen hat, ein Teil aus der einen, ein Teil aus der
anderen Grammatik und man kann die irgendwie zusammenmischen und
irgendwelche komischen Dinge tun, die man nicht haben will.
Deswegen, ohne Beschränkung der Allgemeinheit, Behauptung, wir dürfen
davon ausgehen, die Nicht-Terminalsymbole von G1 und die Nicht
-Terminalsymbole von G2, das sind disjunkte Mengen.
Es gibt kein Nicht-Terminalsymbol, das bei beiden Grammatiken benutzt
wird.
Salopp gesagt, falls doch, malen Sie die einen blau an und die anderen
rot und dann sind sie verschieden.
Also wir nehmen das einfach an.
Das ist keine große Einschränkung.
Wir gehen einfach immer davon aus, wir haben ja noch ein paar Symbole
brauchen, wir haben sie schon.
So und wenn das so ist, dann können Sie einfach das tun, was ich
gerade beschrieben habe.
Neue Grammatik, also wir nehmen alle Nicht-Terminalsymbole von der
einen Grammatik und die von der anderen und zusätzlich noch ein neues
Symbol S, was weder in der einen noch in der anderen Grammatik benutzt
wird.
Und das ist unser neues Startsymbol und wir haben zwei Produktionen.
S darf ich ersetzen durch S1 oder durch S2.
Und außerdem nehmen wir dazu alle Produktionen aus Grammatik 1 und
alle Produktionen aus Grammatik 2.
Und dann erstens können Sie in dieser Grammatik ableiten aus S erstmal
S1 und dann mithilfe der Produktionen aus P1 alles, was Grammatik G1
erzeugt hat.
Und Sie können auch alles erzeugen, was Grammatik G2 erzeugt hat,
indem Sie erst S durch S2 ersetzen und dann eben die Produktionen aus
P2 nehmen.
Also Sie können sicherlich alles erzeugen, was die eine oder die
andere Grammatik erzeugt hat.
Und weil die Produktionen in P1 und P2 nichts miteinander zu tun
haben, kein gemeinsames Nicht-Terminalsymbol, können Sie auch nichts
anderes tun.
Also salopp gesagt, wenn Sie sich erstmal für die blaue Grammatik
entschieden haben, dann werden Sie nur noch blaue Nicht
-Terminalsymbole sehen und wenn Sie sich für die rote Grammatik
entschieden haben, werden Sie nur noch rote Nicht-Terminalsymbole
sehen.
Und Sie können nicht wechseln.
Sie haben keine Produktion, um von einem blauen Nicht-Terminalsymbol
zu einem roten zu kommen oder umgekehrt.
Wenn Sie sich erstmal im ersten Schritt entschieden haben für
Grammatik 1 oder Grammatik 2, das war es.
Und deswegen, wenn man das ein bisschen ordentlich aufschreibt, stellt
man dann fest, was die Grammatik erzeugt, ist genau die Vereinigung
dieser beiden Sprachen und das ist genau das, was durch den regulären
Ausdruck R1 oder R2 beschrieben wird.
Das war jetzt von mir noch ein bisschen händewedelnd, haben Sie
hoffentlich gemerkt.
Aber man kann es auch ein bisschen ordentlicher statt rot und blau
irgendwas anderes hinschreiben und dann ist alles gut.
Achso, also das mit der Vereinigung habe ich plausibel gemacht, dass
das ja wohl so ist.
Worauf man natürlich auch noch achten muss, ist die Grammatik immer
noch rechtslinear, die neue.
Also wie war das bei jeder Produktion, wenn überhaupt ein Nicht
-Terminal -Symbol auf einer rechten Seite vorkommt, dann ganz am Ende.
Welche Produktionen haben wir?
S ersetzen durch S1, da steht das S1 am rechten Ende der rechten
Seite.
S ersetzen durch S2, das S2 steht auch am rechten Ende.
Und in den Produktionen in P1 und P2, ja da ist das auch immer so,
denn die Grammatiken G1 und G2 waren ja rechtslinear nach
Voraussetzung.
Also das ganze Ding ist wirklich rechtslinear.
Und jetzt gehe ich nochmal ein kleines bisschen zurück.
Ich habe ja gesagt, ja ich mache es mir hier leicht, wir gucken uns
den Beweis fürs Oder an.
Wenn Sie das gleiche für die Konkatenation machen wollen, dann der
naheliegende Reflex funktioniert nicht.
Die analoge Idee wäre jetzt einfach, wir nehmen eine Produktion und
aus S kann ich ableiten S1, S2 und dann aus S1 ein Wort aus der einen
Sprache, aus S2 eins aus der anderen Sprache.
Aber dann haben Sie eine Produktion mit zwei Nicht-Terminal-Symbolen
hintereinander und das ist ja verboten.
Da ist es schwieriger, sich eine rechtslineare Grammatik zu besorgen.
Und deswegen habe ich den Fall hier nicht betrachtet.
Da muss man mehr tun, das wollen wir uns hier nicht antun.
So und was wir jetzt hier gerade gemacht haben, so argumentieren über
Regex, Bäume und große sind aus kleinen zusammengesetzt.
Das ist sozusagen ein Beispiel gewesen von sowas wie struktureller
Induktion.
Also was hat man da immer?
Man hat so kleine, man hat Gebilde und aus Bauklötzchen und kleinen
Gebilden kann man größere Gebilde zusammensetzen.
Und da gibt es also so atomare, kleine Lego-Steinchen, die Sie nicht
weiter zerlegen können oder was auch immer.
Und Sie haben Möglichkeiten, die zusammenzusetzen und Sie haben
Konstruktionsvorschriften, aus kleinen Gebilden größere zu machen für
irgendein Maß von groß und klein.
Also bei den Bäumen war es einfach die Höhe.
Und wenn Sie dann zeigen wollen, dass irgendetwas für alle Gebilde,
die Sie konstruieren können, gilt, ist eben eine Möglichkeit, das
jetzt sozusagen allgemein zu tun, was wir gerade für Regex-Bäume
gemacht haben.
Sie zeigen erstmal für diese ganz elementaren, atomaren Gebilde Lego
-Steinchen, triviale, reguläre Ausdrücke, die ganz kurz sind, die
haben alle die Eigenschaft.
Punkt eins.
Und Punkt zwei, wenn Sie aus kleinen Gebilden größere zusammensetzen,
die Eigenschaft bleibt erhalten.
Es gibt rechtslineare Grammatiken, die das Richtige erzeugen oder so.
Egal auf welche Art und Weise Sie die größeren Gebilde aus kleinerem
zusammensetzen, in jedem Konstruktionsschritt, die Eigenschaft
überträgt sich aus den Komponenten auf das ganze größere Ding.
Das ist strukturelle Induktion.
Und damit sind wir dann auch am Ende dieses Kapitels.
Also behalten Sie im Hinterkopf, es gibt diese rechtslinearen
Grammatiken und das, was ich Ihnen so Händewedeln gesagt habe, dieses
Nicht -Terminal, das ist sozusagen so eine Art verallgemeinerte
endliche Automaten.
Das Nicht-Terminal-Symbol ist so ein bisschen der Zustand.
Wedel, Wedel, Wedel.
Das ist die richtige Intuition.
Achso, jetzt könnten Sie natürlich auf die Idee kommen und fragen,
vielleicht hat es mindestens einer im Kopf, was ist denn, wenn ich
statt rechtslineare Grammatiken linkslineare Grammatiken betrachte.
Also das Nicht-Terminal-Symbol muss nicht immer ganz hinten stehen,
sondern ganz vorne.
Das ist eine Mitteilung.
Das ändert nichts.
Mit linkslinearen Grammatiken können Sie auch genau die regulären
Sprachen erzeugen.
Da ist dann die Interpretation nicht mehr so einfach der Zustand des
endlichen Akzeptors.
Das ist dann ein bisschen anders.
So, das ist das eine.
Das zweite, achso, was ich noch sagen wollte,
bitte Obacht, also bei rechtslinearen Grammatiken, alle Produktionen
müssen rechtslinear sein.
Sie dürfen das nicht mischen, manche rechtslinear, manche linkslinear.
Wenn Sie das mischen, dann haben Sie wieder solche Sprachen wie die
Menge aller Wörter der Form A hoch K, B hoch K.
Also mischen von rechts- und linkslinear gibt Ihnen mehr.
Und dann kann man sich natürlich fragen, was ist denn, wenn ich in
Produktionen rechts zwei Nicht-Terminal-Symbole erlaube statt nur
eines.
Kann ich dann noch mehr?
Antwort ist ja.
Mit zwei Nicht-Terminal-Symbolen auf den rechten Seiten der Produktion
können Sie mehr als mit nur einem.
Das werden wir jetzt hier nicht vertiefen.
Mit drei Nicht-Terminal-Symbolen auf den rechten Seiten, also maximal,
können Sie aber nicht mehr als mit zwei Symbolen.
Also mit zwei auf den rechten Seiten können Sie mehr als mit einem,
aber danach ist Schluss.
Das nur so am Rande.
So und wir haben ein Beispiel für strukturelle Induktion gesehen.
Und damit sind wir mit diesem Kapitel am Ende.
Am Freitag ist die sogenannte Probeklausur.
Also da sitzen Sie dann halt hier mal und versuchen sich an ein paar
Aufgaben.
Hinweis, es steht auch vorne drauf.
Also interpretieren Sie das bitte nicht so, dass in der richtigen
Klausur auch alle Aufgaben genau so sind oder genau nur die Themen
drankommen wie der Probeklausur.
Natürlich nicht.
Insbesondere, also da die Probeklausur ja von den Tutoren sozusagen
noch in ihrer Freizeit mit korrigiert wird, ist die so gebaut, dass an
einigen Stellen, dass man sie bequem korrigieren kann.
Das heißt, es gibt diverse Stellen, wo Sie einfach was ankreuzen
können.
Solche Ankreuzaufgaben stellen wir heutzutage in Klausuren nicht mehr,
denn vor der Tür steht eine Satzung für, wie geht man mit
Ankreuzaufgaben in Klausuren um.
Und das, was da drin steht, also die Satzung ist ja noch relativ kurz,
aber die Anleitung, wie das zu verstehen ist, ist dreimal so lang.
Wir wollen keine Ankreuzaufgaben mehr in Klausuren.
Bestimmt nie wieder.
Es gibt einfach zu viele kuriose Gerichtsurteile zu Klausuren mit
Ankreuzaufgaben.
Also die richtigen Klausuren sind dann an einigen Stellen doch ein
bisschen anders.
Und außerdem natürlich in der Probeklausur, hier werden viele Leute
dicht aufeinandersitzen.
In richtigen Klausuren ist das auch nicht der Fall.
Da haben wir dann 10 oder 12 oder wie viele Hörsäle und nur in jeder
zweiten Reihe und da nur auf jedem dritten Platz sitzt überhaupt
irgendwer.
Also es ist dann schon nochmal so ein bisschen anderes Feeling, aber
naja.
Trotzdem viel Spaß dabei und bis zur nächsten Woche dann.
Dankeschön.