So, schönen guten Tag, meine Damen und Herren.
Hoffen wir mal, dass das alles jetzt gut gehen wird.
Wir haben das letzte Mal uns mit Turing-Maschinen beschäftigt.
Und heute wollen wir uns mit regulären Ausdrücken beschäftigen und
rechtslinearen Grammatiken.
Aber eigentlich nicht so gerne mit Videokabeln und anderen Dingen.
Also das letzte Mal haben wir Turing-Maschinen gesehen.
Da kann man sich vorstellen, man hat einen endlichen Automaten und
zusätzlich noch dieses unendliche Speicherband.
Und jetzt gehen wir nochmal zurück zu endlichen Automaten und gucken
uns noch etwas an, was zum einen nützlich ist, was Ihnen öfter noch
über den Weg laufen wird, was auch hilfreich sein wird.
Das sind sogenannte reguläre Ausdrücke.
Da müssen Sie also schon mal als Warnung ein bisschen aufpassen.
Das, was wir uns angucken werden in der Vorlesung, ist das, was
klassischerweise reguläre Ausdrücke genannt wird.
Das ist ein bisschen was anderes.
Also reguläre Ausdrücke auf Englisch heißen regular expressions.
Und wenn Sie sich irgendwo heutzutage etwas angucken mit regular
expressions, also da gibt es ein Paket in Java, hier und da und dort
tauchen regular expressions auf.
Das ist im Allgemeinen dann etwas Allgemeineres, etwas, was Ihnen mehr
Ausdrucksmöglichkeiten gibt, als das, was klassisch regular
expression, regulärer Ausdruck hieß.
Also bitte Vorsicht, wir gucken uns nur den harmlosen Fall an, so das
Original in Anführungszeichen.
Und für diese harmlose in Anführungszeichen Varianten, wir werden das
nicht im Detail beweisen, aber wenn Sie sehen, das, was man die
formalen Sprachen, die man mit regulären Ausdrücken beschreiben kann,
das sind genau die, die man auch mit endlichen Automaten erkennen
kann, genau die.
Aber manchmal ist es halt bequemer, einen regulären Ausdruck
hinzuschreiben, als einen endlichen Automaten.
Aus Gründen, die Sie dann vielleicht mal verstehen werden, falls Sie
zum Beispiel Informatik studieren und dann in einem Jahr theoretische
Grundlagen hören.
So, endliche Automaten.
Wenn Sie nochmal in das Kapitel C reingucken, werden Sie sehen, naja,
offensichtlich gibt es formale Sprachen, die kann man mit endlichen
Akzeptoren erkennen.
Wir hatten aber auch von einer Sprache bewiesen, nein, die kann man
nicht mit endlichen Akzeptoren erkennen.
Und dann kann man sich natürlich die Frage stellen, also kann man doch
irgendwie ein besseres Gefühl dafür kriegen, was geht mit endlichen
Akzeptoren.
Und, ja, reguläre Ausdrücke sind eine Möglichkeit.
Das ist das, womit wir uns jetzt hier hauptsächlich beschäftigen
werden.
Rechtslineare Grammatiken sind noch eine andere Möglichkeit.
Das ist ein Spezialfall von kontextfreien Grammatiken.
Damit können Sie auch genau das beschreiben, was Sie mit endlichen
Akzeptoren erkennen können.
Und dann gibt es noch einen dritten Abschnitt in diesem Kapitel, wo
wir dann sozusagen die allgemeinste Form von vollständiger Induktion
uns nochmal so ein bisschen angucken, die wir hier jedenfalls
behandeln, das heißt dann strukturelle Induktion.
Da redet man nicht mehr explizit über Zahlen, also nicht mehr explizit
über Zeigen für 1, 2, 3, 4, 5, aber implizit, das ist immer noch da,
also das ist kein Hexenwerk.
So, reguläre Ausdrücke dienen der Beschreibung von gewisser formaler
Sprachen.
Das geht zurück auf so eine Arbeit von Herrn Klini von 1956.
Und das ist auch der Herr, nach dem dieses Sternchen dann manchmal
auch, habe ich irgendwann mal gesagt, das Sternchen beim
Konkatenationsabschluss heißt auch Klinistar, das ist nach diesem
Herrn hier.
Und wie gesagt, Vorsicht, wir gucken hier nur die harmlose Variante
an, nicht das, was Sie an allen möglichen und unmöglichen Stellen
finden.
Das ist mächtiger.
So, und ein regulärer Ausdruck ist dazu da, eine formale Sprache zu
beschreiben.
Da haben wir also irgendein zugrunde liegendes Alphabet.
Denken Sie an sowas wie ABC oder sowas harmloses.
Und dann hat man in regulären Ausdrücken zusätzlich so fünf
Hilfszeichen.
Die gehören also nicht zu dem Terminalzeichenalphabet, das einen
interessiert, sondern das sind so Hilfssymbole.
Ein senkrechter Strich, Klammer auf, Klammer zu, ein Sternchen und so
eine durchgestrichene Null.
Und also diese Zeichen mögen bitte nicht in dem Alphabet vorkommen,
mit den Zeichen, aus denen wir das zusammensetzen, worüber wir reden
wollen.
Also A und Z seien disjunkt.
So, und dann gibt es Regeln.
Was ist ein regulärer Ausdruck?
Und ich habe es jetzt hier erstmal nochmal wieder verbal
hingeschrieben.
Also erstens, diese durchgestrichene Null ist ein regulärer Ausdruck.
Statt regulärer Ausdruck schreibe ich immer RA.
Jedes einzelne Symbol aus dem Alphabet, das einen eigentlich
interessiert, ist, wenn Sie es einzeln hinschreiben, einfach schon ein
regulärer Ausdruck.
Also wenn Sie ein kleines A hinschreiben, ist ein regulärer Ausdruck.
So, und das sind die kleinsten, sozusagen die atomaren regulären
Ausdrücke.
Und dann gibt es drei Regeln, wie man größere reguläre Ausdrücke aus
kleineren zusammensetzen kann.
Nämlich, wenn Sie schon zwei reguläre Ausdrücke R1 und R2 haben, dann
können Sie auch einen senkrechten Strich zwischen die zwei schreiben.
Außenrum, runde Klammern, auf und zu und fertig ist ein größerer
regulärer Ausdruck.
Also per Definition, das ist wieder einer.
Und einfach direkt hintereinander schreiben, ohne senkrechten Strich,
runde Klammern außenrum, ist auch wieder ein regulärer Ausdruck.
Und wenn Sie schon einen haben, dann können Sie auch noch einen Stern
dahinter machen, hinter den regulären Ausdruck, und auch erstmal
wieder runde Klammern außenrum.
Und dann haben Sie auch wieder einen etwas größeren regulären
Ausdruck, also drei Zeichen mehr.
Und das sind die einzigen Möglichkeiten, reguläre Ausdrücke zu
konstruieren.
Alles, was Sie in endlich vielen Schritten auf diese Art und Weise
basteln können, sind reguläre Ausdrücke und alles andere nicht.
Also meinetwegen, wenn das zugrunde liegende Alphabet A, B ist, dann
elementar, also die durchgestrichene Null ist immer ein regulärer
Ausdruck.
Das kleine a ist im Alphabet, können Sie einfach hinschreiben.
Das kleine b auch, haben Sie drei reguläre Ausdrücke, so die ersten
kleinsten.
Und dann können Sie anfangen, aus kleineren größere zusammenzusetzen,
also meinetwegen a und b hintereinander schreiben, runde Klammern
außenrum.
Oder durchgestrichene Null, b dahinter, runde Klammern außenrum.
Oder a mit der Null dahinter.
Oder dann eben, wenn Sie wissen, a, b in Klammern ist einer, und
dahinter a als ein anderer, runde Klammern außenrum, regulärer
Ausdruck.
Dann können Sie das nehmen, noch ein a dahinter schreiben, runde
Klammern außenrum, regulärer Ausdruck, naja und so weiter.
Oder Sie machen einen senkrechten Strich zwischen zwei reguläre
Ausdrücke, meinetwegen zwischen das a und das b, runde Klammern
außenrum.
Oder Sie machen ein Sternchen hinter irgendwelche Dinge, also a,
Stern, runde Klammern außenrum, ist ein regulärer Ausdruck.
Und hinter dem können Sie dann nochmal einen Stern machen, runde
Klammern außenrum und so weiter und so weiter.
Und so wie wir die Regeln definiert haben, auch wieder sehr schnell
entstehen viele Klammern, die man nicht alles schreiben und lesen
will.
Und deswegen definiert man wieder so Abkürzungsregeln, Klammer
-Einsparungsregeln, nämlich erstens, also das Sternchen bindet
stärker, als irgendwie reguläre Ausdrücke hintereinander schreiben.
Also wenn Sie sowas haben wie r2, r3, Stern, dann bedeutet, ohne die
ganzen Klammern, die offiziell vorgeschrieben sind, dann bedeutet das,
der Stern, der gehört nur zu dem r3.
Also Sie müssen sich eigentlich runde Klammern um r3, Stern, denken.
Und wenn Sie dann irgendwas haben, wo was hintereinander geschrieben
ist, zum Beispiel r2 und r3, Stern, und irgendwo ist was mit einem
Strich dazwischen, dann so in Anführungszeichen Punkt vor Strich,
diese, ich nenne das mal jetzt schon Konkatenation, bindet stärker als
der senkrechte Strich.
Also das ohne Klammern müssen Sie sich eigentlich vorstellen so, dass
das hintere r2, r3, Stern geklammert ist und der Strich steht außen
und davor, das r1.
Und wenn Sie mehrere gleiche hintereinander haben, meinetwegen
implizit, wollen wir anmerken, das bedeutet, die Klammern stehen
möglichst weit links immer.
Was man da sich aussucht, ist egal, denn für das, was reguläre
Ausdrücke bedeuten dann hinterher, nämlich, oder beschreiben, also
formale Sprachen, ist es egal, wie man das definiert hat, hier in dem
letzten Punkt bei mehreren Strichen oder mehreren Punkten.
Und das heißt dann, statt dieses regulären Ausdrucks hier, Klammer
auf, Klammer auf, Klammer auf, a, b, Klammer zu, können Sie einfach a,
b, a, a schreiben.
Man kann nicht offiziell dann beliebig alle Klammern wegnassen, da
müssen Sie ein bisschen aufpassen.
Aber gerade in der letzten Zeile sieht man ja, das spart einem schon
einiges an Klammern.
Okay.
Ja, und alles, was nicht aussieht wie ein regulärer Ausdruck nach den
Vorschriften, ist halt auch keiner.
Also hier so Klammer auf und dann gleich ein senkrechter Strich, das
geht nicht.
Vor einem senkrechten Strich muss ein regulärer Ausdruck stehen.
Und das leere Wort ist kein regulärer Ausdruck.
Also da muss irgendwas stehen.
Und einfach irgendwas in senkrechte Striche einklammern geht nicht.
Und in Zwischenrunden Klammern, wenn man sie denn hat, muss was
Vernünftiges stehen.
Und die Klammern müssen ordentlich paarweise so ineinandergeschachtelt
sein, wie man sich das vorstellt.
Und es dürfen auch nur die Symbole vorkommen, über die man reden will.
Also wenn Sie da einfach ein C hinschreiben und sagen, mich
interessieren reguläre Ausdrücke über dem Alphabet AB, ist halt auch
verkehrt.
So, das, was wir gerade verbal gemacht haben, so was sind reguläre
Ausdrücke?
Das hat Sie vielleicht an arithmetische Ausdrücke erinnert oder was
auch immer.
Und dann haben Sie vielleicht schon dran gedacht, das haben wir doch
auch mal mit kontextfreien Grammatiken festgelegt, was syntaktisch
korrekt ist.
Und in der Tat, Sie können auch hier eine kontextfreie Grammatik
angeben, die festlegt, was sind syntaktisch korrekte reguläre
Ausdrücke.
Also alles, was Sie in dieser Grammatik ableiten können, sind
syntaktisch korrekte reguläre Ausdrücke.
Aber bitte Achtung, wichtig, deswegen habe ich das nicht gleich auf
die erste Folie gemalt, was diese Grammatik festlegt, diese
kontextfreie Grammatik ist nur die Syntax von regulären Ausdrücken.
Das sagt gar nichts darüber aus, was man mit regulären Ausdrücken
beschreiben kann.
Und diese Grammatik ist also ganz harmlos.
Es gibt nur ein Nicht-Terminalsymbol, das habe ich R genannt, und aus
R können Sie ableiten.
Die atomalen regulären Ausdrücke, durchgestrichene Null, jedes
einzelne Symbol in A, und Sie können aus R ableiten, Klammer auf, R
ist engerichtet, Strich R, Klammer zu, und Klammer auf, R, R, Klammer
zu, und Klammer auf, R, Stern, Klammer zu.
Und wenn Sie das an wohlgeformte Klammerausdrücke aus Kapitel 12
erinnert, das mit der 12 musste ich auch mal abgucken.
Also, als wenn Sie sich an wohlgeformte Klammerausdrücke erinnern, na
ja, da liegen Sie genau richtig.
Das ist hier im Prinzip das Gleiche.
Und wenn Sie die Grammatik haben, dann können Sie natürlich jeden
regulären Ausdruck auch hinmalen, sozusagen für jeden regulären
Ausdruck den Ableitungsbaum.
Der ist dann übrigens eindeutig bei der Grammatik, die ich Ihnen da
gerade hingemalt hatte.
Also, hier wäre zum Beispiel der Ableitungsbaum für A-Stern, B-Stern,
in Klammern Stern.
Das ist ein regulärer Ausdruck.
Da ist ein Stern und davor steht ein regulärer Ausdruck.
Der ist nämlich das Produkt, also hintereinander geschrieben, zwei
reguläre Ausdrücke A-Stern und B-Stern.
Und da ist der Ableitungsbaum.
Und wofür tut man das?
Man will mit regulären Ausdrücken formale Sprachen beschreiben, also
Ausdrücken, Wörter, welcher Bauart sind in Ordnung, also genügen
diesem einem vorgegebenen regulären Ausdruck.
Und deswegen definieren wir also für jeden regulären Ausdruck, was ist
die formale Sprache, die er beschreibt.
Und wir hatten reguläre Ausdrücke gerade eben so konstruiert,
definiert.
Es gibt Atomare, die durchgestrichenen Nullen und einzelne Symbole und
drei Regeln, wie man aus kleinen regulären Ausdrücken größere baut.
Und entlang dieser Definition handelt man sich jetzt auch, wenn man
festlegt, was bedeutet das Ganze denn?
Und die Bedeutung von der durchgestrichenen Null, also für einen
regulären Ausdruck, die dadurch beschriebene formale Sprache, da
schreiben wir jetzt mal den regulären Ausdruck in spitzen Klammern,
und die formale Sprache, die durch die durchgestrichene Null
beschrieben wird, ist die leere formale Sprache.
Da ist gar nichts drin.
Wenn Sie ein einzelnes Symbol hinschreiben, klein a oder klein b oder
was auch immer, dann bedeutet das die formale Sprache, in der genau
ein Wort ist, nämlich dieses einzelne Symbol, dieses Wort der Länge 1.
Wenn Sie zwei reguläre Ausdrücke hinschreiben mit einem senkrechten
Strich dazwischen, die Bedeutung davon ist einfach die Vereinigung der
Dinger, die durch R1 bzw.
R2 beschrieben werden.
Also den senkrechten Strich können Sie sozusagen als oder immer lesen.
Das tue ich dann auch meistens.
Die Wörter, die Sie kriegen, sind entweder durch R1 beschrieben oder
durch R2.
Und wenn Sie ohne alles zwei reguläre Ausdrücke hintereinander
schreiben, die Bedeutung ist einfach Produkt der formalen Sprachen, so
wie wir es definiert haben.
Und die Bedeutung von R-Stern, ganz große Überraschung, ist Bedeutung
von R-Stern.
Also Konkatenationsabschluss dessen, was durch R beschrieben wird.
Also drei einfache Beispiele.
A, senkrechtes Strich, B.
Also ich nehme immer an, ja, das zugrunde liegende Alphabet enthält
klein a und klein b.
Was ist dann die formale Sprache, die dadurch beschrieben wird?
Das ist laut Definition von eben, wenn man was hat mit dem senkrechten
Strich dazwischen, Vereinigung der formalen Sprachen, die durch ein a
bzw.
ein einzelnes b beschrieben werden.
Das sind die formalen Sprachen, die jeweils ein Wort enthalten,
nämlich das a und das b.
Und wenn Sie das vereinigen, haben Sie halt diese Menge, die a und b
enthält.
Nicht aufregend, ja?
Wenn Sie dann a senkrechtes Strich b in Klammern Stern haben, was ist
die Bedeutung davon?
Da sagte die Regel eben, oh, wenn man dann regulären Ausdruck hat mit
dem Stern am Ende, die Bedeutung ist der Konkatenationsabschluss
dessen, was durch den Unterausdruck a Strich b beschrieben wird.
Naja, das hatten wir uns gerade überlegt, das ist a b.
Also durch a senkrechtes Strich b in Klammern Stern wird beschrieben
a, b Konkatenationsabschluss.
Mit anderen Worten, die Menge aller Wörter aus a's und b's.
Hier ist ein dritter regulärer Ausdruck, Klammer auf, a Stern, b
Stern, Klammer zu Stern.
Was ist das?
Bedeutung von dem regulären Ausdruck, naja, das ist der
Konkatenationsabschluss dessen, was durch den regulären Ausdruck a
Stern b Stern beschrieben wird.
Da stehen zwei reguläre Ausdrücke hintereinander, das ist also Produkt
der formalen Sprachen, die durch a Stern bzw.
b Stern beschrieben werden.
Das ist a Stern bzw.
b Stern.
Also die formale Sprache, die durch diesen regulären Ausdruck
beschrieben wird, ist a Stern, b Stern in Klammern Stern.
Sie sehen, da passiert nicht viel, ja.
Aber wenn Sie jetzt mal ein bisschen nachdenken über diese letzte
formale Sprache, wie sie hier steht, welche Wörter sind da so drin?
Also fangen wir mal ganz banal an.
Sind da überhaupt Wörter drin?
Wer ist für ja?
Alle, aha, genau.
Das sind alle Wörter, denn egal welches Wort Sie nehmen, jedes Wort
können Sie zerhacken in so Blöcke der Form erst ein paar a´s und dann
ein paar b´s.
Also gehen Sie das Wort einfach durch von vorne bis zum letzten b.
Also nehmen wir mal an, es kommt ein b vor, ja.
Also bis zum ersten Mal nach einem b wieder ein a kommt, da zerhacken
Sie, dann haben Sie den ersten Block aus a´s und b´s und dann ein
zweiter.
Und Sie können ja beliebig oft so ein Wort haben, das von der Bauart
ist, erst ein paar a´s, dann ein paar b´s.
Jedes Wort können Sie so auffassen.
Sie können sogar im Extremfall immer sagen, als jeden Block einzeln,
nehme ich immer ein einzelnes Zeichen, egal ob das ein a oder ein b
ist.
Das ist immer von der Bauart a-Stern, b-Stern, ein a und null b´s oder
null a´s und ein b, ja.
Also Sie können das Wort auch unterschiedlich noch zerhacken.
Also das gibt die gleiche formale Sprache wie da oben.
Das sind einfach alle Wörter.
Und da sehen Sie, man kann die gleiche formale Sprache durchaus
mithilfe unterschiedlicher regulärer Ausdrücke beschreiben, den man
vielleicht nicht gleich ansieht, ob Sie das gleiche beschreiben oder
nicht.
Wenn Sie für einen regulären Ausdruck den Ableitungsbaum gemäß dieser
Grammatik von vorhin haben, dann können Sie da auch irgendwie relativ
leicht sozusagen ausrechnen, was wird denn beschrieben.
Sie gehen einfach von unten nach oben hoch, schreiben erstmal an die
Blätter, was beschreiben die und hangeln sich dann so hoch.
Jedes Nicht-Terminalsymbol in dem Ableitungsbaum, für welche formale
Sprache steht es denn?
Das unterste R hier steht für b und dann mit dem Stern dahinter, das
steht dann für den Konkatenationsabschluss von b und dann das da oben
für den Produkt und dann ganz oben das für den Konkatenationsabschluss
davon.
Das ist ganz ähnlich, wie Sie arithmetische Ausdrücke auswerten.
Wenn Sie da einen großen irgendwo stehen haben auf dem Zettel, Sie
fangen halt innen aus, rechnen erstmal unter Ausdrücke, die
eingeklammert sind, aus und dann setzen Sie so nach und nach das
Ergebnis zusammen.
So, wir haben gerade gesehen, es gibt manchmal verschiedene reguläre
Ausdrücke, die die gleiche formale Sprache beschreiben.
Da haben wir gerade mit hingucken gesehen, ja, in dem Beispiel, die
beschreiben die gleiche.
Kann man das im Allgemeinen überprüfen?
Ja, kann man.
Es gibt da Verfahren, sogar ein relativ plausibel aussehendes.
Also wir werden gleich noch ein bisschen Ergebnisse sehen, aus denen
folgt das dann relativ harmlos.
Aber, naja, also das ist die eine Frage, die ich da nicht stellen kann
und ich habe Ihnen das letzte Mal schon gesagt, ja, ja, das geht, da
wussten wir noch nicht, was reguläre Ausdrücke sind, aber übrigens,
das ist eines der schwierigen Probleme in einer Komplexitätsklasse,
die PSPACE heißt.
Und die andere Frage ist, also welche formalen Sprachen kann man denn
überhaupt beschreiben?
So, zur Äquivalenz.
Nochmal hier der Hinweis, das ist ein Problem, das ist in PSPACE und
zwar ein sogenanntes PSPACE-vollständiges Problem, was auch immer
Vollständigkeit hier bedeutet, das lernen Sie in Theoretische
Grundlagen.
Das heißt anschaulich, das ist sozusagen am Rand von PSPACE, das
gehört zu den schwierigsten, in einem gewissen präzisen Sinne, zu den
schwierigsten Problemen, die noch in PSPACE sind.
Und die Beobachtung ist, für diese Probleme, man hat noch keinen
Algorithmus gefunden, der halbwegs erträgliche Laufzeit hat.
Alle Algorithmen, die man kennt, vielleicht war man nur zu blöd,
bessere zu finden, aber alle, die man bisher kennt, haben
exponentielle Laufzeit, sagen wir mal, oder jedenfalls sehr, sehr,
sind sehr, sehr langsam.
Und man weiß nicht, ob es vielleicht doch Algorithmen gibt, die dieses
Problem, zwei reguläre Ausdrücke, beschreiben Sie die gleiche formale
Sprache, in Polynomialzeit lösen.
Dann, einfach weil das auch manchmal vorkommt, nehmen Sie als Beispiel
den regulären Ausdruck AB und dann AB-Stern, was bedeutet das?
Na ja, da muss also erst einmal AB kommen und dann 0, 1, 2, 3,
beliebig oftmal, wiederholt nochmal immer AB, AB, AB.
Und das ist nichts anderes, als das, was wir mit AB-Plus beschrieben
hatten.
Ja, beliebig viele Faktoren aus AB, aber mindestens einer.
Und weil man das auch manchmal gerne ausdrücken möchte, auch wenn der
reguläre Ausdruck nicht so kurz AB ist, sondern so eine Zeile lang
ist.
Und jetzt will man sagen, sowas wie Stern, aber nicht der Fall
Nullwiederholungen, dann will man nicht das zweimal hintereinander
schreiben.
Deswegen führt man dann manchmal noch so Abkürzungen ein, wie man
erlaubt, auch einen Plus in regulären Ausdrücken mit der naheliegenden
Bedeutung.
Dann die durchgestrichene Null mit einem Stern dahinter, was ist das?
Na ja, das ist der Konkatenationsabschluss dessen, was durch die
durchgestrichene Null beschrieben wird, das ist die leere Sprache.
Und Konkatenationsabschluss der leeren Sprache per Definitionen ist
die Sprache, die enthält das leere Wort und nur das leere Wort.
Das heißt, wenn Sie einen regulären Ausdruck haben und irgendwo steht
senkrechter Strich durchgestrichene Null Stern, dann heißt das, man
möchte gerne die Wörter haben, die durch den regulären Ausdruck vor
dem Strich beschrieben sind.
Und zusätzlich erlaubt man noch das leere Wort.
Mit anderen Worten, so ein regulärer Ausdruck beschreibt irgendwie so
eine Situation.
Da kann ABC jetzt in diesem Beispiel stehen oder halt nicht.
Das leere Wort.
Also irgendwie hier kann etwas stehen oder nicht.
Das ist irgendwie optional, dass das da auftaucht an der Stelle.
Das kann ja auch Teil in einem größeren regulären Ausdruck sein.
Und weil man das auch öfter mal ausdrücken will und dann nicht diese
komische Konstruktion machen will, gibt es dann noch Varianten, wo
auch vielleicht sowas wie ein Fragezeichen hinter einem regulären
Ausdruck erlaubt ist.
Und das bedeutet dann genau das, die beschriebene formale Sprache ist,
also das, was durch R beschrieben wird, oder das leere Wort.
Das, was durch R beschrieben ist, sowas darf da stehen oder auch
nicht.
Also wenn Sie sowas wie reguläre Ausdrücke irgendwo mal sehen und da
taucht ein Plus oder ein Fragezeichen auf, dann wissen Sie, was das
soll.
Da kann vielleicht auch noch was anderes auftauchen, da müssen Sie
dann halt nachlesen.
So, kleines Beispiel.
Datumszeitangaben in E-Mails sind irgendwo offiziell spezifiziert.
Und das steht irgendwo in einem RFC, wo viel festgelegt wird über E
-Mails.
Und weil da einige Dinge ein bisschen komplizierter festzulegen sind,
werden da nicht einfach reguläre Ausdrücke benutzt, sondern etwas
namens Augmented Bacchus-Nauer-Form, was auch immer das sein mag.
Aber für E-Mails, im Wesentlichen sagt die Spezifikation, hier ist ein
regulärer Ausdruck, der sagt, wie eine Datumsangabe aussieht.
Hier ist ein Beispiel.
Wochentag, Komma, Tag, Monat, Jahr, Uhrzeit und dann noch was, was die
Zeitzone angibt.
Und wenn Sie da in den RFC reingucken, wo es um Date-and-Time
-Specification geht, dann steht da fast wörtlich, also ich habe jetzt
nicht alles abgeschrieben und vielleicht an der einen oder anderen
Stelle ein bisschen vereinfacht, dann steht da sowas hier.
Und gucken wir uns mal einen Teil davon, gucken wir mal zwei Zeilen
raus, da steht irgendwo Time of Day gleich, Hour, Gänsefüßchen,
Doppelpunkt, Gänsefüßchen, Minute, eckige Klammer auf, Gänsefüßchen,
Doppelpunkt, Doppelpunkt, Minute, eckige Klammer zu und irgendwo
steht, Hour ist gleich Two-Digit.
Und da haben Sie also mehr so Zeilen von dieser Bauart und das dürfen
Sie jetzt hier in diesem eingeschränkten Fall einfach so
interpretieren, dass rechts vom Gleichheitszeichen sozusagen sowas wie
ein regulärer Ausdruck dasteht.
Und links von dem Gleichheitszeichen steht der Name, den der reguläre
Ausdruck bekommt, also da werden reguläre Ausdrücke hingeschrieben und
die kriegen Namen und dann darf eben rechts vom Gleichheitszeichen in
so einem regulären Ausdruck, in Anführungszeichen, halt auch der Name
eines anderen regulären Ausdrucks stehen, damit da nicht so ein langes
Gebilde steht, sondern ein Name, der ausdrückt, naja, was ist denn
hier gemeint.
Also zum Beispiel in der ersten Zeile steht hier irgendwo Hour und das
ist an der anderen Zeile definiert als Name für einen regulären
Ausdruck, der hat noch wieder Namen, Two-Digit.
Und wenn Sie irgendwo anders dann hinreichend lange bühlen, stellen
Sie fest, Two-Digit ist eine Abkürzung für Digit-Digit, also zwei
hintereinander und Digit ist Abkürzung für den regulären Ausdruck 0
oder 1 oder 2 oder 3 oder 4 oder 5 oder 6 oder 7 oder 8 oder 9.
Und das bedeutet, also die formale Sprache, die durch Hour festgelegt
ist, das sind also alle Folgen von zwei Ziffern, also von 00 bis 99.
Das sind sozusagen die offiziellen Stundenangaben.
Und Time of Day, da steht dann also, da muss eine Stunde stehen, dann
etwas in Gänsefüßchen heißt, hier soll ein Doppelpunkt stehen,
wörtlich, so, Doppelpunkt ist Symbol des Alphabets, darf da stehen.
Und dann für Minute ist auch wieder was definiert und etwas in eckigen
Klammern in dieser Notation bedeutet, ja, das kann da auch noch
stehen, was zwischen den eckigen Klammern steht.
Oder es darf fehlen, optional.
Also wie man das mit normalen regulären Ausdrücken ausdrückt, hatten
wir auch gerade.
Und das heißt, Time of Day ist sozusagen beschrieben durch so einen
regulären Ausdruck, hour, Doppelpunkt, Minute oder hour, Doppelpunkt,
Minute, Doppelpunkt, Second.
Und hier sind Beispiele.
Und eben hour muss aus zwei Ziffern bestehen.
Also wenn Sie da 9 Doppelpunkt 50 hinschreiben, dann ist das keine
syntaktisch korrekte Zeitangabe, weil die Stunde nur eine Ziffer hat
und nicht zwei.
Also das ist syntaktisch falsch.
Aber 39 Doppelpunkt 71 ist eine syntaktisch korrekte Zeitangabe.
Ist halt so, ja.
Der Mail-Client sollte halt dann bitte immer die richtige Zeit da
reinschreiben und nicht so ein Quatsch.
Und die richtige Zeit, da wird das halt nicht passieren.
Gut.
Was haben jetzt reguläre Ausdrücke mit endlichen Automaten zu tun und
mit Grammatiken?
Hier steht eine zentrale Aussage, die wir jetzt hier nicht beweisen
werden.
Aber Sie sollten sie zumindest mal gesehen haben.
Nämlich wenn Sie eine formale Sprache haben, dann sind drei Fälle
völlig äquivalent.
Erste Möglichkeit, es gibt einen endlichen Akzeptor, der genau diese
formale Sprache akzeptiert.
Solche Sprachen gibt es.
Und es gibt auch Sprachen, die nicht so sind.
Und wenn es einen endlichen Akzeptor gibt, dann und nur dann können
Sie auch die gleiche formale Sprache durch einen regulären Ausdruck
beschreiben.
Also Sie können sicher sein, wenn es einen endlichen Automaten gibt,
dann gibt es auch einen regulären Ausdruck und umgekehrt.
Und drittens, wenn die Sprache von einem endlichen Akzeptor erkannt
wird, dann gibt es auch eine sogenannte rechtslineare Grammatik, die
diese Sprache erzeugt.
Rechtslineare Grammatiken sind ein Spezialfall von kontextfreien
Grammatiken.
Das gucken wir uns gleich noch an.
So, und wenn eine Sprache diese Eigenschaften hat, also durch
endlichen Akzeptor erkennbar, durch regulären Ausdruck beschreibbar,
mit einer rechtslinearen Grammatik erzeugbar, dann heißt so eine
Sprache auch regulär.
Und weil diese rechtslinearen Grammatiken ein Spezialfall von
kontextfreien Grammatiken sind, ist also jede reguläre Sprache
automatisch kontextfrei.
Aber die Umkehrung gilt nicht, wenn man den Satz da oben glaubt, die
formale Sprache aller Wörter der Form A hoch K, B hoch K.
Von der haben wir bewiesen, dass es keinen endlichen Akzeptor gibt,
der die erkennt.
Und wenn der Satz da oben stimmt und er stimmt, dann gibt es auch
keine rechtslineare Grammatik, die genau das erzeugt.
Und das heißt, mit rechtslinearen Grammatiken können Sie weniger
erzeugen als mit kontextfreien Grammatiken.
Das ist eine echte Einschränkung.
Gut.
Wie beweist man das?
Also man muss beweisen, die Aussage 1 ist äquivalent zu 2 und 2 ist
äquivalent zu 3 und 3 ist äquivalent zu 1.
Das klingt erstmal nach 6 Richtungen, von 1 nach 2, von 2 nach 1, von
2 nach 3, von 3 nach 2, von 1 nach 3, von 3 nach 1.
Aber es reicht die Hälfte der Arbeit.
Sie müssen nur zeigen, wenn es einen endlichen Automaten gibt, dann
gibt es einen regulären Ausdruck.
Das werden wir nicht beweisen.
Das ist so mäßig anspruchsvoll, sage ich mal.
Und wenn Sie sich dann irgendwann mal den Standardbeweis sehen, dann
vielleicht werden Sie erinnert an den Algorithmus von Herrn Warschall
über Wegematrix ausrechnen.
Also man kommt vom endlichen Akzeptor zum regulären Ausdruck.
Man kommt vom regulären Ausdruck auch immer zu einer rechtslinearen
Grammatik.
Was das ist, sehen wir wie gesagt gleich.
Das ist mehr Schreibarbeit als Denkarbeit.
Also das ist sehr leicht zu verstehen.
Und dann zeigt man noch, von einer rechtslinearen Grammatik komme ich
zurück zu einem endlichen Akzeptor.
Also wenn Sie mir eine rechtslineare Grammatik geben, dann kann ich
einen endlichen Akzeptor daraus konstruieren, der genau das
akzeptiert, was die Grammatik erzeugt und nichts anderes.
Das ist am kniffligsten.
Und warum das so ist, das werden Sie wieder im dritten Semester
wahrscheinlich in theoretischen Grundlagen sehen.
Und jetzt für die Rückrichtungen braucht man, für die anderen drei
muss man nichts mehr tun, denn da kann man sich immer behelfen.
Also wenn Sie jetzt gerne von endlichem Akzeptor zu rechtslineare
Grammatik wollen, dann gehen Sie halt einfach den Umweg über den
regulären Ausdruck, dann sind Sie da.
Das ist vielleicht nicht die effizienteste Konstruktion, aber es zeigt
Ihnen, es geht.
Und vom regulären Ausdruck zum endlichen Akzeptor gehen Sie halt über
die Grammatik.
Also man muss nur drei Implikationen zeigen und nicht sechs.
So, ja und eine Andeutung von Beweis für einen Teil sehen wir dann
gleich noch, aber im Großen und Ganzen lassen wir das hier.
Also jetzt wissen Sie, was reguläre Ausdrücke sind, jedenfalls gemäß
der klassischen Definition.
Also man hat Konkatenation, den senkrechten Strich, also Vereinigung
und den Sternenkonkatenationsabschluss.
Mehr nicht.
Bitte Vorsicht, die Tatsache, dass man irgendetwas nicht
offensichtlich hat, heißt nicht, dass man es nicht ausdrücken kann.
Manchmal schon, aber nicht immer.
Also zum Beispiel haben wir keine Notation bei regulären Ausdrücken
eingeführt für Durchschnitt.
Also Sie können nicht naheliegend ausdrücken, ich meine die Wörter,
die sowohl durch den einen regulären Ausdruck als auch durch den
anderen beschrieben werden.
Gleichwohl kann man, also wenn man so etwas beschreiben möchte, obwohl
man nichts hat für Durchschnitt, man kann das auf Umwegen immer
ausdrücken.
Genauso für Negation, da steht, man hat keine Notationsmöglichkeit
für, ich meine alle Wörter, die nicht von der folgenden Bauart sind,
braucht man auch nicht.
Also wenn Sie einen regulären Ausdruck haben für etwas, Sie können
auch immer automatisch einen regulären Ausdruck bauen, also der nur
die Mittel zur Verfügung hat, die wir halt haben, der genau das
Gegenteil, das Kompliment der ursprünglichen formalen Sprache
beschreibt.
Aber das ist bei regulären Ausdrücken nicht naheliegend.
Und warum das nicht naheliegend ist, das merken Sie dann auch im
dritten Semester vielleicht mal.
Also wie gesagt, wenn die Sprache regulär ist, kann man vor die
Aufgabe gestellt werden, einen regulären Ausdruck hinzuschreiben, was
dann schwierig ist, wenn die Beschreibung über so etwas wie
Durchschnitt oder Negation benutzt, weil Sie die nicht haben explizit
als Notationsmöglichkeit in regulären Ausdrücken.
Das ist halt ein bisschen kniffliger.
Oder umgekehrt, der reguläre Ausdruck steht da, man finde eine
vielleicht umgangssprachliche, einfache Beschreibung, dessen der
Wörter...
Ich habe jetzt schon mehrfach gesagt, ja, da gibt es diese
rechtslinearen Grammatiken.
Was ist das?
Ich hatte gerade schon gesagt, also wir unterstellen jetzt immer
völlig zu Recht, der Satz von eben ist richtig, also wenn es endlich
einen Akzeptor gibt, genau dann gibt es eine rechtslineare Grammatik.
Und mit einer normalen kontextfreien Grammatik können Sie diese
formale Sprache A hoch K, B hoch K problemlos erzeugen.
Bauen Sie einfach nur ein, nicht Terminalsymbol, Staatssymbol X,
können Sie ersetzen durch A, X, B oder Y.
Fangen Sie an, solange Sie dieses X ersetzen durch A, X, B anwenden,
erzeugen Sie immer vorne ein A, hinten ein B, das bleiben immer gleich
viele und irgendwann machen Sie das einzige Nicht-Terminalsymbol, was
Sie haben, die ganze Zeit in der Mitte, das machen Sie weg, ersetzen
es durch Y und was Sie abgeleitet haben, sind genau diese Wörter A
hoch K, B hoch K.
So, diese Sprache ist nicht regulär.
Wir haben bewiesen, es gibt keinen endlichen Akzeptor.
Und das heißt, also mit dieser Grammatik kann man etwas, was man
sozusagen, salopp gesagt, nicht mit endlichen Akzeptoren kann.
Frage, kann man jetzt die Grammatiken noch einschränken, so dass
alles, was mit der Grammatik geht, auch mit endlichen Akzeptoren geht?
Naja, da kann man nicht mehr viel einschränken, wie Sie sehen.
Wir haben hier nur ein Nicht-Terminalsymbol, wir haben nur zwei
Produktionen und bei der einen Produktion kommt auf der rechten Seite
nur das leere Wort vor und bei der anderen kommt nur ein Nicht
-Terminalsymbol vor.
Was kann man da noch einschränken?
Naja, die Stelle, wo das Nicht-Terminalsymbol erlaubt ist, an der
rechten Seite, daran kann man noch drehen und das macht man bei
rechtslinearen Grammatiken.
Eine Grammatik heißt rechtslinear, wenn alle Produktionen von einer
der folgenden Formen sind.
Entweder auf der rechten Seite kommt überhaupt kein Nicht
-Terminalsymbol vor, also da steht dann ein Wort aus Terminalzeichen
oder das leere Wort ist auch aus T-Stern.
Also rechte Seite ist einfach nur ein Wort aus T-Stern.
T ist das Alphabet der Terminalsymbole.
Oder, also wenn man nur solche Produktionen hätte, da man nur endlich
viele Produktionen haben darf, könnte man nur endlich viele Wörter
erzeugen.
Das ist ein bisschen langweilig.
Also mindestens ein Nicht-Terminalsymbol auf der rechten Seite will
man schon ab und zu mal haben.
Und die Einschränkung bei rechtslinearen Grammatiken ist, deswegen
heißt das rechtslinear, das Nicht-Terminalsymbol, wenn eins vorkommt,
auf der rechten Seite einer Produktion.
Also erstens, es darf nur eins vorkommen und nicht mehrere.
Und zweitens, es muss ganz am Ende der rechten Seite vorkommen.
Hinter dem Nicht-Terminalsymbol darf kein Terminalsymbol mehr stehen.
Also die rechte Seite ist dann von der Form wieder so ein Wort W aus T
-Stern und am Ende ein Nicht-Terminalsymbol.
Und das W kann leer sein.
Also Sie können auch einfach X durch Y ersetzen.
Das ist rechtslinear.
Also das Wort rechts kommt daher, dass auf der rechten Seite das Nicht
-Terminalsymbol am rechten Ende steht.
Und das linear kommt daher, dass da tatsächlich nur ein Nicht
-Terminalsymbol auftaucht, höchstens in einer Produktion.
Im Allgemeinen bei kontextfreien Grammatiken, es dürfen auch mehr
Nicht -Terminalsymbole auftauchen auf einer rechten Seite.
Und wenn Sie da von mehr das einschränken auf nur maximal ein Nicht
-Terminalsymbol, dann macht man da schon eine Einschränkung.
Das lassen wir hier mal offen, wieso und wie und was.
Also dann können Sie schon echt weniger formale Sprachen erzeugen.
Und wenn Sie dann noch verlangen, das Nicht-Terminalsymbol muss am
rechten Ende stehen, dann kann man noch weniger.
Behauptung ist, mit diesen rechtslinearen Grammatiken können Sie
tatsächlich nur noch reguläre Sprachen erzeugen.
Also das, was Sie mit endlichen Automaten akzeptieren können.
Ja, hier ist ein einfaches Beispiel für eine rechtslineare Grammatik.
Also wieder nur ein Nicht-Terminalsymbol.
Das können Sie ersetzen durch ABX oder BBAX oder Y.
Was kann man mit der Grammatik ableiten?
Also man fängt an mit dem Startsymbol X.
Und dann jedes Mal, wenn Sie das anwenden, also am Anfang steht da nur
ein X, das steht am rechten Ende dessen, was Sie bisher haben.
Da steht ja nur das X.
Und wenn Sie jetzt dieses Nicht-Terminalsymbol ersetzen, gemäß einer
Produktion, dann alles, was links davon steht, das fassen Sie gar
nicht an.
Und das Nicht-Terminalsymbol ganz rechts ersetzen Sie durch etwas, da
stehen vielleicht ein paar Terminalsymbole, und dann wieder am rechten
Ende Nicht-Terminalsymbol.
Also was Sie hier tun, ist immer, Sie erzeugen jedes Mal, wenn Sie X
ersetzen, solange Sie es nicht durch Y ersetzen, Sie erzeugen ABX oder
BBAX.
Also Sie erzeugen immer so einen Block AB oder BBA.
Das können Sie sich in jedem Schritt aussuchen, was Sie da tun.
AB, AB, AB, BBA, AB, BBA...
Und irgendwann X ersetzen durchs leere Wort und weg ist es.
Und was haben Sie abgeleitet?
Ein Wort, das aus lauter Blöcken besteht und jeder ist AB oder BBA.
Und davon beliebe ich viele.
Das heißt, was diese Grammatik erzeugt, können Sie beschreiben durch
diesen regulären Ausdruck, jetzt erstmal so, wenn man es sich so
anguckt, beliebe ich oft einen Block, der entweder AB ist oder BBA.
Das ist jetzt hier mit angucken ganz einfach.
Ah, das habe ich vorhin vergessen zu sagen, jetzt blätter ich nochmal
ein paar Folien zurück.
Oh, viele Folien.
Dieser Satz hier, endliche Automaten, reguläre Ausdrücke und
rechtsliniere Grammatiken sind äquivalent, alle diese drei Schritte
sind konstruktiv.
Sie können das in Automaten, also Maschine erledigen lassen, stecken
endlich einen Automaten rein, regulärer Ausdruck kommt raus.
Sie stecken einen regulären Ausdruck rein, rechtsliniere Grammatik
kommt raus und so.
Allerdings, also wenn Sie das nicht mit hingucken, sondern konstruktiv
machen, in mindestens einem dieser drei Schritte werden die Gebilde
auf einmal sehr groß.
Und das ist auch erzwungen.
Das kann man auch beweisen.
Und sehr groß heißt,
aus etwas, jetzt salopp, der Größe n wird etwas der Größe 2 hoch n.
Das kann man nicht vermeiden.
Das heißt, wenn Sie hier hinten jetzt die Grammatik genommen hätten
und hätten sie in den naheliegenden Automatismus reingesteckt, in die
Konstruktion, mach mir einen regulären Ausdruck, da wäre nicht das da
rausgekommen, der nicht mehr auf die Folie passt.
Die werden wirklich ziemlich schnell, ziemlich groß.
Aber es sind die richtigen regulären Ausdrücke zum Beispiel.
So, also hier ist ein Beispiel.
Hier ein Beispiel, das greift nochmal was auf aus dem Kapitel über
endliche Akzeptoren.
X ersetzt zwei Nicht-Terminalsymbole.
X ist das Startsymbol, können Sie ersetzen durch AX oder BX.
Das heißt, am Anfang, Sie können erstmal A und B bunt durcheinander
erzeugen.
Jedes Wort, das Sie wollen.
Und wenn Sie irgendwann fertig werden wollen, also fertig sein mit der
Ableitung, müssen Sie irgendwann das X loswerden.
Und die einzige Möglichkeit ist dann, das X zu ersetzen durch ABABBY.
Das heißt vorne, Sie können X beliebiges erzeugen, aber dann müssen
Sie zwangsweise als nächstes aus dem X ABABBY machen.
Damit dieses Teilwort ABABBY in dem, was Sie ableiten, auf jeden Fall
einmal vorkommt.
Und dann haben Sie hier hinten Y und mit dem Y können Sie wieder
beliebiges Durcheinander von A's und B's erzeugen und dann irgendwann
wegmachen.
Das heißt, mit der Grammatik können Sie alle Wörter erzeugen, wo
irgendwo an mindestens einer Stelle einmal ABABBY als Teilwort
vorkommt.
Dafür hatten wir auch einen endlichen Automaten gebaut.
Hier haben Sie eine rechtslineare Grammatik
mit etwas Beliebiges vorne, dann dieses Teilwort ABABBY und dann
dahinter wieder etwas Beliebiges.
Und wenn das Alphabet AB ist, beliebig heißt A oder B in runden
Klammern Stern.
Sie erinnern sich.
Und nochmal zu unserem Beispiel mit dieser Grammatik, die die Wörter
der Form A hoch K, B hoch K erzeugt.
Da sehen Sie also, da hatten wir die eine Produktion X ersetzen durch
AXB, da sehen Sie, das X steht nicht am rechten Ende.
Die Grammatik, die Sprache, die erzeugt wird, ist auch nicht regulär.
Das heißt, Sie können auch sicher sein, Sie werden keine rechtslineare
Grammatik finden, die die gleiche formale Sprache erzeugt.
Und da merkt man, naja, hinter diesem Satz, diese Äquivalenz von
endlichen Automaten, regulären Ausdrücken und rechtslinearen
Grammatiken, irgendwo muss da vielleicht doch irgendwie so ein
bisschen Arbeit drinstecken, um zu beweisen, es gibt keine
rechtslineare Grammatik, die A hoch K, B hoch K erzeugt.
Naja, das könnten Sie schon hinkriegen, aber man muss schon ein
bisschen was tun.
Gut.
Solche rechtslinearen Grammatiken heißen auch Typ-3-Grammatiken.
Normale, in Anführungszeichen, kontextfreie Grammatiken heißen auch
Typ -2-Grammatiken.
Es gibt auch Typ-1- und Typ-0-Grammatiken.
Nur, dass Sie das vielleicht so ganz vage im Hinterkopf behalten.
Und von Typ-3 nach Typ-2, das ist also eine Verallgemeinerung, ja, da
kann man mehr erzeugen.
A hoch K, B hoch K können Sie nur mit Typ-2, nicht mit Typ-3.
Und so geht es auch weiter.
Mit Typ-1-Grammatiken können Sie mehr als mit Typ-2-Grammatiken.
Da können Sie nämlich im Wesentlichen ausdrücken,
dass Sie Ersetzungen ausdrücken, wie X ersetzen durch A, X, B.
Aber Sie können zusätzlich sagen, ja, aber das X möchte ich nur dann,
ich möchte nur erlauben, dass X dann durch A, X, B ersetzt werden
kann, wenn links neben dem X noch ein C steht oder so etwas.
Also da haben Sie mehr Ausdruckmöglichkeiten, da können Sie noch mehr.
Und bei Typ-0-Grammatiken können Sie noch mehr.
Mit Typ-0-Grammatiken können Sie alles erzeugen, was Sie mit Turing
-Maschinen erkennen können.
Also da haben Sie dann die Äquivalenz zu Turing-Maschinen bei Typ-0
-Grammatiken.
Und bei Typ-1-Grammatiken gibt es auch ein Automatenmodell, mit dem
Sie genau das erkennen können, was Sie mit Typ-1-Grammatiken erzeugen
können.
Und bei Typ-2-Grammatiken, kontextfreien Grammatiken, da gibt es auch
ein Automatenmodell, das also irgendwie zwischen Typ-3 und Typ-0 ist,
irgendwie zwischen endlicher Akzeptor und Turing-Maschine.
Das ist ein Automatenmodell, das ist ein Kellerautomaten, da können
Sie genau das erkennen, was Sie mit Typ-2-Grammatiken erzeugen können.
Das ist ein endlicher Automat, auch mit zusätzlichem Speicher, aber
nicht so wahlfreier Zugriffe bei der Turing-Maschine, sondern Sie
haben nur so einen Stapel, und wenn Sie was in den Speicher reintun,
Sie können immer nur das angucken, was Sie zuletzt reingetan haben, in
den Speicher und nur das wieder rausnehmen.
Das ist die Grammatik.
Und falls Sie das mal irgendwo lesen, oder falls ich es aus Versehen
sage, wenn Sie für 0, 1, 2 oder 3 eine formale Sprache haben, die von
der Typ-I-Grammatik erzeugt wird, dann sagt man auch, die formale
Sprache ist eine Typ-I-Sprache, oder sie ist vom Typ-I.
Also Typ-2-Sprachen sind die kontextfreien Sprachen und Typ-3-Sprachen
sind die regulären Sprachen.
Nur für den Fall, dass Ihnen das irgendwo mal über den Weg läuft.
Jetzt kann man sich auf den Standpunkt stellen...
Ja, toll.
Also jetzt kann man beweisen, mit endlichen Automaten kann man das
Gleiche wie mit rechtslinearen Grammatiken.
Ist ja nett, aber wozu reden wir dann über rechtslineare Grammatiken,
wenn man doch nicht mehr kann als mit endlichen Akzeptoren?
Naja, das ist ein Beispiel für eine Situation, die hat man öfter mal.
Man hat verschiedene Formalismen und stellt fest, oh, die sind ja
äquivalent.
Welchen Vorteil kann das denn noch haben?
Also, sich trotzdem mit mehreren Formalismen zu beschäftigen, obwohl
einer so gut ist wie der andere, genauso mächtig, in irgendeinem
Sinne.
Naja, der Punkt ist, man kann zwar genau das Gleiche, aber die Frage
ist immer, ob in allen Fällen das eine Beschreibungsmittel genauso
bequem ist wie das andere.
Das ist halt im Allgemeinen nicht unbedingt der Fall.
Zum Beispiel bei regulären Sprachen, da gibt es Beispiele, sehr
eindrückliche Beispiele.
Da können Sie relativ einfache rechtslineare Grammatiken hinschreiben,
die irgendwas erzeugen, aber wenn Sie dann sich angucken, wie sieht
denn ein endlicher Akzeptor aus, so wie wir ihn definiert haben, der
genau das Gleiche akzeptiert, ist der viel größer.
Wieder dieses N und 2 hoch N, was ich vorhin gesagt habe.
Das liegt daran, dass unsere endlichen Akzeptoren so sind, dass in
jedem Schritt eindeutig klar ist, was ist der nächste Zustand.
Das finden Sie auch natürlich, ist es auch.
Aber das ist tatsächlich eine Einschränkung, die sozusagen bei
rechtslinearen Grammatiken wegfällt.
Gucken Sie sich nochmal ein paar rechtslineare Grammatiken an,
vielleicht kriegen Sie ein Gefühl dafür.
Manchmal rechtslineare Grammatiken sind einfach bequemer fürs
Hinschreiben als endliche Akzeptoren.
Einfach kompakter, übersichtlicher.
Und zwar erzwungenermaßen.
Da muss man mit endlichen Akzeptoren viel umständlicher sein.
Nach diesem Ausflug zu rechtslinearen Grammatiken, damit wir mal über
Typ 3 und Typ 2 reden konnten, und schon ohne, dass Sie es gemerkt
haben, etwas angedeutet haben, was irgendwie in einem Jahr mal
wiederkommt, gehen wir nochmal zurück zu regulären Ausdrücken.
Stellen wir uns vor, wir möchten tatsächlich einen Teil dieses Satzes
von vorhin, der sagte, dass endliche Automaten, reguläre Ausdrücke und
rechtslineare Grammatiken sind äquivalent.
Wir wollen einen Teil davon beweisen oder zumindest eine Beweisskizze
angucken, also wenn ein beliebiger regulärer Ausdruck gegeben ist,
dann kann man immer systematisch eine rechtslineare Grammatik
konstruieren, die genau das erzeugt, was durch den regulären Ausdruck
beschrieben wird und nichts anderes.
Da muss man also etwas beweisen, also Aussage zu jedem regulären
Ausdruck, es gibt R, es gibt eine rechtslineare Grammatik G mit L von
G gleich das, was durch R beschrieben wird.
Da muss man also etwas beweisen für alle regulären Ausdrücke.
Wie beweist man für alle regulären Ausdrücke?
So ein, zwei, drei Beweismethoden für Aussagen der Form für alle X
gilt etwas.
Haben wir gesehen, die einfachste war, man sagt, ich nehme hier
einfach ein X und ich mache keine zusätzlichen Annahmen, nur an dieses
Ding genügt der Definition von das sind die Eigenschaften, die ich
verwende, nur die, und wenn es mir in diesem allgemeinen Fall gelingt,
zu beweisen, das, was ich beweisen will, dann ist das also wahr für
alle Objekte mit dieser schönen Eigenschaft, also für alle regulären
Ausdrücke.
Eine andere Möglichkeit, bei Zahlen, haben wir gesehen, für alle
natürlichen Zahlen gilt, manchmal hilft Induktion.
Und sowas kann man jetzt hier bei so einer Aussage, die zu beweisen
ist für alle regulären Ausdrücke auch sowas wie Induktion machen.
Und wie Sie gleich sehen werden, über Zahlen redet man sozusagen nur
noch implizit.
Und deswegen vordergründig mehr so über Gebilde, reguläre Ausdrücke
und wie die aufgebaut sind aus Teilausdrücken.
Und deswegen redet man da manchmal von struktureller Induktion.
Aber, also Sie werden sehen, das ist jetzt kein Hexenwerk, nicht
magisch, das ist normale, vollständige Induktion.
Erster Schritt.
Hier an einem Beispiel dargestellt.
Wenn Sie einen regulären Ausdruck haben, dann sozusagen aufgrund der
Definition regulärer Ausdrücke hat er ja so eine gewisse Struktur, ist
er auf eine gewisse, eindeutig auf eine gewisse Art und Weise aus
Teilausdrücken zusammengesetzt, also aus Teilen, die auch reguläre
Ausdrücke sind.
Und dann kann man das auch, wie hoffentlich auch Sie finden, relativ
naheliegend mit so einem Baum darstellen, wo nämlich die Blätter, an
den Blättern das steht, was wir als atomare, in Anführungszeichen,
reguläre Ausdrücke zugelassen hatten, nämlich die durchgestrittene
Null und so einzelne Symbole A oder B.
Und wenn man dann so einen Teil aus, wenn man jetzt aus kleinen
Ausdrücken größere zusammenbaut, zum Beispiel, indem man hier B,
senkrechter Strich, Null, Klammern außenrum macht, dann malt man einen
Knoten über diese Bleiten, Beta B und durchgestrichene Null und
schreibt da den Operator sozusagen rein, den senkrechten Strich mit
Pfeilen zu den Unterausdrücken.
Und wenn Sie dann hinter dem sozusagen mit Bedeutung Produkt einen
anderen regulären Ausdruck A haben, dann malt man hier einen Knoten
oben drüber.
Und da habe ich jetzt mal einen Malpunkt reingeschrieben als
Erinnerung an dieses Hier steht nichts, aber es bedeutet Konkatenation
der formalen Sprachen.
Also hier ein Punkt für Konkatenation oder Hintereinanderschreibung
und dann eine Kante zu dem Teilbaum für den linken Teil, Teilausdruck
B oder nichts.
Und ein Pfeil zu dem Teilbaum ist nur ein Blatt mit dem rechten
Teilausdruck A.
Und B Stern, da haben Sie erstmal das Blatt B und dann oben drüber ein
Knoten Stern.
Und ein Stern bezieht sich nur auf einen regulären Ausdruck, deswegen
gibt es da nur eine Kante eben zu diesem Blatt B.
Und dann diese beiden hintereinander, B oder nichts A und einerseits
und B Stern andererseits, die hintereinander haben Sie noch einen
Knoten oben drüber Hintereinanderschreibung und die linke Kante zu dem
linken Teilausdruck, also zur Wurzel des Baumes für den linken
Teilausdruck und die rechte Kante zu dem rechten.
Und sowas wollen wir jetzt mal als Regex-Baum bezeichnen.
Das ist nicht ein Ableitungsbaum, gemäß zum Beispiel der Grammatik von
vorhin.
Das sind hier keine Nicht-Terminalsymbole, die wir in die Knoten
geschrieben haben.
Aber es drückt auch eindeutig aus, die Struktur des regulären
Ausdrucks.
Und übrigens so nebenbei, wenn Sie in Java einen arithmetischen
Ausdruck hingeschrieben haben und Sie geben das dem Compiler, dann
macht er vielleicht erstmal einen Ableitungsbaum für den
arithmetischen Ausdruck zu irgendeinem Zeitpunkt.
Aber dann baut er aus dem Ableitungsbaum auch mehr oder weniger
schnell genau so einen Baum.
Wo die ganzen Nicht-Terminalsymbole und die ganzen Klammern weg sind.
Die Klammern braucht man nicht mehr.
Das ist wie eng aneinander gebunden.
Das steckt in der Struktur des Baumes.
Die Klammern kann man alle weglassen.
Das ist schön.
Ist kompakter.
Die Blätter sind sozusagen die atomaren regulären Ausdrucke, die
Dinge, aus denen man was zusammensetzt.
Und die inneren Knoten sind so die Operatoren oder wie soll ich sagen,
mit denen aus kleineren Gebilden größere zusammengesetzt werden.
Gut.
Und damit wir jetzt gleich vernünftig reden können, machen wir es noch
ein kleines bisschen genauer.
Wann wollen wir sagen, irgendetwas ist ein Regexbaum?
Also erster Fall.
Da ist nur ein einzelner Knoten.
Das ist die Wurzel.
Jeder Baum hat eine Wurzel.
Und das ist aber auch schon alles.
Die Wurzel ist auch gleich platt.
Und dann muss da aber drinstehen einer von den atomaren regulären
Ausdrücken.
Das ist ein Element aus dem zugrunde liegenden Alphabet.
Also meinetwegen klein a oder was auch immer.
Das sind Regexbäume.
Und dann, so wie man aus kleinen regulären Ausdrücken größere
zusammensetzen kann, darf man jetzt auch aus kleinen Regexbäumen
größere zusammensetzen.
Eine Möglichkeit ist, einen Regexbaum zu kriegen.
Die Wurzel ist beschriftet mit einem Sternchen.
Und die Wurzel hat genau einen Nachfolger.
Oder die Wurzel ist beschriftet mit einem senkrechten Strich für das
oder oder mit einem Punkt für Konkordination.
Und die Wurzel hat zwei Nachfolger.
Und das sind die Wurzeln von Regexbäumen.
Also alles, was Sie so zusammenbauen können, das sind Regexbäume.
Und wenn wir jetzt beweisen wollen, für jeden regulären Ausdruck, es
gibt eine rechtslineare Grammatik, dann, ach so,
also offensichtlich, gegeben der reguläre Ausdruck, Sie können so
einen Regexbaum bauen und umgekehrt auch, wenn Sie den Baum sehen,
können Sie auch rekonstruieren, wie sah der reguläre Ausdruck aus.
Also das ist so eine Bijektion, ja.
Und zwar deswegen, weil Sie einen regulären Ausdruck immer nur auf
eine Art und Weise aus Teilausdrücken zusammensetzen können.
Das ist das Schöne an dieser Definition, wie wir sie hatten.
Und, ah ja, wenn man jetzt also etwas beweisen möchte für alle
regulären Ausdrücke, dann äquivalent kann man auch das beweisen für
alle Regexbäume, ja.
Irgendwie beweist man etwas für alle Bäume, egal wie groß sie sind.
Man macht so etwas wie Induktion über die Größe und zeigt für jede
Größe, alle Bäume dieser Größe haben die Eigenschaft.
Und was ist jetzt ein sinnvolles Maß für Größe?
Ja, zum Beispiel die sogenannte Höhe von Bäumen.
Was ist die Höhe eines Baumes?
Also wenn die Wurzel gleich ein Blatt ist, wenn es gar keine Kanten
nach unten gibt, dann sagt man, es hat Höhe Null.
Und ansonsten die Höhe eines Baumes, das ist also die Länge der
längsten Pflanze, von der Pfade, von der Wurzel bis zu den Blättern.
Und das heißt, die Höhe eines Baumes, also wenn die Wurzel nicht Blatt
ist, dann hat also die Wurzel mindestens einen Nachfolger und daran
hängen irgendwelche Teilbäume.
Da können Sie für jeden, also nennen wir die heißen hier UI, ja.
Gerade eben in dem Beispiel gab es nur den Fall ein Unterbaum oder
zwei.
Und die können natürlich diese beiden Teilbäume, die da unten hoch
sind, unterschiedlich groß, ja.
Also reden wir lieber über Höhe.
Und was man dann sagt, ist, die Höhe von dem ganzen Baum ist so
festgelegt, man guckt sich an, was ist die größte Höhe eines
Unterbaumes und da addiert man noch eins drauf.
Also die Höhe eines Baumes, wenn er nicht triviale Höhe Null hat, ist
eins plus Maximum der Höhen der Unterbäume, die da drunter hängen.
Und einen Beweis für alle Regex-Bäume können Sie dann machen durch
Beweis über vollständige Identifikation über die Höhe der Regex-Bäume.
Also Beweis für alle Bäume der Höhe Null und wenn für alle Bäume der
Höhe N, dann auch für alle Bäume der Höhe N plus 1 oder so.
Aber da muss man halt jetzt so ein bisschen aufpassen.
Also das, was ich gerade gesagt habe, war die naive Variante.
Sie behandeln sich von Höhe N nach Höhe N plus 1.
Das ist aber ein bisschen blöd, denn wenn Sie für einen Baum der Höhe
N plus 1 was beweisen wollen, da brauchen Sie ja vielleicht
Induktionsvoraussetzungen für alle Unterbäume, die da drunter hängen.
Und die können ja unterschiedlich hoch sein.
Also wenn Sie da nur zur Verfügung haben, für Bäume der Höhe N gilt
etwas, dann reicht das vielleicht nicht.
Man möchte gerne als Induktionsvoraussetzung für alle Bäume
irgendeiner Höhe i kleiner gleich N.
Egal, ob das N oder N minus 1 oder 1 oder 0 ist, gilt das schon.
Und wenn Sie nochmal in Kapitel 6 gucken, da haben wir aus unter
anderem genau dem Grund, weil wir es hier brauchen können, aber eben
nicht nur hier, sondern in vielen Zusammenhängen bewiesen, tatsächlich
sogar bewiesen, das darf man als Induktionsvoraussetzung immer nehmen.
Es ist trotzdem alles gut.
Sie dürfen sich beim Induktionsschritt nicht beschränken auf das, was
Sie über von N, also wenn Sie jetzt für Höhe N plus 1 zum Beispiel
hier was beweisen wollen, Sie müssen sich als Induktionsvoraussetzung
nicht beschränken auf wir wissen etwas über Höhe N, sondern Sie können
benutzen, wir wissen etwas über alle Höhen kleiner gleich N.
Und das heißt dann, wenn Sie jetzt da so eine vollständige Induktion
über die Höhe N sagen,
Sie hangeln sich zu Bäumen, die zusammengesetzt sind aus immer
größeren Unterbäumen.
Und
dann beweisen Sie zum Beispiel durch vollständige Induktion, für jedes
N gilt das folgende, für jeden Regexbaum, der Höhe N hat, gibt es eine
rechtslineare Grammatik, die genau das erzeugt, was der reguläre
Ausdruck beschreibt.
Was sind Regexbäume mit der Höhe Null?
Da steht entweder direkt an der Wurzel die durchgestrichene Null oder
ein einzelnes Symbol.
Und das bedeutet die leere Sprache oder die Sprache, die einfach ein A
oder ein B enthält und sonst nichts.
Und für diese einfachen formalen Sprachen können Sie natürlich
rechtslineare Grammatiken hinschreiben.
Also eine rechtslineare Grammatik, die nichts erzeugt, können Sie
hinschreiben.
Startsymbol kann man ersetzen durch Startsymbol und sonst nichts.
Da können Sie überhaupt kein Wort aus Terminalsymbolen ableiten.
Und wenn Sie nur ein Wort ableiten für ein einzelnes Symbol, dann
nehmen Sie die Produktion.
Startsymbol kann ich ersetzen durch dieses Symbol.
Eine Produktion, die können Sie einmal anwenden, fertig, können Sie
das ableiten und offensichtlich nichts anderes.
Also Induktionsanfang ist ganz einfach.
Und dann halt Induktionsschritt.
Sie hangeln sich nach N plus 1 und Sie dürfen, das ist legal, als
kleiner gleich N gilt für jeden Regexbaum der Höhe i gibt es eine
rechtslineare Grammatik, die das erzeugt.
Und Sie haben das und müssen jetzt beweisen, ja, für Bäume der Höhe N
plus 1 gilt das entsprechende.
Und naja, ein Baum der Höhe N plus 1, wie kann der aussehen?
Da gibt es also ein oder zwei Nachfolger.
Da gibt es nur drei Fälle und die muss man halt getrennt angucken.
Also hier sind die drei Möglichkeiten, wie ein Regexbaum der Höhe N
plus 1 aussehen kann.
Sie haben eine von den drei möglichen Beschriftungen an der Wurzel und
einen oder zwei Nachfolger.
Und jeweils unten drunter hängen ein oder zwei Regexbäume und die Höhe
von den Dingern ist
N plus 1.
Und Sie wissen schon, es gibt für R' R1' R2' nach
Induktionsvoraussetzung jeweils eine rechtslineare Grammatik, die das
Richtige erzeugt.
Und dann müssen Sie aus den Grammatiken für die Teilbäume eine
Grammatik für das Ganze konstruieren.
Das ist in manchen Fällen einfach, in anderen Fällen nicht ganz so
der Fall, ja.
Ansonsten muss man erst noch wieder ein bisschen was lernen über
Grammatiken.
Das wollen wir uns hier sparen, das führt zu weit.
Für Vereinigungen oder bei regulären Ausdrücken.
Also die Induktionsvoraussetzung ist, es gibt eine Grammatik G1, die
erzeugt genau das, was durch den regulären Ausdruck R1 beschrieben
wird.
Und es gibt eine Grammatik G2, die
die Vereinigung erzeugt.
Was ist die Aufgabe?
Wir müssen eine rechtslineare Grammatik konstruieren, die die
Vereinigung erzeugt.
So.
Jetzt dürfen wir uns vorstellen, und das ist aber tatsächlich bei der
Konstruktion dann wichtig, wenn man beweisen will, dass die
Konstruktion funktioniert.
Die Nicht-Terminalsymbole von Grammatik G1 und die Nicht
-Terminalsymbole von
Grammatik G2, kein Nicht-Terminalsymbol der einen Grammatik wird auch
bei der anderen benutzt.
Das ist wichtig, weil wir nämlich gleich im Wesentlichen die ganzen
Produktionen in einen Topf schmeißen wollen.
Und dann muss sozusagen immer noch klar sein, was gehört zu der einen
Grammatik, was gehört zu der anderen.
Und das kann
natürlich auch bei der Konstruktion Grammatik G2, das sind alle blau.
Also sie spendieren bei einem noch einen Strich oder irgendetwas.
Umbenennung.
Gut.
Und wie erzeugt man dann alles, was durch die eine oder die andere
Grammatik immer deutlich erkennen kann?
Gehört sie zu der einen oder zu der anderen Grammatik?
Dann also einfach im ersten Schritt, wenn sie es durch S1 ersetzen,
die Startsymbole der ersten Grammatik, dann danach.
Sie haben alle Produktionen von Grammatik 1, die können sie benutzen,
das ist prima.
Und die von Grammatik 2 können sie aber nicht benutzen, weil die Nicht
-Terminalsymbole das und nur das erzeugen, was eben Grammatik G1
erzeugt.
Und wenn sie anfangen mit S ersetzen durch S2, dann sind sie eben beim
Startsymbol von Grammatik 2 und sie können ableiten alles, was
Grammatik 2 erzeugt, aber auch garantiert nichts anderes.
Und das ist alles, ja.
Also die Konstruktion ist ganz simpel.
Man muss jetzt natürlich auch noch beweisen, dass die
Grammatik 1 und die Grammatik 2 unterschieden sind, dass kein Nicht
-Terminalsymbol in beiden Grammatiken vorkommt, denn andernfalls kann
man Unfug treiben.
Da gibt es einfach Beispiele.
Also der Beweis ist nicht völlig banal, aber interessiert uns hier
nicht, dass die Grammatik das Richtige tut.
Achso, und übrigens, das ist wichtig, die Grammatik soll ja
nicht ganz rechtslinear sein, weil es rechtslinear Grammatiken sind.
Und S ersetzen durch S1, S ersetzen durch S2 ist auch erlaubt, ja.
Auf der rechten Seite taucht nur ein Nicht-Terminalsymbol auf und es
steht ganz rechts.
Also die Grammatik ist rechtslinear.
Und also für Vereinigung ist das ganz einfach.
Für Konkatenation ist es nicht ganz so einfach und für
Konkatenationsabschluss ist es nicht ganz so einfach.
Ja, und jetzt abstrahieren Sie einfach noch ein kleines bisschen mehr
und stellen sich vor, naja, also dieses Reden über die Höhe der Bäume,
das ist ja mehr so geschehen am Rande.
Der wesentliche Punkt ist, man setzt große Gebilde aus kleinen
zusammen und man hat die Induktionsvoraussetzung für die kleinen
Gebilde und nutzt das dann aus,
wenn es funktioniert.
Es klappt auch die Behauptung, die man beweisen will.
Und dann hat man also sozusagen den allgemeinen Fall von so
struktureller Induktion.
Da haben Sie also immer die Situation, dass Sie erstens so atomarische
Bilder haben, also irgendwie so ganz kleine Dinger, bei den regulären
Ausdrücken eben die durchgestrichene Null oder ein einzelnes A, ein
einzelnes B.
Und Konstruktionsvorschriften,
die Sie dann mit der gleichen interessierenden Bauart zusammensetzen
können.
Und Sie müssen natürlich auch sicher sein, dass Sie mit Ihren
Konstruktionsvorschriften alles konstruieren können, was Sie
konstruieren wollen.
Und dann eben, wenn Sie etwas beweisen wollen, beweisen wir, dass
etwas gilt für alle Gebilde, die Sie so in endlich vielen Schritten
zusammensetzen können.
Da zeigen Sie eben sozusagen als
Induktionsschritt.
Und Sie zeigen, egal mit welcher der erlaubten
Konstruktionsvorschriften man aus kleinen Gebilde große zusammensetzt,
wenn die Unterstrukturen die gewünschte Eigenschaft haben, dann das
größere zusammengesetzte Gebilde auch.
Das ist dann sozusagen der Induktionsschritt.
Und dann redet man also nicht mehr explizit über, wir haben
vollständige Induktion über die Größe der Objekte, so nach dem Motto,
wie viele Konstruktionsschritte haben wir denn gemacht oder so,
sondern da redet man gar nicht mehr explizit drüber.
Aber man macht immer noch sozusagen vollständige Induktion.
Gut.
Also, haben Sie rechtslineare Grammatiken gesehen vorhin und jetzt
noch strukturelle Induktion und vor allem reguläre
Ausdrücke?
Genau.
Die werden Ihnen oder machen wir es mal so, wer von Ihnen hat denn
schon mal in der Praxis vor dem Rechner reguläre Ausdrücke benutzt?
Ah ja, wunderbar.
Gut.
Genau.
Also, Sie haben hoffentlich gemerkt, dass die nützlich sind.
Jedenfalls manchmal.
Also, um nochmal an syntaktisch korrekte E-Mails und sowas, um auf das
nochmal kurz nachlesen, wie sieht syntaktisch korrekt eine E-Mail
-Adresse aus?
Das ist auch festgelegt.
Das kann man auch durch einen regulären Ausdruck beschreiben.
Aber der reguläre Ausdruck ist leider sehr groß.
Also, er füllt eine DIN A4-Seite von oben bis unten komplett, selbst
wenn man noch allerlei Abkürzungen einführt.
Also, zum Beispiel in der Praxis, Sie wollen nicht so reguläre
Ausdrücke hinschreiben wie A oder B oder C oder D oder E oder F oder G
oder H oder, oder, oder, oder Z.
Das will kein Mensch tippen.
Da führt man noch Abkürzungen ein.
Natürlich.
Da schreibt man dann A bis Z in eckigen Klammern oder so etwas.
Aber selbst mit den Abkürzungen, also
E -Mail-Adressen ist nicht schön.
Das möchte man nicht lesen.
Also, bitte, nur weil man etwas mit einem gewissen Werkzeug tun kann,
heißt das nicht, dass man es auch unbedingt damit tun sollte.
Nicht.
Aber manchmal sind sie einfach sehr nützlich.
Gut.
Damit sind wir am Ende dieses Kapitels über reguläre Ausdrücke.
Jetzt ist noch ein bisschen Zeit, und zwar so viel Zeit, die man
verschwenden möchte für, ja, gehen Sie in die Mensa, sind Sie an einer
kurzen Schlange.
So.
Äquivalenzrelationen haben wir schon mal definiert.
Zur Erinnerung, also, wir haben eine Menge M.
Bei uns, na ja, die kann endlich sein, die kann auch unendlich sein.
Und eine binäre Relation heißt Äquivalenzrelation, wenn sie reflexiv
ist, symmetrisch ist und transitiv ist.
Notation ist sowas, was ans Gleichheitszeichen erinnert, mehr oder
weniger, weil halt Gleichheit ein Beispiel für eine Äquivalenzrelation
ist.
Und zur Erinnerung, die Eigenschaften, also Reflexivität heißt, jedes
Ding steht in Relation zu sich selbst.
Symmetrie heißt, wenn X in Relation zu Y steht, dann auch Y in
Relation zu X.
Und drittens, Transitivität, wenn X in Relation zu Y steht und Y in
Relation zu Z, dann steht auch X in Relation zu Z.
Das sind alles drei Eigenschaften.
Wenn Sie da statt des Äquivalenzzeichens einfach Gleichheit schreiben,
dann stimmt das offensichtlich, ja?
Also Gleichheit ist egal, was die Grundmenge ist, Gleichheit ist immer
eine Äquivalenzrelation, ganz banal.
Eine andere, wenn wir jetzt zum Beispiel bei den ganzen Zahlen sind,
Äquivalenz oder man sagt dann auch Kongruenz modulo n, was das mit der
Kongruenz auf sich hat, das sehen wir dann noch.
Also Sie sagen, zwei Zahlen sind äquivalent, wenn Sie den gleichen
Rest bei Division durch n geben.
Nun ist das bei negativen Zahlen vielleicht nicht ganz offensichtlich,
was der Rest sein soll.
Also sagen wir mal genauer, n ist ein Vielfaches, nein, n teilt die
Kongruenz.
Wenn das der Fall ist, dann heißen zwei Werte x und y Kongruenz modulo
n und man schreibt dann vielleicht so etwas, ja?
x äquivalent y modulo n.
Und da können Sie auch leicht nachrechnen, Reflexivität, Symmetrie und
Transitivität.
x minus x ist 0, das ist offensichtlich ein Vielfaches von n.
Und wenn x minus y ein Vielfaches von n ist, dann y minus x auch, also
ein ganz offensichtlich ein Vielfaches von n.
Und Transitivität auch ganz banal.
Kompliziertere Beispiele, wir haben in dem Kapitel, was war das, 17
oder so, über asymptotisches Wachstum von Funktionen.
Das erste, was wir definiert hatten, war für zwei Funktionen f und g
so dieses verbogene Gleichheitszeichen dazwischen für die beiden
Funktionen wachsen asymptotisch genauso schnell.
Da ist offensichtlich, also offensichtlich, dass es eine reflexive,
symmetrische und transitive Relation ist.
Ach ja, Kapitel 17, da steht es ja.
Also es gab Beispiele.
Bei Isomorphie von Grafen haben wir auch darüber geredet.
So, und eine einfache, ganz einfache Möglichkeit, die aber tatsächlich
sehr viele Beispiele erschlägt.
Eine sehr nützliche Situation ist die hier, wenn Sie irgendeine
Abbildung haben von einer Menge M in eine Menge M', dann können Sie
eine Äquivalenzrelation auf den Elementen in M definieren, indem Sie
sagen, ja, zwei Elemente heißen äquivalent, wenn sie den gleichen
Funktionswert haben.
Und man schreibt dann, dass diese, das gibt eine binäre Relation, ja,
also x äquivalent zu y, wenn f von x gleich f von y.
Da ist offensichtlich ein Zeichen kaputt gegangen.
Da muss ich mal noch was fixen, ja.
Diese Relation heißt dann auch die Faserung von f.
Also da würde man dann sagen, zum Beispiel, die drei blauen, jetzt
hier blau angemalten Elemente in M sind äquivalent, weil sie den
gleichen Funktionswert haben.
Die zwei roten sind äquivalent, weil sie den gleichen Funktionswert
haben, aber ein rotes und ein blaues sind nicht äquivalent, ja, die
haben verschiedene Funktionswerte.
Und das gelbe ist auch nicht äquivalent zu den anderen, aber es ist,
naja, jedenfalls äquivalent zu sich selber, denn es hat den gleichen
Funktionswert.
Also dann hat man jetzt hier drei so Mengen, wo jeweils jedes Element
zu sich selber äquivalent ist.
Und dass das eine Äquivalenzrelation gibt, das ist ganz banal
nachzurechnen.
Sie erben nämlich sozusagen einfach die Tatsache, dass Gleichheit eine
Äquivalenzrelation ist.
Und bei allen drei Bedingungen zieht man das ganz banal zurück, dass
dann die Faserung auch diese Eigenschaften hat.
Gut, machen wir das soweit und da geht es dann am Freitag weiter.
Dankeschön.