Gehen wir jetzt zur nächsten Folie.
Wir haben hier eine Reihe von Notationen, die wir brauchen.
Darf ich Sie bitten, ein bisschen ruhiger wieder zu werden.
Wir haben noch 10 Minuten oder eine Viertelstunde haben wir noch.
Die will ich aber ausnutzen.
Also, einige Begriffe werden immer wieder auftauchen und Notationen.
Und ich möchte das einmal kurz Ihnen hier zeigen.
Wir werden sehr viel zu tun bekommen mit Alphabeten.
Sprache, bauen auf auf Alphabeten.
Was ist ein Alphabet?
Eine endliche, nicht leere Menge von Zeichen.
Endlich, also nicht beliebig viele.
Die Menge der natürlichen Zahlen ist kein Alphabet.
Die Menge der natürlichen Zahlen ist unendlich.
Aber die Menge der Zahlen von 0 bis 9 ist ein Alphabet.
Oder auch 0,1 oder auch A bis Z oder Kombination von all diesen
Dingen.
Und wenn ich ein Alphabet habe, kann ich Wörter schreiben.
Sie sehen hier viele Wörter auf dieser Seite.
Hier das Wort Informatik, geschrieben über dem lateinischen Alphabet.
Oder 1,2,3, ein Wort über dem Alphabet 0 bis 9.
Oder hier dieses hier, ein Wort über dem Alphabet 0,1.
Das sind Wörter.
Haben keine Bedeutung, einfach nur Wörter.
Bedeutung wäre dann Semantik.
Wie interpretiere ich so etwas?
Und dann rede ich darüber, wie lang ein Wort ist.
Da zähle ich einfach die Anzahl der Zeichen in dem Wort.
Also bei Informatik ist das 10, bei 1,2,3 ist es 3, hier bei diesem
binären Wort ist es 8.
So kann ich die Länge eines Wortes feststellen.
Und dann gibt es manchmal leere Wörter.
Also überall sind ja ganz viele leere Wörter auf der Folie, natürlich.
Leere Wörter sind Wörter, in denen nichts ist.
Wir brauchen manchmal aus technischen, formalen Gründen das leere
Wort.
Wir sagen einfach, das leere Wort ist ein Wort der Länge 0.
Und wir bezeichnen das mit Lambda für leer.
Im Englischen finden Sie dafür häufig ein Epsilon für empty.
Auch etwas, wenn man Notationen wählt, irgendwelche Variablen wählt,
um etwas zu beschreiben, sollte man immer das mnemonisch machen.
Also mnemonisch.
Was ist mnemonisch?
So, dass man etwas damit verbindet.
Deswegen Lambda für leer oder Epsilon für empty.
Oder wenn Sie Variablen nehmen, auch immer bedeutungsorientiert.
Dann haben wir die Möglichkeit, systematisch Wörter zu bilden.
Zum Beispiel alle Wörter einer Länge n.
Zum Beispiel für n gleich 3 wäre die Menge a hoch 3, die Menge der
Wörter über dem Alphabet 01, alle Wörter der Länge 3, die 0 und 1
enthalten.
Es gibt 2 hoch 3 solche Wörter, also 8 solche Wörter, von 000 bis 111.
Und das sind also Wörter der Länge 3.
Oder 17 oder was immer, was Sie haben wollen.
Dann möchten wir manchmal alle Wörter anschauen.
Die Menge aller Wörter über einem Alphabet.
Das wäre die Vereinigung aller Mengen a hoch n, wobei n von 0 an alle
möglichen natürlichen Zahlen durchlockt.
Also n größer als 0.
Das heißt, das leere Wort ist da drin, 0 1 0 0 0 1 1 0 1 1 und so
weiter und so weiter.
Alle Wörter über dem Alphabet sind dort drin.
Für Alphabet 01 geht das hier so los.
Dann gibt es eine andere Schreibweise a+.
Bei a+, sage ich, Wörter der Länge 0 oder das Wort der Länge 0 ist
nicht drin.
An den nicht leeren Wörtern.
Das ist übrigens eine Standardschreibweise.
Wenn ich irgendwo plus sage, meine ich, die 0 ist nicht dabei.
Wenn ich Stern hinschreibe, sage ich, beliebig, kann auch leer sein.
Aber plus heißt immer, mindestens ein Zeichen.
Und dann habe ich ein Wort Sprache, L für Sprache, nicht Mnemonisch.
L für Language, Mnemonisch.
Ja, also L für Language, Sprache über einem Alphabet, ist einfach eine
beliebige Teilmenge der Menge aller Wörter über dem Alphabet.
Also irgendeine Teilmenge.
Und eine formale Sprache ist dann eine solche Sprache, die ich durch
ein endliches, formales System vollständig beschreiben kann.
Und solche endlichen, formalen Systeme wollen wir da später genauer
nennen.
Ja, und hier zum Beispiel eine Sprache, Menge aller Wörter über dem
Alphabet 01, wobei die Anzahl der Einsen in dem Wort gerade ist.
Die sehen Sie hier unten drunter leider gerade nicht, weil das
Werkzeug da verdeckt ist, aber da steht drunter, Anzahl der Einsen in
W ist gerade.
Also mit zwei oder drei oder vier oder null Einsen ist ein Wort dieser
Sprache.
Sie können also solche Sprachen unterschiedlich beschreiben.
Das, was ich hier aufgeschrieben habe, ist auch eine formale
Beschreibung.
Da habe ich ja die Menge definiert.
Durch einen Text endlicher Länge habe ich das spezifiziert.
Wir werden viele solche Dinge kennenlernen.
Und jetzt gibt es für solche Beschreibungen von Sprachen verschiedene
Möglichkeiten.
Und diejenigen, die wir kennenlernen werden, sind einerseits die
erzeugenden Methoden.
Drei grundlegende Methoden.
Erzeugend heißt, wenn ich dieses formale System sehe, weiß ich, wie
ich ein Wort der Sprache aufbauen muss.
Ich kann also jedes Wort der Sprache durch Verwendung dieses Systems
in endlich vielen Schritten erzeugen.
Das ist eine erzeugende Methode.
Zum Beispiel eine Grammatik.
Das wäre also hier eine Grammatik.
Analysieren, eine ganz andere Methode.
Ich gebe Ihnen ein Wort und das formale System, der Analysator, sagt
mir nach endlich vielen Schritten, ob das Wort zur Sprache gehört oder
nicht.
Das wäre ein solchen Automat.
Und dann gibt es noch eine Methode operationell.
Ich gebe Ihnen eine Vorschrift für diese Wörter der Sprache.
Zum Beispiel, wenn ich sage A plus B Stern C.
Das ist eine operationelle Beschreibung einer Sprache.
Da drin sind, das soll ein Stern sein hier.
Stern steht immer für Null oder beliebig oft.
Ich darf also ein A oder ein B beliebig oft hinschreiben und dahinter
muss noch ein C stehen.
Das heißt, ich habe hier Operationen, mit denen ich aus einfachen
Bestandteilen eine Sprache definieren kann.
Also zum Beispiel das Wort C ist da drin.
Das Wort AC oder das Wort BC oder das Wort ABBBC und so weiter.
C immer am Ende.
Das sind drei verschiedene Arten und das sind die wesentlichen drei
Arten der Beschreibung von Sprachen, die wir hier kennenlernen.
Erzeugen über Grammatiken, analysieren über Automaten, operationell
über solche Ausdrücke.
Und das werden wir im Weiteren dann genauer angucken.
Ich kann Ihnen jetzt noch ganz kurz etwas erzählen zu Chomsky
-Grammatik.
Was ist denn jetzt das schon wieder?
Chomsky-Grammatik habe ich Ihnen auch schon erzählt.
Sie werden gleich sehen, wie die aussehen.
Das hier ist der Chomsky, Noam Chomsky, ein Wissenschaftler, ein
Sprachwissenschaftler, der sich eigentlich mit der Beschreibung
natürlicher Sprache auseinandersetzt, aber er möchte formale Modelle
für Sprachen allgemein entwickeln.
Und er hat eine sogenannte Chomsky-Hierarchie entwickelt.
Und diese Chomsky-Hierarchie werden wir noch genauer kennenlernen.
Ich weiß nicht, wie weit wir heute noch kommen, vielleicht schaffen
wir das noch, die kurz aufzuschreiben.
Ich gebe Ihnen jetzt aber noch ein anderes System, nämlich eine
sogenannte Bacchus-Naur-Forschung.
Bacchus und Naur sind zwei Wissenschaftler, die Anfang der 60er Jahre,
Ende der 50er Jahre die Sprache Allgäu entwickelt haben.
Und die haben eine systematische Methode entwickelt für diese
Algorithmic Language, um die Syntax zu beschreiben.
Das ist hier die Art, wie Sie auch Java, Pascal und C beschreiben
können.
Und was sehen Sie hier drin?
Sie sehen einerseits solche Wörter in spitzen Klammern, das sind
sogenannte Nicht-Terminal- oder Non-Terminal-Symbole, Nicht-Terminal
-Symbole, oder auch Variablen, oder im Sinne der Sprachwissenschaftler
syntaktische Kategorien.
Name, Buchstabe, Ziffer.
Dann sehen Sie hier zwei Doppelpunkte und ein Gleichheitszeichen.
Das soll praktisch sagen, ich kann einen Namen, diese syntaktische
Kategorie oder Variable Name, ersetzen durch ein Buchstaben und dann,
etwas in geschweiften Klammern, das kommt gleich noch, Wiederholung
des eingeklammerten Ausdrucks.
Das heißt, ich kann hier Buchstaben und Ziffern beliebig oft machen,
das entspricht praktisch dem Stern.
Dann habe ich hier noch einen senkrechten Strich, das entspricht dem
Oder.
Das heißt, ein Name kann ich ersetzen durch ein Buchstaben, gefolgt
von einem Buchstaben oder einer Ziffer, und das beliebig oft.
Oder das erste muss ein Buchstabe sein.
Ein Buchstabe kann etwas sein, dieser A bis Z und 0 bis 9 sind
Konstanten oder auch Terminalsymbole, atomare Bestandteile der
Sprache.
Und ein Programm später muss aus Konstanten bestehen.
Alle Variablen da drin müssen irgendwann ersetzt werden durch diese
Konstanten.
Also zum Beispiel etwas wie A12 wäre ein Wort der Sprache, die
hierdurch beschrieben wird.
Indem ich nämlich Namen durch Buchstaben ersetze und dann hinter
Buchstaben noch eine Ziffer schreibe und noch eine Ziffer.
Das kann ich über diesen Konstrukt machen.
Und dann muss ich den Buchstaben durch A ersetzen und die Ziffer
zweimal durch eine 1 und durch eine 2.
Und dann kommen wir zur Grammatik.
Und jetzt haben wir also das formale Konstrukt, was der Chomsky
gemacht hat, das andere war Bacchus-Maurer, pragmatisch für
Programmiersprachen definiert.
Jetzt kommt formal eine Abstraktion.
Und da sehen Sie jetzt eine Menge N von Nicht-Terminalsymbolen oder
syntaktischen Variablen.
Eine Menge von Terminalsymbolen oder Konstanten.
Eine Menge von Regeln.
Was ist das denn?
P enthalten in N vereinigt T plus Kreuz N vereinigt T star.
Sie wissen ja schon, was das ist.
N vereinigt T plus heißt, ich habe Paare von irgendwelchen Regeln.
Zum Beispiel kann hier stehen A, dann ein Pfeil und dann meinetwegen
hier irgendein bc.
Das wäre eine solche Regel.
Jetzt hier mit einem Pfeil dazwischen, weil das ersetzt werden soll,
das A durch bc.
Ich habe auf der linken Seite, das phi ist immer mindestens ein
Zeichen.
Auf der rechten Seite darf aber auch das leere Wort stehen.
Da steht nämlich ein Stern.
Da können irgendwelche Konstanten oder Variablen stehen.
Irgendein Wort.
Also irgendwelche...
Sowas kann auch eine Regel sein.
Links steht ein Wort, rechts steht auch ein Wort und es ist noch keine
Beschränkung bezüglich der Länge usw.
Das kommt später.
Das sind irgendwelche Regeln.
Mit solchen Regeln, ähnlich wie das, was wir bei der Backels-Mauer
-Form kurz gesehen haben.
Mit solchen Regeln wollen wir Zeichen ersetzen durch andere.
Und wir beginnen mit dem S.
Mit dem Startsymbol.
Und damit haben Sie also hier alle vier Bestandteile.
Nicht-Terminalsymbole, Terminalsymbole, Regeln.
Das sind die eigentlichen Elemente, die Ihnen sagen, wie die Syntax
aussieht.
Und ein Startsymbol, mit dem Sie anfangen.
Und alles jeweils endliche nicht-leere Mengen.
Und damit haben wir also eine Grammatik gefunden.
Jetzt müssen wir wissen, wie man damit umgehen kann.
Ich sagte Ihnen schon, wir wollen formale Sprachen beschreiben.
Möglichst so, dass sie ganz einfach sind.
So einfach wie möglich.
Aber auch so ausdrucksstark wie möglich.
Damit wir alles beschreiben können, was in Programmiersprachen
beschrieben werden muss.
Das, was ich Ihnen hier angegeben habe, ist viel zu allgemein.
Und deswegen muss man das noch...
Jetzt kommen aber noch Beispiele.
Zu den Einschränkungen kommen wir dann am Mittwochmorgen.
Mittwoch um 8 Uhr, etwas früh.
Aber es ist ja noch nicht richtig tiefer Winter.
Das kann man auch machen.
Also, schauen wir uns jetzt mal an, das, was wir vorgesehen haben,
diese Bacchus-Nauer-Form, jetzt als Grammatik.
Ist ja ein bisschen was anderes, ein bisschen formaler.
Dazu brauchen wir die Menge der Nicht-Terminalsymbole, Namen,
Buchstabe, Ziffer.
Wir brauchen die Menge der Konstanten.
Und wir brauchen ein Staatssymbol.
Das Staatssymbol in dem Fall sei also gerade diese syntaktische
Kategorie Name in spitzen Klammern.
Jetzt schreiben wir die Regeln der Grammatik auf.
Das sind die Regeln, die genau dieser Bacchus-Nauer-Form hier oben
entsprechen.
Die ist da oben ein bisschen kürzer, weil wir dort einige Metasymbole
drin haben, die wir hier in der Chomsky-Grammatik nicht haben.
Also hier müssen wir sagen, dass wir einen Namen durch einen
Buchstaben ersetzen können oder durch einen Namen gefolgt von einem
Buchstaben.
Dann können Sie wieder den Namen durch einen Buchstaben ersetzen oder
einen Namen durch Name und Ziffer.
Also ich könnte, ich mache es mal kürzer, N für Name ersetzen durch
meinetwegen N, Z für Name, Ziffer und das ersetzen durch N, Z, das Z
bleibt stehen.
Und dann könnte ich das wieder ersetzen durch N könnte ich durch A
ersetzen.
Dann steht da A, Z, Z und das könnte ich ersetzen durch A, 1, Z und
das könnte ich ersetzen durch A, 1, 2.
So würde ich mit dieser Grammatik ganz einfach dieses Wort A, 1, 2
ableiten.
Beginnend hier mit einem N als Startsumf, ich habe das abgekürzt, da
müsste eigentlich Name in spitzen Klammern stehen und es müsste das Z
in spitzen Klammern stehen und es müsste Ziffer stehen.
Dann hätte ich hier, beziehungsweise hier ist nur ein Fehl, eine Sache
fehlt noch, da hätten Sie gerade einparken müssen, ich habe hier eine
Sache vergessen.
Ich muss natürlich an dieser Stelle eine Regel dazwischen bauen,
nämlich muss das auf WZZ überführen, für Buchstabe, Ziffer, Ziffer,
denn aus dem Namen kann ich nämlich nicht direkt ein A ableiten,
sondern nur über den Buchstab.
Ja, also das hatte ich hier gerade eben fast übersehen.
Und so haben wir hier eine vollständige Ableitung aus dem Startsymbol
N, das Wort A, 1, 2 abzuleiten.
Das ist jetzt eine Grammatik für die Wagnus-Mauer-Form.
Das machen wir auf dem nächsten Folio ein bisschen genauer.
Also, was heißt das?
Wir haben jetzt eine Grammatik gegeben und wir wollen in der Lage sein
zu sagen, dies ist ein Wort der Sprache, der Sprache, die von der
Grammatik erzeugt wird, dem Begriff, auf den kommen wir auch gleich
noch.
Jetzt gibt es einen Begriff, den wir hier brauchen, das ist der
Begriff der Überführbarkeit.
Wir haben also ein Wort V und ein Wort W.
Also, hier ist ein Wort V und das ist unser Wort V.
Und wir haben ein Wort W.
So, und jetzt steht hier, das V heißt durch P, durch unsere
Regelmenge, unmittelbar überführbar in das Wort, das hier ist das Wort
W da unten, genau dann, wenn es Wörter U und Z aus N vereinigt T
Sternen gibt, also U und Z und eine Regel V auf Psi in der Regelmenge,
das heißt, wir haben hier ein V und hier unten auch U, Z und das Psi.
Dann sagen wir, dass das V auf W überführbar ist.
Das heißt, wir haben hier ein Wort stehen, in diesem Wort kommt die
linke Seite einer Regel vor, das ist dieses V.
Und wenn wir in einem Wort die linke Seite einer Regel entdecken,
können wir diese linke Seite einer Regel ersetzen durch die rechte
Seite einer Regel, durch das Psi.
Das ist eine Ableitung.
Also die Regel V auf Psi wird verwendet, um das Wort W aus dem Wort V
abzuleiten.
Wir werden gleich dafür noch Beispiele sehen.
Das ist also ganz einfach die Anwendung, wie man jetzt mit den Regeln
der Grammatik aus irgendeinem Wort ein anderes Wort ableiten kann.
Diese Regel ist also anwendbar auf das Wort V, weil die linke Seite
der Regel in diesem Wort auftaucht.
Jetzt wollen wir das manchmal häufiger machen, nicht nur einmal.
Und dann schreiben wir nicht nur einfach dieses V kann mit der
Regelmenge P abgeleitet werden auf W, sondern wir schreiben dann einen
Stern dahin.
Stern hatte ich letztes Mal gesagt, verwenden wir immer, wenn wir
meinen, beliebig oft.
Also reflexiv transitive Hülle heißt, wir können es eventuell nullmal
machen, das ist reflexiv, ein Wort wird nullmal auf sich selbst
abgeleitet, das heißt V auf V kann ich auch ableiten durch dieses
Stern, wenn ich gar keine Regel anwende.
Ich kann aber auch mehrfach etwas ableiten, wenn eben in dem Wort W
auch wieder eine linke Seite einer Regel auftaucht, will ich da ja
auch wieder was ableiten und so weiter und so weiter.
Und dann habe ich mehrfach Ableitungen gemacht und dann habe ich halt
hier über Transitivität dann diese Sternrelation.
Stern heißt also, habe ich schon mehrfach gesagt, wir können beliebig
oft das anwenden, was dort mit dem Stern versehen ist.
Wenn also V, Stern, P, W so in dieser Relation steht mit W, dann ist V
überführbar in W bzw.
W ableitbar aus V.
Ich gebe Ihnen gleich dazu ein Beispiel, damit Sie sehen, wie das
funktioniert.
Die Schreibweisen machen wir natürlich dann gleich wieder etwas
einfacher.
Wir werden nicht immer die Regelmenge P daran schreiben, das ist so
umständlich.
Wir schreiben nur diesen Doppelfeil dahin.
Und merken Sie sich diesen Unterschied, der Doppelfeil, den wir hier
verwenden, ist was anderes als der einfache Pfeil.
Der einfache Pfeil, den haben wir vereinbarungsgemäß immer nur für die
Regeln verwendet.
Der Doppelfeil wird verwendet für das Ableiten.
Beim Ableiten leite ich ein Wort W aus einem Wort V ab.
Bei der Regel sage ich, wie ich ableiten kann, indem ich nämlich eine
linke Seite auf eine rechte Seite oder durch eine rechte Seite
ersetze.
Das also zu diesen Dingen.
Wir kommen gleich zum Beispiel.
Erstmal muss ich Ihnen jetzt noch sagen, was eigentlich dann die
Sprache ist, die von einer Grammatik erzeugt wird.
Ich habe mir also eine Chomsky Grammatik gegeben.
Wir haben eine Regelmenge, wir haben ein Staatssymbol.
Und jetzt sind alle Wörter über dem Terminalalphabet, die ich aus dem
Staatssymbol ableiten kann, Wörter der Sprache.
Und damit ist diese Menge aller Wörter, die ich aus dem Staatssymbol
ableiten kann, die Sprache, die durch diese Regelmenge, nicht
Terminalsymbolmenge, Konstantenmenge usw.
beschrieben wird.
Und ich kann jetzt sagen, dass das hier eine Ableitung ist.
Das habe ich schon vorgesagt.
Die einzelnen Ableitungsschritte hier sind dann, wenn ich die
zusammennehme, ist das eine Ableitungsfolge.
Und wir haben also für jedes Wort aus einer Sprache eine
Ableitungsfolge, beginnend mit dem Staatssymbol.
Ich denke, das ist eine sehr intuitiv verständliche Art, wie man das
machen muss.
Das ist sinnvoll, das so zu beschreiben.
Ein Staatssymbol, von dem alle Wörter dieser Sprache ausgehend erzeugt
werden.
Und natürlich sind Wörter der Sprache nur die, die aus den
Terminalsymbolen bestehen.
Alles dazwischen sind irgendwelche Satzformen.
Jetzt kommt ein Beispiel.
Schon wieder unsere Grammatik, die ich Ihnen jetzt schon mehrfach
gezeigt habe.
Und jetzt kommt nochmal das Beispiel, das ich Ihnen vorhin schon
gezeigt habe, jetzt aber ein bisschen besser geschrieben.
Hier haben wir also die Ableitung, wir wollen mit dem Staatssymbol
Name anfangen.
Das ist jetzt ein Wort.
Jetzt suchen wir in dem Wort die linke Seite einer Regel.
Wir werden mehrfach fündig.
Zum Beispiel diese Regel hier.
Name, er wird ersetzt durch Name Ziffer.
Ist eine mögliche Regel, die wir anwenden.
Dadurch entsteht aus dem Wort Name das Wort Name Ziffer.
Das ist neu entstanden.
Und jetzt machen wir den nächsten Schritt.
Wir finden hier wieder linke Seiten von Regeln, sogar mehrfach.
Wir können Name, wir können Ziffer uns hernehmen.
Und das nächste, was wir tun, ist, dass wir das Wort Name, das ist die
linke Seite, ersetzen durch Name Ziffer.
Und anschließend haben wir wieder ein Wort mit mehreren Symbolen, die
wir auf linken Seiten von Regeln finden.
Man könnte vielfältige andere Ableitungen machen.
Ich mache jetzt hier die Ableitung Name auf Buchstabe.
Also wird jetzt Name hier in dem Fall ersetzt durch Buchstabe.
Und dann finde ich wieder mehrere linke Seiten, nämlich Buchstabe,
Ziffer und Ziffer.
Und jetzt kann ich zum Beispiel hier, das ist der nächste Schritt, was
hier gemacht wird, ist, dass ich also diese Ziffer hier ersetze durch
die zwei.
Und anschließend wird diese Ziffer hier ersetzt durch die eins.
Und dann wird der Buchstabe ersetzt durch das A.
Und damit haben wir aus Name das Wort A12 abgeleitet.
Und A12, das sind Zeichen aus dem Terminalalphabet.
Das heißt, A12 ist ein Wort der Sprache, die aus der Grammatik erzeugt
wird, die hier angegeben ist.
Eine sehr, sehr einfache Sprache.
Das sind alle Wörter, die halt mit einem Buchstaben beginnen und
danach irgendwelche weiteren Buchstaben oder Ziffern enthalten.
Sehr einfach.
Aber die haben wir jetzt formal beschrieben.
Sie wissen jetzt, wie man also ableiten kann.
Gut.
Das ist also ein Wort der Sprache L von G.
Und auf diese Art und Weise kann man also jetzt Wörter ableiten.
Genauso können Sie also aus der Grammatik für Java Programme der
Sprache Java ableiten.
Das werden noch nicht unbedingt sinnvolle Programme sein, die Sie
dabei erzeugen, wenn Sie nur die Regeln der Syntax blind anwenden.
Aber Sie bekommen syntaktisch gültige Programme in Java, wenn Sie die
Grammatik von Java entsprechend verwenden.
Okay.
Sie werden noch viele Beispiele für Grammatiken kennenlernen.
Und jetzt machen wir noch ein paar kleinere Vereinbarungen.
Wir werden üblicherweise gewisse Schreibweisen verwenden.
Nicht-Terminalsymbole werde ich jetzt zur Vereinfachung, weil ich hier
nicht immer so viel hinschreiben kann, zur Vereinfachung meistens mit
irgendwelchen lateinischen Großbuchstaben bezeichnen.
Die Terminalsymbole meistens mit kleinen lateinischen Buchstaben.
Das ist alles nur zur Abkürzung, damit ich hier einfacher Sachen
aufschreiben kann.
Sie können sich aber unter solchen Variablen A, B, C oder so etwas
auch vorstellen, dass da steht irgendeine Variable für eine Methode
oder für irgendeinen Datentyp oder für irgendwelche Konstrukte, für
Anweisungen, für Wildschleifen oder Ähnliches, irgendwelche
syntaktischen Kategorien aus irgendeiner komplexeren Sprache.
Nur die will ich jetzt hier nicht aufschreiben.
Ich gebe Ihnen auch solche Beispiele, aber meistens nehme ich solche
künstlichen Beispiele, weil ich Ihnen darin erklären kann, wie man
prinzipiell vorgeht.
Das ist einfach eine kleine Abstraktion, die uns das Schreiben ein
bisschen vereinfacht.
Und so werden wir also vorgehen.
Dann haben wir noch Wörter, die wir meistens mit den Zeichen am Ende
des Alphabets beschreiben.
Also U, V, W sind normalerweise Wörter über einem Alphabet.
Oder wenn das Wörter sind innerhalb von Regeln einer Grammatik,
verwenden wir häufig auch die griechischen Buchstaben Phi, Psi, Tau,
Nu oder Omega oder was immer uns da gerade einfällt.
Das ist so einfach Vereinbarung, damit man einfach weiß, da steht ein
Phi oder Psi, das ist also die linke Seite oder rechte Seite einer
Regel.
Wenn da ein U, V, W steht, sind das irgendwelche Wörter, die gerade
abgeleitet werden.
Auf diese Art und Weise kann man sich ein bisschen besser
zurechtfinden.
Und dann haben wir eine weitere Vereinfachung.
Wenn ich mehrere Regeln habe, bei denen auf der linken Seite immer das
gleiche Zeichen steht, dann wollen wir das, genau wie wir das bei der
Bacchus -Nauer-Form gesehen haben, etwas abkürzend aufschreiben
können.
Nämlich, dass wir nur einmal diese linke Seite hinschreiben und danach
den senkrechten Strich verwenden, um die verschiedenen Alternativen
für die rechten Seite zu kennzeichnen.
Was hier steht, ist die Kurzform für diesen Block von Einzelregeln.
Eigentlich war es so definiert, alles einzelne Regeln.
Jetzt machen wir da eine Vereinfachung und sagen, wir können auch
durch Verwendung dieses senkrechten Striches, der natürlich nicht Teil
unserer Alphabete ist, mit diesem senkrechten Strich können wir
andeuten, dass wir hier verschiedene rechte Seiten haben, durch die
wir die linke Seite viel ersetzen können.
Naheliegende Schreibweisen...
Der senkrechte Strich steht immer für Alternativen.
Wir können also links oder rechts verwenden und das ist also etwas,
was man generell in Spezifikationen so macht.
Gut, dann gibt es eine ganze Reihe von Bemerkungen, die man hier
machen kann.
Zunächst einmal, das hatte ich letztes Mal gesagt, diese Definition
der Chomsky-Grammatik ist sehr allgemein.
Da können ja zig verschiedene Regeln sein, da kann stehen A auf A, das
ist ja etwas sehr Einfaches.
Kann aber auch da stehen A, U, X, V, da noch irgendein V und das
irgendwie auf A, B, X oder sowas.
Also Sie können links sehr lange Wörter haben und rechts kurze oder
Sie können auch hier auf der rechten Seite sehr lange Wörter haben.
Also können beliebige Sachen da stehen haben.
Irgendwelche Wörter über den Alphabeten, die wir hier angegeben haben.
Links können also auch Mischungen von Terminalzeichen und Nicht
-Terminalzeichen stehen.
Das ist alles völlig beliebig.
Sehr allgemein.
Und Sie können sich vorstellen, wenn man damit eine Sprache
beschreibt, wird das ziemlich kompliziert herauszufinden, welche
Wörter eigentlich erzeugt werden können.
Und es ist tatsächlich so, dass im Allgemeinen es nicht entscheidbar
ist, algorithmisch entscheidbar heißt, in endlicher Zeit durch ein
Verfahren, das auf einem endlichen Text mit endlicher Länge
beschrieben ist, in endlicher Zeit herauszufinden, ob die Antwort Ja
oder Nein ist, ob also ein Wort zur Sprache einer vorgegebenen
Grammatik gehört oder nicht.
Das nennen wir auch das Wortproblem einer formalen Sprache.
Gehört einem gegebenes Wort zur Sprache, die von dieser Grammatik
erzeugt wird oder nicht?
Ich gebe Ihnen ein beliebiges Wort, entscheiden Sie, ob das Wort zur
Sprache gehört oder nicht.
Das Wortproblem, das soll möglichst effizient beantwortet werden
können.
Das ist im Allgemeinen für beliebige Grammatik nicht entscheidbar.
Das werden wir noch sehen.
Für spezielle Grammatiken selbstverständlich kann es entscheidbar
sein.
Aber Sie können kein Verfahren angeben, das für beliebige Grammatiken
und für ein beliebiges Wort Ihnen sagt, ob das Wort zur Sprache gehört
oder nicht.
Und wir wollen natürlich generell wissen, wie groß der Aufwand ist, um
dieses Wortproblem zu entscheiden.
Und außerdem, auch darauf hatte ich hingewiesen, das werde ich
mehrfach betonen, wollen wir wissen, was wir eigentlich alles
beschreiben können.
Also, möglichst einfache Grammatiken, damit wir sehr effizient
entscheiden können, ob ein Wort zur Sprache gehört oder nicht, aber
auch gerade ausreichend, sodass wir alles das ausdrücken können, was
erforderlich ist.
Wir schränken deswegen die Grammatiken ein durch verschiedene
Grammatiktypen und Sie werden später sehen, dass wir zu jedem
Grammatiktyp, den wir hier angeben, auch eine äquivalente Klasse von
Automaten finden.
Was heißt hier äquivalent?
Die Sprache, die dann durch eine Grammatik beschrieben wird, können
wir auch durch einen Automaten beschreiben.
Das heißt, wir können dann die Sprache sowohl auf eine erzeugende Art
und Weise beschreiben, als auch durch eine analysierende Art und
Weise.
Das heißt, wir können sowohl Regeln uns überlegen, die uns sagen, wie
wir ein Wort hinschreiben müssen und andererseits auch ein Konstrukt
entwickeln, einen Automaten, der uns für ein gegebenes Wort
analysiert, ob das Wort zur Sprache gehört oder nicht.
Also das ist diese Äquivalenz zwischen Grammatiken und Automaten.
Jetzt kommen wir hier zur...
Aha, könnte man den Buchstaben auch nach B ableiten, beziehungsweise
woher wird das vorgegeben?
Also, da gehen wir nochmal, jetzt muss ich nochmal kurz zurück und
sagen, ich habe das beantwortet, das mache ich jetzt, das beantworte
ich jetzt sofort.
Wir gehen kurz zurück auf die vorige Folie.
Das war, da hatte ich die Frage vorher übersehen.
Also hier.
Selbstverständlich haben Sie viele Möglichkeiten, die Regeln
einzusetzen.
Wir hätten selbstverständlich auch B17 ableiten können oder A, B, C,
X, Y, 17 oder A, X, R, U, 3, 5, 7, X.
Hätten wir alles ableiten können.
Sie haben eine Frage?
Also, passen Sie auf.
Ich schreibe Ihnen jetzt die Frage wahr, muss ich links oder rechts
ableiten, kann ich auch in der Mitte ableiten.
Sie haben hier gesehen bei meinen Beispielen, da habe ich zum Beispiel
hier in der Mitte diese Ziffer ersetzt durch eine 1.
Ganz generell, das hatte ich ja gesagt, ist es so, wenn Sie irgendein
Wort haben, und da steht irgendwas drin.
Und an irgendeiner Stelle finden Sie jetzt hier, meinetwegen, da steht
jetzt Ziffer.
Da irgendwann drin.
Und hier steht irgendwas anderes davor und dahinter.
Das sind auch irgendwelche Zeichen aus dem Alphabet, den beiden
Alphabeten N und T.
Dann können Sie diese Variable ersetzen.
Die linken und rechten Seiten bleiben gleich.
Und Sie können hier hinschreiben, statt Ziffer, irgendeine dieser
rechten Seiten.
Können Sie also 7 hinschreiben, zum Beispiel.
Das heißt, es ist völlig egal, an welcher Stelle in dem Wort eine
Variable oder eine linke Seite einer Regel auftaucht.
Das sind in diesem Fall hier nur nicht Terminalzeichen, die links
auftauchen, einzelne.
Wo immer Sie also so eine linke Seite finden, können Sie diese linke
Seite ersetzen durch irgendeine passende rechte Seite.
Und was passt, das ist völlig egal.
Sie haben hier also große Vielfalt, das zu tun.
Ja, ich denke, das sollte die Frage beantwortet haben.
Dann gehen wir also gleich weiter nochmal hier zu diesen Bemerkungen.
Wir werden also die Grammatik einschränken.
Und das ist das, was wir dann Chomsky-Hierarchie nennen, auf die wir
später noch genauer eingehen.
Die will ich jetzt einmal Ihnen beschreiben.
Und dann gehen wir anschließend zu den einfachsten Grammatiken, die
wir beschreiben können und den einfachsten Sprachen und werden dann
sukzessive komplexere Sprachen beschreiben.
Jetzt fange ich ganz oben an.
Das, was ich Ihnen bisher definiert habe, ist eigentlich so die Typ-0
-Grammatik.
Nichts eingeschränkt, beliebige Regeln.
Man hat dafür verschiedenste Bezeichnungen.
Man nennt sie manchmal Phrasen, Strukturgrammatik, also nur
irgendwelche Regeln für das Ersetzen von irgendwelchen Bestandteilen
eines Wortes sind dort gegeben.
Die Regeln sind beliebig, keinerlei Einschränkung.
Beliebig komplex kann das werden.
Dann schränkt man das auf die erste Art und Weise ein.
Das sind die sogenannten Typ-1-Grammatiken oder auch Kontext
-sensitiven Grammatiken.
Warum Kontext-sensitiv?
Kontext ist der Zusammenhang, die Umgebung.
Sensitiv heißt, irgendwie wird dabei der Kontext berücksichtigt.
Was meint man damit?
Wir nehmen uns ein Wort her.
Und in diesem Wort, das wir jetzt ableiten wollen, kommt irgendeine
Variable A vor.
Zur Vereinfachung, A ist immer irgendein Terminalsymbol.
Und jetzt sind die Regeln von der Art, wie es hier angegeben ist, wenn
also so ein Nicht-Terminalsymbol auftaucht, dann kann es also Regeln
geben, bei denen ein Kontext, Vieh 1, Vieh 2 angegeben ist und links
und rechts daneben irgendwas anderes, meinetwegen irgendein X und ein
Y.
Und jetzt kann ich dieses A ersetzen, wenn ich also jetzt diese Regel
anwenden will.
Wenn ich das ersetze, dann steht hier unten drunter ein neues Wort.
Wenn das also unser V ist und das das W, was wir aus V ableiten
wollen, dann kann ich also hier dieses A ersetzen in dem Kontext Vieh
1, Vieh 2.
Das heißt, das X bleibt sowieso erhalten, das Vieh 1 steht auch wieder
da, das Y bleibt erhalten, das Vieh 2 steht auch wieder da und
dazwischen steht jetzt ein Psi.
Das ist gemeint mit kontextsensitiven Regeln.
Ich kann ein Nicht-Terminalzeichen in dem Kontext Vieh 1, Vieh 2
ersetzen durch ein Psi, also durch irgendein Wort.
Und dieses Psi ist dabei ein nichtleeres Wort.
Und das heißt automatisch, dass wenn wir uns die beiden Wörter V und W
anschauen, wir können also V auf W ableiten, dann ist automatisch,
dass die Länge von V kleinergleich der Länge von W.
Weil wir ein Zeichen mindestens durch ein anderes Zeichen ersetzen,
das Psi ist ungleich Lambda, ungleich dem leeren Wort.
Das heißt, das Wort kann nicht kürzer werden.
Das, was ich auf der vorigen Folie angedeutet hatte, dass man
eventuell auf der rechten Seite auch kürzere Wörter haben kann, das
ist bei den kontextsensitiven Grammatiken nicht der Fall.
Deswegen nennt man sie auch monotone Grammatiken, weil dort bei allen
Regeln, die hier auftauchen, die rechte Seite immer mindestens so lang
ist wie die linke Seite.
Und das erleichtert schon die Möglichkeiten für eine Ableitung ganz
gravierend.
Wir können nämlich für alle Typ-1-Grammatiken immer entscheiden, ob
ein gegebenes Wort zu der durch diese Grammatik erzeugten Sprache
gehört oder nicht.
Der Aufwand ist noch relativ hoch, der kann auch exponentiell in der
Länge des Wortes sein, aber exponentiell in der Länge des Wortes ist
sehr, sehr, sehr, sehr lang, das ist klar.
Also zwei hoch irgendwas oder irgendeine konstante Hochlänge des
Wortes.
Das kann sehr lange dauern.
Aber es geht auf jeden Fall, ich kann es immer entscheiden, weil ich
nur eine endliche Menge von Wörtern durchsuchen muss.
Also, schauen wir uns das nochmal an.
Was ist der Unterschied zwischen Terminal- und Non-Terminal-Symbol?
Das hatte ich eigentlich auch schon gesagt, will ich aber nochmal
sagen.
Ein Nicht-Terminal-Zeichen, Non-Terminal-Symbol ist eine einfach
festgelegte Menge von Symbolen, die ich brauche, um daraus andere
Wörter zu erzeugen, die also auf der linken Seite von Regeln
auftauchen, wobei auf der linken Seite von Regeln auch Terminal
-Symbole auftauchen können.
Aber die Wörter der Sprache bestehen nur aus den Terminal-Symbolen.
Das heißt, ich muss in so einem Wort, das ich erzeuge, alle Nicht
-Terminal -Symbole rauswerfen können, durch Ersetzungen entsprechend
den Regeln der Grammatik.
Und erst wenn ich Wörter habe, die nur aus Zeichen bestehen, die in
dem Terminal-Alphabet sind, dann habe ich ein Wort der Sprache.
Ich habe Ihnen ja gerade vorher Beispiele genannt, da hatten wir bei
der Bacchus-Nauer-Form für diese einfachen Wörter oder Identifier,
hatten wir Kategorien Name, Buchstabe, Ziffer und dann die
Terminalzeichen, Alphabet, Symbole A bis Z beziehungsweise Ziffer 0
bis 9.
Das waren die Terminalzeichen.
Ich denke, das dürfte deutlich geworden sein.
Machen wir weiter mit diesen Einschränkungen.
Das sind also jetzt die kontextsensitiven Grammatiken.
Wenn etwas kontextsensitiv sein kann, dann können wir auch etwas
kontextfrei machen.
Also, bei kontextfreien Regeln, da ist es so, dass alle Regeln so
aussehen, dass wir ein Nicht-Terminalzeichen links haben, ein
einzelnes Nicht-Terminalzeichen, das wir durch eine Folge von Zeichen
ersetzen können.
Das heißt, da kommt es auf den Kontext nicht an.
Da reicht es aus, wenn wir irgendein Wort haben, da taucht irgendwo
dieses Zeichen A auf, dann können wir das sofort überführen in ein
anderes Wort, wo hier auf der rechten Seite, wo das A durch das Psi
ersetzt wurde.
Dann haben wir also hier jetzt ein V und W und in dem Fall haben wir
das so abgeleitet.
Also das ist dann kontextfrei, wir können die Nicht-Terminalzeichen
unabhängig von dem Kontext, in dem sie auftauchen, ersetzen, während
bei den kontextsensitiven Regeln diese Ersetzung von Nicht
-Terminalzeichen nur in einem Kontext passieren konnte, der durch die
Regel angegeben ist, durch Psi 1, Psi 2.
Okay, das also zu diesen beiden Möglichkeiten, das war die Typ-2
-Grammatik.
Ein wichtiger Unterschied ist da, bei den Typ-1-Grammatiken hatten wir
die Bedingung, dass das Psi, die rechte Seite, immer nicht leer ist.
Das steht bei den kontextfreien Regeln nicht dabei.
Da steht das Psi aus N vereinigt T-Stern.
Das heißt, das kann eine beliebige Folge von Nicht-Terminal- und
Terminalzeichen sein, die auch leer sein darf.
Jetzt gab es hier oben noch einen weiteren Satz, auf den ich noch gar
nicht eingegangen bin, bei den Typ-1-Grammatiken.
Da darf auf der rechten Seite in einem einzigen Fall ein leeres Wort
auftauchen, nämlich nur, wenn das Staatssymbol links steht und wenn
dieses Staatssymbol auf keiner rechten Seite auftritt.
Warum braucht man das?
Einfach nur für den Fall, dass das leere Wort auch ein Element der
Sprache sein soll.
Das ist also mehr eine technische Anforderung.
Das Problem ist aber, wenn Sie also hier eine Typ-2-Grammatik haben,
eigentlich muss man ja meinen, dass die Typ-2-Grammatiken eigentlich
nur Einschränkungen von Typ-1-Grammatiken sind.
Da müsste ja jede Sprache, die von einer Typ-2-Grammatik erzeugt
werden kann, auch von einer Typ-1-Grammatik erzeugt werden können.
Ist aber nicht so, weil zumindest sieht das auf den ersten Blick nicht
so aus, tatsächlich ist es doch so, aber auf den ersten Blick sieht es
so aus, dass eben die Typ-2-Grammatik wegen dieser Bedingung, dass
hier auf der rechten Seite eventuell auch das leere Wort stehen darf,
leider nicht die Anforderungen der Typ-1-Grammatik erfüllt, weil eben
die Regeln nicht monoton sind.
Bei Typ-1 hat man das nur für das Staatssymbol erlaubt.
Das ist also ein kleiner Unterschied.
Sie werden später sehen, dass man immer zu einer Typ-2-Grammatik, wo
also rechtsleere Wörter auftauchen, eine Äquivalente finden kann, die
die gleiche Sprache erzeugt, bei der das nur für das Staatssymbol
passiert und dann ist das auch insbesondere eine Typ-1-Grammatik.
Aber wir können auch Typ-2-Grammatiken definieren, bei denen
rechtsleere Wörter auftauchen.
Ist eigentlich mehr eine formale Geschichte.
Und dann haben wir hier die Typ-3-Grammatik, noch weiter
eingeschränkt, die man auch rechtslinear nennt, mit folgenden
einfachen Regeln.
Links dürfen nicht Terminalzeichen auftauchen und rechts entweder das
leere Wort, wie bei den kontextfreien, ein Terminalzeichen oder ein
Terminalzeichen gefolgt von einem Nicht-Terminalzeichen.
Sehr einfache Regel.
Und rechtslinear ist jetzt offensichtlich, Sie haben hier immer rechts
bei einer Regel als rechtestes Zeichen eventuell noch ein Nicht
-Terminalzeichen und das können Sie weiter ersetzen.
Wenn Sie also jetzt irgendeine Ersetzung machen, dann sehen alle diese
Ersetzungen, wenn Sie jetzt also hier bei einer Typ-3-Grammatik, wenn
wir uns das anschauen, dann haben wir hier bei den Wörtern, die da
irgendwo abgeleitet werden können, als rechtestes Zeichen eventuell
irgendeine, ein C oder irgendein A, ich schreibe mir einfach jetzt ein
A rein, das rechteste Zeichen kann also irgendein Nicht
-Terminalzeichen sein und das dürfen Sie dann ersetzen.
Und dann entsteht wieder irgendetwas, hier irgendein B und dann
vielleicht irgendein Groß-B oder was immer, oder A, B, was immer Sie
für Regeln haben.
Das heißt, ganz rechts steht eine Variable, die können Sie weiter
ersetzen und alles links davon, das sind schon Terminalzeichen.
Offensichtlich sehr, sehr einfach.
Nur eine Position, an der noch Nicht-Terminalzeichen auftauchen
können.
Ich sehe, dass Ihnen das zu langsam ist, ich mache mal ein bisschen
schneller.
Jetzt haben wir Grammatiken erzeugt und jetzt müssen wir natürlich
sehen, wie sind die Sprachen dazu zu charakterisieren.
Passend zu den Grammatiken reden wir eben auch von Typ 0, 1, 2, 3
Sprachen.
Also eine Sprache heißt eine Chomsky-Sprache von Typ I, für I aus der
Menge 0 bis 3.
Genau dann, wenn es eine Grammatik gibt von dem entsprechenden Typ,
die diese Sprache erzeugt, über diesem entsprechenden Eingabealphabet.
Und jetzt irgendwie fett gedruckt mit Index I von E, das ist die Menge
aller Sprachen von Typ I über einem Alphabet E.
Damit können wir über die Menge der Typ 0 Sprachen, die Menge der Typ
1 Sprachen, die Menge der Typ 2 Sprachen reden.
Und eine Sprache, wie gesagt, ist von einem Typ I, Typ 2, 3 oder 1
oder 0, wenn es eine Grammatik von diesem Typ gibt, die diese Sprache
erzeugt.
Also offensichtlich, das habe ich gerade gesehen, ist jede Typ 3
Grammatik von Typ 2.
Also jede Typ 3 Sprache auch eine Typ 2 Sprache, also jede
rechtsliniare Sprache auch eine kontextfreie Sprache.
Und jede Typ 1 Grammatik auch von Typ 0, aber eben nicht, da hatte ich
gerade auch auf hingewiesen, Typ 2 Grammatiken sind im Allgemeinen
nicht von Typ 1, wegen dieser Probleme mit dem leeren Wort auf der
rechten Seite.
Man kann aber zu jeder Sprache von Typ 2, zu jeder kontextfreien
Sprache, auch eine Grammatik finden, die diese Anforderungen der Typ 1
Grammatiken erfüllt, nämlich rechts kein leeres Wort hat, sondern nur
für das Startsymbol das leere Wort ermöglicht.
Und dann haben wir eine Grammatik von Typ 1 und damit ist das dann
auch eine Sprache von Typ 1.
Insofern ist also jede Sprache von Typ I auch eine Sprache von Typ I
-1.
Für I gleich 1, 2, 3.
Weil das ja alles nur Einschränkungen sind, bis auf diesen kleinen
Bruch da in der Mitte.
Übrigens noch eine kleine Bemerkung.
Ich hatte gesagt, rechtslineare Grammatiken könnten natürlich auch
Regeln definieren.
Statt rechtslinear könnte ich sagen, naja, es könnte ja auch sein,
dass ich nur Regeln habe dieser Art.
Dann hätte ich eine linkslineare Grammatik.
Das ist völlig symmetrisch.
Wir machen es zur Einfachheit, aber betrachten wir nur die
rechtslineare.
Das wäre also dann hier linkslinear.
Man kann auch sowas definieren wie linear.
Dann hätten wir sowas wie A auf ABC, solche Regeln.
Das wäre dann einfach nur linear.
Und das wäre dann schon was anderes als rechts- oder linkslinear.
Das ist dann schon Typ 2 und nicht mehr Typ 3.
Das werden Sie ziemlich bald einsehen können, warum das so ist.
Jetzt haben wir also diese Hierarchie von Grammatiken beschrieben.
Und jetzt noch der Begriff der Äquivalenz.
Das ist das, was dieser Aussage eigentlich zugrunde liegt.
Zwei Grammatiken heißen Äquivalent, wenn sie die gleiche Sprache
beschreiben.
Und das, was hier steht, ist eigentlich, ich kann zu jeder Grammatik
vom Typ I, für die Sprache, die von dieser Grammatik erzeugt wird,
auch eine Grammatik finden, die vom Typ I-1 ist.
Eine Äquivalente Grammatik.
Ich kann also Sprachen durch viele verschiedene Grammatiken erzeugen.
Wenn ich also die gleiche Sprache erzeuge, dann sind diese Grammatiken
Äquivalent.
Natürlich wird man dann sofort sagen, naja, wenn das so ist, dann will
ich natürlich immer die kleinstmögliche Grammatik erzeugen oder die
verwenden, weil ich dann die einfachste Art habe, die Grammatik zu
beschreiben.
Also das wird immer das Ziel sein, eine Sprache möglichst einfach
darzustellen, dann wird es auch effizienter sein, diese Sprache dann,
oder das Wortproblem für diese Grammatik zu lösen.
Und jetzt werden wir in den weiteren Dingen diese Sprachklassen
genauer untersuchen.
Das Ziel ist herauszufinden, was ist die Sprachklasse, die wir
brauchen, beziehungsweise was sind die Grammatiken, die wir brauchen,
um Programmiersprachen adäquat zu beschreiben.
Wir haben jetzt die Auswahl von Typ 3 bis Typ 0.
Irgendwo werden wir landen und können dann die Frage beantworten, wo
haben wir die notwendige Ausdrucksfähigkeit und wo ist immer noch die
akzeptable Effizienz vorhanden.
Und damit sind wir schon am Ende dieses einführenden Kapitels und
kommen dann zu dem Kapitel 2.
Und da geht es jetzt erstmal los, nicht mit Grammatiken, sondern jetzt
werden wir uns zunächst mal beschäftigen mit Automaten.
Wir schalten also etwas um.
Wir kommen später wieder zu den Grammatiken.
Aber wir fangen erstmal an jetzt damit, die andere Seite zu
betrachten, die analysierende Seite.
Wir haben gerade die Hierarchie der Sprachen beschrieben.
Die einfachsten sind die Rechtslinearen.
Sie können sich denken, dass dann dieser einfache Automatentyp,
endliche Automaten, da auch was mit zu tun hat.
Und das, was hier steht, in der Kapitelüberschrift, endliche
Automaten, ich muss erstmal umschalten auf den Stift, endliche
Automaten, reguläre Sprachen und auch die rechtslinearen Sprachen, das
sind eigentlich alles gleiche Begriffe, das sind die gleichen
Sprachklassen, nur unterschiedlich dargestellt.
Das ist der analysierende Ansatz, das ist der erzeugende Ansatz und
das ist der operationelle Ansatz, um Sprachen zu beschreiben.
Das heißt, in diesem Kapitel gebe ich Ihnen Beispiele für genau diese
verschiedenen Dinge, wobei wir, wenn wir mit Automaten anfangen,
zunächst mal noch allgemeiner sind und irgendwelche
informationsverarbeitenden Systeme darstellen wollen.
Das heißt, zunächst mal gehen wir einen Schritt zurück und sagen, was
sind eigentlich diese Systeme, mit denen wir etwas berechnen können.
Und das sind also endliche Automaten mit Ausgabe oder auch Maschinen,
im Englischen finden Sie oft den Begriff der Finite State Machines,
also Maschinen mit endlich vielen Zuständen.
Und Sie finden im täglichen Leben viele Beispiele dafür.
Zum Beispiel die Fahrkartenautomaten, Getränkeautomaten,
Geldautomaten, alle sehr einfach beschreibbar durch endliche
Automaten.
Sie haben alle die Gemeinsamkeit, dass Sie einen klar definierten
Ablauf von Handlungen haben, die dort ausgeführt werden können.
Sie haben eine selbsttätige Ausführung von Aktionen, es ist klar
definiert, was passiert, wenn Sie irgendeine Eingabe machen, wenn Sie
irgendeine Taste drücken oder ähnliches.
Dann ändert sich eventuell der Zustand Ihres Automaten und es wird
irgendeine Ausgabe erfolgen.
Sie werden etwas sehen können bei dem Automaten, was dann passiert.
Und wenn also diese Mengen der Eingaben, die Mengen der Zustände und
der Ausgaben endliche Mengen sind, dann reden wir von endlichen
Automaten.
Dazu gehört natürlich auch der Ablauf von Handlungen und ich muss
wissen, was in einem Zustand passiert, wenn irgendeine Eingabe gemacht
wird, was dann als nächster Zustand zu erwarten ist und was dann
außerdem an Ausgabe erzeugt wird.
Wir können das allgemein so darstellen, dass irgendwelche Eingaben
oder auch Folgen von Eingaben, dann haben wir Wörter, die eingegeben
werden, was dieser Automat damit macht und welche Ausgaben er dann
produziert.
Wir werden gleich viele Beispiele dafür sehen, an unterschiedlichen
Systemen, wo man solche Automaten verwenden kann.
Ganz allgemein eine informationsverarbeitende Maschine und wir nehmen
hier an, dass wir interne Zustände haben, dass der Automat kann sich
etwas merken, darüber, was er gerade oder was er bisher schon gesehen
hat und kann auf Basis dessen, was er bisher schon gesehen hat, etwas
Neues erzeugen.
So, das also zu unseren Automaten.
Jetzt können wir das ein bisschen anders darstellen.
Das erste war eine sehr abstrakte Darstellung, interne Zustände,
Eingabe, Ausgaben.
Jetzt machen wir das etwas formaler und wir sagen, wir haben etwas wie
ein Eingabeband.
Also ich habe noch tatsächlich angefangen, mit Automaten zu arbeiten,
die Eingabebänder hatten.
Wir hatten auf Lochstreifen unsere Programme geschrieben.
Lange her, da wurden die Programme eingelesen über einen Lochstreifen.
Wenn man dann Fehler gesucht hat, hat man so geguckt, ob irgendwo ein
Zeichen da ist.
Man kriegt natürlich Fehlermeldungen, konnte dann in dem Lochstreifen
ein Zeichen rausschneiden und Neues reinkleben und dann den Streifen
wieder abgeben.
Also das war eine ganz andere Art, wie man Fehler beseitigt hat.
Lange, lange her.
Inzwischen machen wir das alles etwas anders.
Aber abstrakt ist das so, dass wir eine Folge von Zeichen eingeben.
Hier sagen wir, wir haben dafür ein Eingabeband zur Verfügung.
Und dieses Eingabeband hat irgendwelche Felder, auf die wir eine
definierte Menge von Eingabesymbolen schreiben können.
Die sind aus unserer Eingabemenge E, das ist das Eingabealphabet.
Und wir sind in der Lage zu lesen, was auf diesen Feldern steht.
Wir haben also eine Einrichtung, um die Zeichen, die eingegeben
werden, zu lesen.
Das nennen wir ein Lesekopf.
Also kommt irgendwie aus der Anfangszeit, aber das ist abstrakt genau
das, was wir tun.
Und dann hat unser Automat oder die Steuereinheit dieses
informationsverarbeitenden Geräts interne Zustände, irgendwelche N
plus 1 viele Zustände, S0 bis Sn.
Normalerweise sagen wir, S0 ist der Anfangszustand.
Und wir nehmen an, dass wir etwas ausgeben können.
Abstrakt würden wir etwas schreiben auf ein Ausgabeband.
Das heißt, wir haben einen Schreibkopf und dieser Automat kann also
etwas auf ein Band schreiben.
Irgendwelche Zeichen aus einem definierten Zeichenvorrat, ein Alphabet
A.
Das ist ein Automat.
Und jetzt gibt es für die Modellierung solcher Automaten, für die
formale Modellierung, zwei verschiedene Alternativen.
Wir können uns überlegen, wann entsteht eigentlich diese Ausgabe.
Es ist interessant, dass man sich da prinzipiell unterschiedliche
Dinge überlegen kann.
Das eine ist, wir lesen etwas in einem Zustand und produzieren dann
die Ausgabe gleichzeitig mit dem Zustandsübergang.
Das ist ein sogenannter Milliautomat.
Milli waren Wissenschaftler, der sich mit solchen Automaten
beschäftigt hat.
Das andere ist ein Moore-Automat, nach einem Wissenschaftler, der
Moore mit Nachnamen hieß.
Und da wird die Ausgabe mit einem Zustand assoziiert.
Sie werden gleich noch sehen, was das für Unterschiede sind.
Das sind zwei prinzipielle Möglichkeiten.
Das heißt, beim ersten hängt die Ausgabe ab von Zustand und Eingabe.
Im zweiten Fall nur von einem Zustand.
Naja, können Sie sagen, was ist das schon wichtig?
Sie werden noch sehen, dass das durchaus wichtig sein kann.
Und jetzt definieren wir zunächst mal den Milliautomaten.
Formal haben wir also eine Eingabemenge, ein Eingabealphabet, ein
Ausgabealphabet, eine Zustandsmenge.
Und Sie sehen also hier, das sind n plus 1 Elemente.
Und in der Zustandsmenge R Zeichen im Eingabealphabet, M Zeichen im
Ausgabealphabet.
Und jetzt kommt die Handlungsweise, die Vorschrift, was macht der
Automat.
Da haben wir einmal die Angaben, wie Zustände abhängig von Eingaben in
Folgezustände übergehen.
Das ist die sogenannte Überführungs- oder Übergangsfunktion.
Und wir haben die Ausgabefunktion.
Und bei dem Milli, hatte ich gesagt, hängt die Ausgabe ab von Zustand
und eingegebenem Symbol.
Das ist die Ausgabe.
Und wir haben einen Anfangszustand S0.
Wir müssen wissen, wo wir normalerweise beginnen wollen.
Denn es ist klar, dass abhängig davon, was der Anfangszustand ist, wir
von dem Automaten unterschiedliche Ausgaben bekommen könnten.
Die Arbeitsweise kann also beschrieben werden durch das, was hier
angedeutet ist.
Ich hoffe, Sie können das auch hinten noch lesen.
Das, was hier vorne steht, zunächst einmal ist etwas, kann man sagen,
nach Definition vielleicht gar nicht erforderlich.
Technisch aber durchaus erforderlich.
Wenn wir einen Automaten einschalten, der soll anfangen zu arbeiten,
dann wissen wir ja gar nicht, was der Anfangszustand ist.
Dann müssten wir erstmal irgendeinen Reset-Knopf drücken und dafür
sorgen, dass der Automat in seinen definierten Anfangszustand kommt.
Dieses Reset-Knopf drücken ist praktisch hiermit angedeutet, bringe M
in den Zustand S0 auf irgendeine Art und Weise.
Der soll zu Anfang im Zustand S0 sein.
Wir nehmen normalerweise an, dass der standardmäßig im Anfangszustand
S0 ist, deswegen heißt der Anfangszustand S0.
Technisch müsste man das aber so machen, dass man erstmal dafür sorgt,
der ist zu Beginn in einem vorher bekannten definierten
Anfangszustand.
Und dann wollen wir natürlich, dass das Wort, was eingegeben werden
soll, auch vollständig gelesen wird.
Das heißt, wir fangen immer auf dem linkesten Zeichen an.
Das ist die erste Position und dann gehen wir...
hier steht der Pfeil nach links, der Pfeil soll andeuten, dass wir das
Band nach links bewegen.
Das heißt, zunächst steht das Band auf dem Lesekopf mit der linkesten
Position und dann wird sukzessive nach links bewegt.
Das linkeste Zeichen ist also das erste Zeichen, das wir lesen und
dann bewegen wir also oder lesen wir zunächst mal das, was dort steht.
Solange also ein Zeichen unter dem Lesekopf vorhanden ist, schreiben
wir gemäß der Ausgabefunktion ein Zeichen auf das Ausgabeband und
bewegen dann das Ausgabeband ein Zeichen weiter.
Deswegen auch hier der Pfeil nach links.
Gehen außerdem gemäß der Überführungsfunktion in einen Folgezustand
über, bewegen also dann den Lesekopf um ein Feld nach rechts
beziehungsweise schieben das Eingabeband um ein Feld nach links.
Genauso machen wir das mit dem Schreibkopf oder mit dem Ausgabeband
und dann haben wir wieder ein Zeichen unter dem Lesekopf und können
weitermachen.
Sehr einfache Arbeitsweise, das muss man natürlich genauso
hinschreiben.
Hätte ich Ihnen kaum erzählen brauchen, trotzdem muss man sowas
natürlich machen.
Für Übungen und Klausur setzen wir immer voraus, dass wir uns darum
gar nicht kümmern müssen.
Da gibt es mal wieder eine kurze Frage.
Warum beginnt das Ausgabealphabet nicht bei A0?
Naja, das ist etwas, das Ausgabealphabet, das ist einfach eine
Bezeichnungsweise.
Sie sind wahrscheinlich schon so geprägt durch Java und C und solche
Sachen, dass sie immer bei 0 anfangen zu zählen.
Aber wenn ich irgendeine Menge von Zeichen mit Indizes versehe, ich
fange halt mit 1 an.
Das ist eine reine Vereinbarungssache.
Wir haben die Zeichen des Eingabealphabets halt mit 1 beginnend
nummeriert.
Wir hätten auch bei minus 1 anfangen können oder bei 17, ist mir
völlig egal.
Wir müssen sie nur irgendwie bezeichnen.
Bei der Zustandsmenge ist einfach so, dass man sagt, ich möchte ja
gerne einen Anfangszustand haben, den ich S0 nenne.
Und hat sich so eingebürgert.
Es ist richtig, dass das vielleicht ein bisschen unsystematisch ist.
Man hätte auch alle beginnend mit der 0 anfangen können.
Aber das ist eigentlich egal.
Also das ist ein bisschen Freiheit bei der Modellierung.
In dem Fall vielleicht nicht ganz systematisch.
Aber es hängt einfach damit zusammen, dass wir einen definierten
Anfangszustand haben.
Was Sie dann als erstes auf das Ausgabeband schreiben, hängt ja von
der Ausgabefunktion ab.
Das muss nicht ein Zeichen A0 sein.
Sondern das ist irgendein Zeichen.
Jetzt ist die Frage, das war eine formale Definition.
Wie gehen wir eigentlich damit um?
Wie beschreiben wir eigentlich jetzt die einzelnen...
oder wie visualisieren wir uns das?
Also wenn ich sage, das ist eine Funktion, wie definieren Sie die
Funktion?
Und dafür gibt es verschiedene Möglichkeiten, Funktionen zu
definieren.
Ja, das schreibe ich mir auf für jedes Eingabe- für jedes
Eingabesymbol, für jeden Zustand, muss ich mir aufschreiben, was der
Automat damit machen soll.
Er hat zwei verschiedene Dinge, muss einen Folgezustand angeben und
muss ein Ausgabesymbol definieren.
Also, ich schreibe das einfach auf als eine Tafel, als eine Matrix.
Die Zeilen sind charakterisiert durch die Zustände.
Für jede Zeile habe ich einen Zustand.
Für jede Eingabe habe ich eine Spalte.
Das heißt, ich habe jetzt für jedes Eingabezeichen also eine Spalte.
Und da, wo sich jetzt Zeile und Spalte treffen, habe ich also
drinstehen, das, was der Automat machen soll.
Bei Eingabe von EEI im Zustand SJ, geht er über entsprechende
Übergangsfunktionen in einen Zustand SK und gibt außerdem
entsprechende Ausgabefunktionen das Zeichen AH aus.
Das sind also Folgezustand, Folgezeichen.
Das ist eine Möglichkeit, einen Automaten zu definieren, indem Sie für
jeden Zustand, für jedes Zeichen, auf diese Art und Weise in einer
Zustandstafel angeben, was der Automat machen soll.
Eine einfache Art und Weise.
Jetzt können Sie das noch anders darstellen.
Zum Beispiel so, dass Sie das über einen Graphen darstellen.
Jeder Zustand ist hier beschrieben durch einen Knoten SJ, SK.
Also hier, das war unser SJ, das ist SK.
Wir gehen mit der Übergangsfunktion im Zustand SJ mit Eingabe von EEI
in den Zustand SK und dabei wird der Ausgabefunktion das Zeichen AH
ausgegeben.
Das heißt, hier haben wir Kanten, die beschriftet sind mit den
Eingabezeichen, die den Übergang bewirken und der Ausgabe, die während
des Übergangs erzeugt wird.
Das ist also jetzt die andere Art und Weise.
Jetzt können Sie sich überlegen, was für Sie angenehmer ist.
Mal ist es angenehmer, eine Tafel zu schreiben, mal ist es angenehmer,
ein Zustandsdiagramm zu malen.
Das ist Geschmackssache.
Okay, das also zu dieser Art, wie wir Automaten aufschreiben können.
Das nochmal zu diesen Definitionen von Knoten, Kanten,
Kantenbeschriftungen, hatte ich Ihnen gerade alles erklärt.
Und jetzt kommen Beispiele.
Ein einfaches Beispiel ist aus dem normalen praktischen Leben
genommen, ein Tiefgaragentor.
Also Sie haben hier irgendeine Einfahrt und jetzt haben Sie, ich nehme
das mal wieder weg, Sie haben hier irgendein Tor, das wir uns
angucken.
Und dieses Tor hat irgendeine Tür.
So, so eine Tür.
Und jetzt kommt hier irgendein Auto an, das möchte da gerne
durchfahren, möchte gerne dahin kommen.
Wie funktioniert so eine Tür?
Das kann ich durch einen Automaten darstellen.
Was brauche ich dafür?
Das ist jetzt eine einfache Art, das wird, man wird der reale Automat,
das wird ein bisschen komplizierter sein.
Das hier ist eine mögliche Charakterisierung so eines Automaten.
Ich sage also, dieses Tor kann geschlossen sein, oder es kann auch
sein, dass dieses Tor offen ist.
Dann ist das irgendwie eingerollt oder was immer.
Das muss ich feststellen können.
Also das Tor kann geschlossen sein, das Tor kann offen sein und es
kann sein, dass es sich gerade bewegt.
Nach oben oder nach unten.
Aber es bewegt sich in beiden Fällen.
Ich hätte noch unterscheiden können, bewegt nach oben, bewegt nach
unten.
Ich habe nur gesagt, drei verschiedene Zustände.
Das Tor ist geschlossen, das Tor bewegt sich, das Tor ist offen.
Standardfall, Anfangszustand würden wir sagen, ist wahrscheinlich,
dass das Tor geschlossen ist.
Dann ist die Frage, wie wird das jetzt, was sind die möglichen
Eingaben?
Da kann man sich verschiedenste Dinge vorstellen, wie Eingaben hier
formuliert sind.
Ich sage einfach, es gibt einen Sensor, eine Eingabemöglichkeit, die
nenne ich, ein Auto kommt.
Hier kommt ein Auto, es gibt eine Wahrnehmung, da kommt ein Auto an,
das möchte da rein, kann auch sein, dass man eine Karte braucht, um
sich zu identifizieren oder ein Schlüssel oder ähnliches, oder eine
Fernbedienung im Auto hat.
Es gibt ein Signal, da kommt ein Auto an, das berechtigt ist,
durchzufahren.
Dann muss ich feststellen können, ob das Auto ganz durchgefahren ist,
wenn das Tor offen war.
Weil ich dann das Tor nämlich wieder zumachen möchte.
Auch das muss ich irgendwie feststellen können, durch eine
Lichtschranke oder ähnliches.
Dann muss ich feststellen können, ob das Tor offen ist oder zu ist.
Ich brauche also einen Torsensor, nenne ich den.
Hier ein Sensor, kann eine Lichtschranke sein und da unten ein Sensor.
Und dieser Sensor soll unterscheiden können, ob das Tor geschlossen
ist oder ob das Ding offen ist.
Also ob das Tor hier unten ist oder ob es da oben ist.
Okay.
Jetzt will ich auch etwas ausgeben können.
Was sehe ich an dem Tor?
Natürlich sehe ich, ob das offen oder zu ist.
Normalerweise habe ich aber auch noch eine Ampel, die rot oder grün
leuchten kann.
Je nachdem, ob sie rot oder grün ist, weiß ich, bei grün darf ich
durchfahren, bei rot darf ich nicht durchfahren.
Das ist das typische Bild eines Tiefgaragentores.
Und jetzt überlegt man sich, wie das Ganze funktioniert.
Wenn ich also im geschlossenen Zustand habe, ein Auto kommt an, dann
soll das Tor anfangen sich zu bewegen, die Ampel bleibt aber noch rot.
Dann kann es sein, ein seltsames Ereignis, das Tor ist noch
geschlossen und ein Auto ist durchgefahren.
Das ist irgendein fehlerhafter Wert, das heißt, da ist irgendjemand
auf der anderen Seite und hat da diesen Sensor ausgelöst, Auto ist
durch.
Da mache ich gar nichts, da bleibe ich im Zustand geschlossen und die
Ampel bleibt rot.
Genauso wenn das Tor geschlossen ist und der Sensor oben ist an, das
muss auch ein Fehler sein, da ändere ich gar nichts.
Oder auch wenn der Sensor unten anschlägt, ändere ich auch gar nichts.
Sondern darauf reagiere ich eigentlich nur, wenn das Tor bewegt wird.
Wenn das Tor bewegt wird und ein weiteres Auto kommt, dann bleibt das
in Bewegung, aber die Ampel bleibt rot.
Wenn das Auto durch ist, während das Tor sich bewegt, dann muss das
ein sehr flaches Auto gewesen sein, das einfach bei rot durchgefahren
ist, das ignoriere ich auch.
Es bewegt sich weiter und die Ampel bleibt rot.
Wenn der Sensor oben anschlägt, und ich bin ja auf dem Weg nach oben
gewesen, es war rot, dann sage ich, jetzt ist die Ampel grün.
Beziehungsweise, wenn der Sensor unten anschlägt und das Tor bewegt
sich, dann war das wohl der Fall, dass das Tor sich nach unten bewegt
hat, und dann ist das das Zeichen dafür, dass das Tor geschlossen ist,
und die Ampel muss natürlich rot sein in dem Fall.
Untersprechend haben wir hier die Übergänge für das offene Tor, dass
wenn noch ein weiteres Auto kommt, dann die Ampel noch offen bleibt
und es bleibt grün.
Wenn ein Auto durch ist, geht man in den Bewegen-Zustand über und
schaltet sofort auf rot.
Wenn das Tor offen ist und der Sensor oben wird angeschlagen, dann ist
das irgendein Fehler, das heißt, wir ändern nichts weiter, genauso
wenn der Sensor unten angeht und das Tor ist offen, machen wir auch
nichts weiter.
Das ist hier die Tafel.
Jetzt können Sie sich überlegen, was ist einfacher, die Tafel oder
das, was ich hier unten gemalt habe, das Diagramm.
Drei Zustände, die möglichen Übergänge sind alle angedeutet.
Wie komme ich von einem geschlossenen Tor zu einem offenen Tor?
Nur über den Zustand, dass es sich bewegt hat, und das kann in dieser
Richtung laufen, kann aber auch in der Richtung laufen.
Das ist also das, was Sie hier sehen.
Auf die Art und Weise haben Sie hier die verschiedenen Übergänge.
Das ist nicht eine perfekte Modellierung, in der Realität würde man
das etwas komplizierter machen.
Ich wollte einfach nur ein einfaches Beispiel geben.
Sie werden hier sofort einige Fehlerzustände oder irgendwelche Folgen
von Übergängen feststellen können, die vielleicht in der Realität so
nicht gewünscht sind, aber so für die Standardfälle reicht das.