Guten Morgen zusammen.
Wir werden jetzt erst mal die Evaluation der Vorlesung vornehmen.
Also Sie kriegen diesen Bogen und können ihn bitte ausführen.
Dann geht es weiter mit der Vorlesung.
Wir fangen heute mit einem neuen Kapitel an, und zwar Grammatiken.
Und das Schöne an dem Kapitel ist, dass en passant im Prinzip alle
anderen Themen der Vorlesung, die wir bisher hatten, gestreift werden.
Sie werden sehen, dass dieses Thema Grammatiken relativ eng verbunden
ist mit dem ersten Thema, reguläre Sprachen und Automaten.
Aber wir gehen über diese sehr eingeschränkte Sprachklasse der
regulären Sprachen hinaus.
Aus Grundbegriffen der Informatik kennen Sie schon einiges aus dem
Kapitel, aber bei Weitem nicht so vertieft.
Was Sie sehr schnell sehen werden, ist, kontextfreie Grammatiken
werden hier wieder thematisiert und dann aber deutlich ausführlicher
als das in Grundbegriffen der Informatik der Fall ist.
Also Grammatiken, das ist das Thema.
Grammatiken, das wissen Sie, das sind Regelsysteme, mit denen sich die
Wörter einer vorgegebenen Sprache erzeugen lassen.
Und wir machen jetzt einfach ein paar Beispiele.
Und das erste Beispiel ist vielleicht so ein bisschen ungewöhnlich.
Das ist aber insofern sinnvoll, als dass es, das werden Sie gleich
sehen, den Bezug zu dem Thema Komplexitätsklassen auch herstellt.
Also wir betrachten Klicken in einem Graph.
Und wir wollen jetzt die Sprache aller Graphen, die eine Klicke der
Größe, Anzahl der Knoten des Graphen durch zwei haben, beschreiben.
Wie baut die sich auf?
Man wählt erstmal die Anzahl der Knoten des Graphen.
Also in der Sprache sollen alle Graphen sein, kleine, große.
Für die gilt, Sie haben eine Klicke, deren Knotenzahl mindestens die
Hälfte der Knoten des Graphen enthält.
Also wir wählen erstmal die Größe des Graphen.
Als zweites wählen wir eine Teilmenge der Größe V durch 2.
Dann werden alle Knotenpaare in dieser Teilmenge durch eine Kante
verbunden.
Und dann fügen wir noch weitere Kanten ein in den Graph.
So, auf die Art bekommen wir Festlegung von dem N und der Wahl der
Teilmenge der Größe N halber und der Zugabe von weiteren Kanten in
irgend so einen Graph, der eine Klicke der Größe N halber hat.
Also insbesondere ist dieses Regelsystem, das sind ja einfach vier
Regeln, nicht deterministisch, denn die Wahl N ist nicht
deterministisch.
Da können Sie jetzt mal ein anderes N wählen.
Die Wahl der Teilmenge der Größe N halber ist nicht deterministisch
und die Zugabe weiterer Kanten ist nicht deterministisch.
Schritt 3 ist natürlich deterministisch.
Wenn Sie die Teilmenge gewählt haben, dann müssen alle Knotenpaare in
der Teilmenge durch eine Kante verbunden werden.
Also durch diese Regeln könnten Sie die Sprache aller Graphen, die
eine Klicke der Größe, Mächtigkeit oder Anzahl der Knoten des Graphen
durch 2 hat, aufbauen.
Deutlich bekannter ist Ihnen wahrscheinlich dieses Beispiel
arithmetische Ausdrücke.
Wenn A ein Symbol ist aus dem vorgegebenen Alphabet, dann ist A, A
plus A und A mal A, ein arithmetischer Ausdruck, jeweils ein
arithmetischer Ausdruck.
Und wenn Sie arithmetische Ausdrücke haben, Groß A1 und Groß A2,
können Sie aus diesen neueren arithmetischen Ausdrücken bauen.
Durch die Operation Plus oder die Operation Mal.
Wobei wir hier jeweils um arithmetische Ausdrücke, die sozusagen ein
Teil von einem neuen arithmetischen Ausdruck sind, Klammern machen,
was nicht immer notwendig ist.
So, und Grammatiken sind eben solche Regelsysteme, die den Aufbau von
Sprachen beschreiben.
Und wie sieht das formal aus?
Definition einer Grammatik formal.
Die Grammatik besteht aus dem Eingabealphabet Sigma, das ist ein
endliches Alphabet, wie bisher immer, der Variablenmenge V, die
ebenfalls endlich ist, einer Startvariable S, S ist also Element von
V, und einer Menge von Regeln.
Also endliches Alphabet.
Dieses Sigma wird auch Alphabet der Terminalsymbole oder
Terminalalphabet genannt, im Gegensatz zu den Variablen oder Nicht
-Terminale.
Also V ist die Menge der Variablen oder Nicht-Terminale.
Natürlich sollen V und Sigma einen leeren Schnitt haben.
S ist eben eine ganz bestimmte Variable aus V.
Und die Musik spielt in den Ableitungsregeln R.
Wie sieht so eine Regel R aus?
Die besteht aus einer linken und einer rechten Seite.
Und die linke Seite ist ein Wort, das nicht leer sein soll, über V
vereinigt Sigma.
Und die rechte Seite ist auch ein Wort über V vereinigt Sigma und das
kann sogar leer sein.
Wir haben also einfach als Regeln solche Paare, linke Seite, rechte
Seite, mit der Bedeutung, die linke Seite kann durch die rechte
ersetzt werden.
Das schreiben wir dann auch so.
L, was die linke Seite beschreibt, Pfeil R, R beschreibt die rechte
Seite.
Nochmal, was heißt Ersetzung?
Wenn in einem Wort Z das Wort L als Teilwort vorkommt und wir die
Regel L, R haben, dann darf L in Z durch R ersetzt werden.
Wenn man auf ein ganzes Wort W so eine Ableitungsregel anwendet, die
dazu führt, dass das W zu Z wird, dann benutzen wir auch diesen Pfeil,
dieselbe Schreibweise wie für so eine Regel.
Und wenn durch mehrere Regelanwendungen aus dem Wort W das Wort Z
wird, dann benutzen wir als Schreibweise so einen Pfeil mit einem
Sternchen drüber.
Wenn die Anzahl der Regelanwendungen eine Rolle spielt, schreiben wir
auch schon mal die Anzahl der Regelanwendungen hier rüber.
Aber das Sternchen besorgt einfach eine gewisse Anzahl von
Regelanwendungen, führt dazu, dass W zu Z wird.
Und die durch so eine Grammatik erzeugte Sprache, Grammatik G, also
Sprache L von G, ist einfach die Menge der Wörter Z aus Sigma
Sternchen, für die gilt, das Startsymbol oder die Startvariable lässt
sich durch eine gewisse Anzahl von Regelanwendungen überführen in Z.
Wir schauen auf die Startvariable und was man alles aus der
Startvariable bekommen kann durch Anwendungen von Regeln,
Grammatik, derart, dass die Wörter aus Sigma Stern sind, das sind die
Wörter der durch die Grammatik erzeugten Sprache.
Gut, dann schauen wir uns einfach mal die Grammatik für die Menge
aller arithmetischen Ausdrücke an.
Hier wählen wir als Alphabet Sigma, Klammer auf, Klammer zu, klein a,
plus und mal.
Also hier spezielle arithmetische Ausdrücke wollen wir haben, nur
arithmetische Ausdrücke, bei denen a vorkommt.
So, als Variablen brauchen wir hier nur eine Variable, nämlich die
Startvariable, und wir brauchen folgende Regeln.
S, die Startvariable, kann ersetzt werden durch S in Klammern plus S
in Klammern, S kann ersetzt werden durch S in Klammern mal S in
Klammern, S kann ersetzt werden durch klein a, S kann ersetzt werden
durch a plus a, und S kann ersetzt werden durch a mal a.
So, das war jetzt ganz schnell sozusagen die Definition von
Grammatiken und ein kleines Beispiel, da Sie ja Grammatiken kennen.
Was Sie wohl noch nicht kennen, soweit ich Grundbegriffe der
Informatik gesehen habe oder die Folien, ist die gesamte Chomsky
-Hierarchie.
Sie kennen die eine oder andere Sprache oder Grammatik aus der
Hierarchie, aber nicht alle.
Wir bauen also jetzt eine Hierarchie von Grammatiken aus, indem wir
sozusagen einschränken, wie die Regeln aussehen dürfen.
Und das am wenigsten Eingeschränkte ist die Typ-Null-Grammatiken.
Wir machen einfach keine weiteren Einschränkungen an die Regeln.
Die Regeln dürfen einfach so aussehen, wie wir es in der Grammatik
hatten.
Also links und rechts können irgendwelche Wörter stehen über Sigma
vereinigt V, also irgendwelche gemischten Wörter mit Variablen und
Symbolen aus Sigma drin und die einzige Einschränkung, die wir hatten,
ist, dass auf der linken Seite nicht das leere Wort stehen darf.
Aber ansonsten können Sie sozusagen beliebiges durch beliebiges
ersetzen.
Das wäre sozusagen Typ-Null.
Keine Einschränkung an das Aussehen der Regeln.
Typ-Eins, das sind die kontextsensitiven Grammatiken.
Das sind Grammatiken, die ausschließlich Ableitungsregeln in der
folgenden Form enthalten.
Links stehen nur Variablen.
Wieder nicht das leere Wort, aber es dürfen links keine Symbole aus
Sigma stehen.
Und rechts, da können wir jetzt mehr oder weniger beliebige Worte
bilden.
Aus technischen Gründen sagen wir, das leere Wort soll nicht dabei
sein.
Und die Start-Variable soll auch rechts nicht vorkommen.
Und damit wir potenziell auch Sprachen, die das leere Wort enthalten,
konstruieren können, sagen wir noch, aus der Start-Variable darf auch
das leere Wort abgeleitet werden.
Und dann ist die einzige weitere Einschränkung, dass die rechte Seite
mindestens so lang wie die linke Seite sein soll.
Wir wollen sozusagen nicht verkürzen durch Anwenden einer
Ableitungsregel und sozusagen die Worte kürzer machen.
Das ist praktisch das, was wir hier als Einschränkungen haben.
Dass man jetzt also links nur Variablen hat, das ist entscheidend.
Bei allen weiteren Einschränkungen, da kommen wir nochmal drauf
zurück, das ist ja relativ wenig eingeschränkt, dass man sagt, naja
gut, da rechts darf nicht das leere Wort stehen im Allgemeinen, nur
wenn links es steht.
Und ansonsten muss das da rechts, was auf der rechten Seite steht,
mindestens so lang sein wie das, was auf der linken Seite steht.
Also das ist ja nicht sehr restriktiv.
Zu den Namen kontextsensitiv und dann kontextfrei kommen wir nochmal.
Die nächste Einschränkung ist jetzt folgende.
Links darf nur eine Variable stehen, nur eine.
Also Typ 2, wir gehen hier von aus- und schränken weiter ein.
Typ 2 oder kontextfreie Grammatiken sind Grammatiken, die
ausschließlich Ableitungsregeln der folgenden Form haben.
Links steht eine Variable und rechts ein beliebiges Wort über V
vereinigt Sigma.
Also rechts kann auch das leere Wort stehen.
Links nur eine Variable.
So und jetzt schränken wir noch weiter ein, dann kommen wir zu den Typ
3 Grammatiken, die auch rechtslinear genannt werden.
Da erlauben sie ausschließlich Ableitungsregeln, wo links eine
Variable steht, wie schon bei kontextfrei.
Und rechts ein sehr speziell aussehendes Wort V, nämlich das V kann
entweder das leere Wort sein oder das V sieht so aus, das ist ein
Symbol, klein a aus Sigma, gefolgt von einer Variablen, groß b aus V.
Also rechts haben sie immer nur, entweder das leere Wort oder immer
nur Symbol aus dem Eingabealphabet zusammen mit einer Variablen.
Ein sehr eingeschränktes Aussehen der rechten Seite.
Linke Seite nur eine Variable, das hat man schon bei kontextfreien
Grammatiken gefordert.
Gut, also das ist die sogenannte Chomsky-Hierarchie und die werden wir
eins nach dem anderen durchgehen.
Was ist denn Sinn und Zweck jetzt der ganzen Angelegenheit?
Naja gut, im Prinzip wissen sie aus Grundbegriffe der Informatik und
auch aus dem ersten Kapitel, warum man solche Regelsysteme, mit denen
man Sprachen erzeugen kann, überhaupt betrachtet.
Wir wollen schauen, welche Sprachen, welche Regelsysteme sind geeignet
für Programmiersprachen und wir wollen jetzt in Abhängigkeit davon,
wie restriktiv ein Regelsystem ist, das wir angucken, zwei Sachen
ansehen.
Wie mächtig ist das Regelsystem?
Kann man da auch sinnvolle Sprachen, Sprachen, die für
Programmiersprachen sinnvoll sind, überhaupt mit erzeugen?
Wenn Sie sich erinnern an die regulären Sprachen, die wir im ersten
Kapitel hatten, da haben wir festgestellt, die Klasse der regulären
Sprachen ist doch sehr eingeschränkt.
Damit bekommen wir noch nicht mal korrekte Klammerausdrücke.
Also das ist sozusagen der eine Aspekt, wie eingeschränkte oder breite
Klassen von Sprachen bekommt man über solche Regelsysteme.
Und die andere Seite der Medaille ist es, wie komplex es bei den
entsprechenden Sprachen ist, das Wortproblem zu lösen.
Bei regulären Sprachen haben wir gesehen, das kann man recht einfach
machen, da braucht man nur einen endlichen Automaten für.
Wir wissen jetzt natürlich auch, dass es deutlich komplexere Sprachen
gibt.
Sprachen, die in die Klasse der NP-Vollständigen Probleme reinfällt,
Sprachen, die noch nicht mal entscheidbar sind.
Und sozusagen diese Konzepte, wie man Sprachen nach ihrer Komplexität
beziehungsweise nach der Frage, ob sie überhaupt entscheidbar sind
oder nicht, einteilen kann, wollen wir sozusagen zusammenbringen mit
solchen Regelsystemen.
Das heißt, wir werden bei jedem dieser Regelsysteme uns fragen, wie
mächtig sind die Sprachklassen, die dadurch erzeugt werden einerseits
und andererseits, wie komplex ist es, in der entsprechenden
Sprachklasse das Wortproblem zu entscheiden, also zu entscheiden, ob
ein vorgegebenes Wort in der vorgegebenen Sprache ist.
Und, dritter Aspekt, wir werden sozusagen die zugehörigen
Maschinenmodelle uns angucken.
Bei den regulären Sprachen wissen wir, das zugehörige Maschinenmodell
ist der endliche Automat.
Und was die Mächtigkeit des endlichen Automaten angeht, gibt es
grundsätzlich keinen Unterschied zwischen deterministisch und nicht
-deterministisch.
Das andere Maschinenmodell, was sozusagen am anderen Ende ist,
bezüglich wir können, ist die Turing-Maschine.
Auch da haben wir festgestellt, deterministische und nicht
-deterministische Turing-Maschinen sind im Prinzip gleich mächtig,
auch wenn sich das in Komplexität von Laufzeiten dann unterscheidet,
was man mit einer deterministischen und was man mit einer nicht
-deterministischen Turing-Maschine machen kann.
Die Frage ist zum Beispiel jetzt, gibt es da irgendwas Sinnvolles
dazwischen und wie korreliert das hier zu dieser Hierarchie?
Gut.
Gehen wir die einfach mal der Reihe nach durch.
Und jetzt erstmal, ich habe angekündigt, der Name, warum heißt
diese Typ 1
Grammatiken kontextsensitiv und Typ 2 kontextfrei.
Da wollen wir uns jetzt erstmal kurz über verständigen.
Ja, warum heißt Typ 1 kontextsensitiv?
Also bei Typ 1 haben wir Regeln, die folgendermaßen aussehen.
Links steht ein Wort über der Variablenmenge.
Und rechts steht ein Wort, das kann so ein gemischtes Wort sein aus
Variablen und Symbolen aus dem Eingabealphabet und die Einschränkung
ist, das ist, wenn links nicht nur S steht, nicht das leere Wort und
die rechte Seite ist nicht kürzer als die linke Seite.
Und was können sie mit solchen Regeln machen?
Da könnten sie zum Beispiel die Situation haben, dass sie ABC ableiten
dürfen zu AXYC einfach weil sie eine entsprechende Regel haben, aber
DBC nicht zu DXYC ableiten können.
Also hier ABC nach AXYC sieht ja so aus als würde da einfach nur B
durch XY ersetzt.
Und es kann eben sein, dass sie so eine Regel haben, die sagt ja, hier
in diesem Kontext darf B durch XY ersetzt werden.
Das heißt aber nicht, dass in jedem beliebigen Kontext B durch XY
ersetzt werden darf.
Es kann sein, dass aber trotzdem das hier nicht geht.
Einfach weil sie nur eine Regel haben, ABC darf abgeleitet werden zu
AXYC, aber nicht eine Regel haben, DBC abgeleitet zu DXYC.
Bei kontextfreien Grammatiken ist das anders.
Weil bei kontextfreien Grammatiken steht hier links eine einzelne
Variable.
Und wenn sie für die einzelne Variable, meinetwegen B, haben, die
Regel haben, B darf abgeleitet werden zu XY, dann darf B immer zu XY
abgeleitet werden, auch wenn sie ein Wort haben, wo um das B herum
noch alles Mögliche andere steht.
Also das ist sozusagen unabhängig vom Kontext bei kontextfreien
Sprachen oder Grammatiken, ob ein B in gewisser Weise ersetzt werden
darf, während das bei kontextsensitiven Grammatiken vom Kontext
abhängt.
Okay.
Ich glaube, das ist jetzt klar, diese Unterscheidung, kontextsensitiv,
kontextfrei von der Name von den beiden Grammatiken.
So, dann fangen wir mal ganz oben an bei den Typ-Null-Grammatiken.
Also ich habe gesagt, wir interessieren uns unter anderem dafür, wie
mächtig die entsprechenden Sprachklassen sind und wie komplex jeweils
das Wortproblem ist in den Sprachklassen.
So, und bei Typ-Null-Grammatiken kann man Folgendes beweisen.
Falls wir eine rekursiv aufzählbare Sprache haben, oder mit anderen
Worten eine semi-entscheidbare Sprache, so gibt es eine Chomsky-Null
-Grammatik, für die gilt, L ist gerade die Sprache zu dieser Grammatik
durch diese Grammatik erzeugt worden.
Okay, das heißt also Chomsky-Null-Grammatiken, das ist riesig, da
fällt alles Mögliche rein, sogar solche semi-entscheidbaren Sprachen,
die ja nicht notwendig entscheidbar sind.
Also auch nicht entscheidbare Sprachen.
Schauen wir uns das einfach mal an, wie man argumentieren kann, dass
dem so ist.
Wenn wir eine rekursiv aufzählbare Sprache haben, dann gibt es eine
Turing -Maschine, die die Sprache akzeptiert.
Wir können annehmen, die ist deterministisch.
Wenn Sie sich recht erinnern, dann war das in dem Kapitel
Entscheidbarkeit so, dass wir sowieso nur deterministische Turing
-Maschinen angeschaut haben.
OBDA kann diese Turing-Maschine M so aussehen, dass sie genau einen
akzeptierenden Endzustand hat.
Und OBDA soll sie so arbeiten, dass auf dem Band nur Planks stehen,
wenn dieser akzeptierende Endzustand Qj erreicht wird.
Und Q0 soll nur in der Anfangskonfiguration vorkommen.
Und wir konstruieren jetzt eine Grammatik vom Typ 0, die also keine
weiteren Einschränkungen erfüllt, die praktisch diese Berechnung der
Turing -Maschine M nachbildet.
Man kann sagen, wenn man Grammatiken oder Berechnungen von Maschinen
in Grammatiken übersetzt oder die entsprechende Grammatik aufstellt,
dann muss man das, was die Maschine bei einer akzeptierenden
Berechnung macht, im Prinzip rückwärts durchlaufen.
Wir konstruieren eine Grammatik, die die Berechnung der Turing
-Maschine M in gewisser Weise rückwärts durchläuft.
Und das sieht so aus, wenn wir den Übergang DeltaQA gleich DeltaQ-A-R
haben, dann enthält die Grammatik die Regel A-Q- wird ersetzt durch Q
-A.
Wenn wir den Übergang haben, DeltaQA gleich Q-A-L, also vom Zustand Q
geht es in den Zustand Q-A wird ersetzt durch A- und der Kopf der
Turing -Maschine geht danach einen Schritt nach links, dann brauchen
wir in der Grammatik die Ableitungsregel Q-B A- für beliebigiges B aus
Gamma Bandalphabet wird ersetzt durch B-Q-A und wenn wir den Übergang
haben DeltaQA gleich Q-A-N dann brauchen wir in G die Ableitungsregel
Q -A- wird ersetzt durch Q-A.
Genau, das habe ich vergessen zu erwähnen.
Wir müssen natürlich sagen, wie diese Grammatik aussieht, die wir da
konstruieren, die hat dasselbe Eingabealphabet, das ist klar und die
Variablenmenge besteht aus dem Bandalphabet vereinigt der
Zustandsmenge, vereinigt dem Startsymbol von unserer Turing-Maschine
und der Startvariablen Bandalphabet vereinigt Q der Turing-Maschine
und eine Startvariable, die wir zusätzlich brauchen, S, das ist also
sozusagen unsere ausgezeichnete Startvariable und die Regeln, das ist
das, was wir gerade hier konstruieren.
Wir müssen dann außerdem noch die Schlusskonfiguration erzeugen, also
dafür sorgen, dass in unserer Grammatik die richtigen Regeln sind, um
sozusagen das, was am Schluss der akzeptierenden Berechnung passiert,
abzubilden.
Dafür brauchen wir eine Regel S Startvariable wird ersetzt durch Qj,
Qj wird ersetzt durch PlankQj und Qj wird ersetzt durch QjPlank.
Hat mir gesagt, bei der akzeptierenden Schlusskonfiguration sollen nur
noch Planks auf dem Band stehen.
Und dann haben wir diese Regeln aus der Rückwärtsberechnung und dann
brauchen wir sozusagen noch die Schlussregeln, also wenn die
Anfangs...
die Eingabe oder Anfangskonfiguration ist Zugungmaschine ist im
Zustand Q0 und das Wort W1-Wn steht auf dem Band, W1-Wn ist also eine
beliebige Eingabe, dann brauchen wir die Regeln PlankQ0 wird ersetzt
durch Q0, Q0A wird ersetzt durch AQ0 Q0Plank wird ersetzt durch Q0 und
Q0 wird ersetzt durch Y.
Und wenn man das hat, dann können alle Wörter W aus L durch G erzeugt
werden, indem einfach die Berechnung von M rückwärts durchlaufen wird.
Wir gucken einfach jeden Übergang, den M macht und von hinten, von dem
letzten, vorletzten und so weiter nach vorne betrachtet und führen
dann in der Grammatik die entsprechende Regel durch.
Und natürlich kann man dann umgekehrt mit G nur Berechnungen von
dieser Führungmaschine M, von der wir ausgegangen sind, erzeugen oder
wiedergeben.
Die von Typ Null Grammatiken G erzeugten Sprachen sind rekursiv
aufzählbar.
Wir konstruieren jetzt, weil es einfacher geht, eine nicht
deterministische Turingmaschine, die genau die Sprache akzeptiert, die
durch die Grammatik G produziert wird.
Wie machen wir das?
Erstmal schreiben wir S auf das Band, dann wählen wir eine beliebige
anwendbare Ableitungsregel aus, vergleichen das erzeugte Wort mit der
Eingabe.
Bei Gleichheit wird die Eingabe akzeptiert.
Ansonsten springen wir nicht deterministisch wieder nach zwei und
nicht deterministisch wird einfach eine weitere anwendbare
Ableitungsregel ausgewählt.
Wenn W aus L von G ist, gibt es eine akzeptierende Berechnung.
Wir haben jetzt eine nicht deterministische Turingmaschine gebaut zu
einer beliebigen Typ Null Grammatik erzeugte Sprache.
Jetzt könnte man sich an dem nicht deterministisch stören.
Das wird in der Übung dann nochmal thematisiert.
Dass man dann natürlich auch eine deterministische Turingmaschine
konstruieren kann, die dasselbe leistet.
Damit sind wir jetzt schnell durch.
Typ Null Grammatiken sind einfach zu weit.
Da fallen insbesondere nicht entscheidbare Sprachen rein.
Um es gleich mal auf den Punkt zu bringen.
Die Klasse der rekursiv aufzählbaren Sprachen ist genau die Klasse der
von einer deterministischen Turingmaschine akzeptierten Sprachen ist
genau die Klasse der von einer nicht deterministischen Turingmaschine
akzeptierten Sprache so weit so gut.
Und das ist aber genau die Klasse der von Typ Null Grammatiken
erzeugten Sprachen.
Was also insbesondere heißt, es gibt Sprachen, die durch eine Typ Null
Grammatik erzeugt werden, die nicht entscheidbar sind.
Als Grundlage für Programmiersprachen sind also Typ Null Grammatiken
vermutlich zu allgemein.
Okay, das war jetzt sozusagen ganz oben in der Hierarchie das am
wenigsten restriktive Regelsystem oder die am wenigsten restriktiven
Grammatiken.
Jetzt gehen wir mal nach unten zu den restriktivsten Typ 3 oder
Rechtslinear.
Warum heißen die Rechtslinear?
Naja gut, weil die Regeln so aussehen.
Auf der rechten Seite steht immer ein Wort, was einfach nur aus einem
Symbol aus Sigma gefolgt von einer Variablen aus V besteht.
Jetzt wollen wir mal gucken, was das eigentlich für Regelsysteme sind,
diese Typ 3 Grammatiken oder Rechtslinearen.
Ja, das wird sich sehr schnell zeigen, dass sie gerade die regulären
Sprachen erzeugen.
Die Klasse der von endlichen Automaten akzeptierten Sprachen ist genau
die Klasse von Chomsky 3 Grammatiken erzeugten Sprachen.
Die von endlichen Automaten erzeugten Sprachen sind ja gerade die
regulären Sprachen.
Das heißt also Chomsky 3 oder Typ oder Rechtslinear bedeutet gerade
regulär.
Um das zu zeigen, muss man zwei Richtungen zeigen.
Wir betrachten den endlichen Automaten und die davon akzeptierte
Sprache und zeigen dazu, kann man eine Chomsky 3 Grammatik angeben und
andererseits, wir haben eine Chomsky 3 Grammatik und zeigen, dass zu
der entsprechenden Sprache auch ein endlicher Automat angegeben werden
kann.
Also wir haben einen endlichen Automaten, können uns einen
deterministischen Automaten vorgeben, weil deterministisch und nicht
deterministisch endliche Automaten ja gleiche können.
Also wir haben einen D-A-A-L, der sieht so aus, Zustandsmenge hat eine
Zustandsmenge Q, Eingabealphabet Sigma, Übergangsfunktion Delta,
Anfangszustand Q0 und Endzustandsmenge F.
Und wir zeigen, dass es dazu eine Typ 3 Grammatik GL gibt, für die
gilt L von AL ist gerade L von GL.
Das heißt also, wir müssen jetzt die akzeptierenden Berechnungen von
dem D-A-A angucken und gucken, wie die Übergänge, die da gemacht
werden, in Regeln übersetzt werden können, in Regeln einer
Rechtslinearen Grammatik oder Typ 3 Grammatik.
Und das machen wir wieder sozusagen wie eben, als wir so eine
Berechnung, eine akzeptierende Berechnung einer Turing-Maschine
angeguckt haben, dass man rückwärts schaut, was ist denn im letzten
Schritt beim Akzeptieren passiert, was braucht man dafür in der Regel
und so weiter.
Die Grammatik folgendermaßen definiert, die Variablenmenge ist gerade
die Zustandsmenge unseres D-A-A.
Die Startvariable entspricht gerade dem Anfangszustand Q0 und wir
haben folgende Regeln, wenn Q Endzustand ist, dann haben wir die Regel
Q jetzt als Variable, wird ersetzt durch Epsilon und wenn es,
ansonsten, wenn es einen Übergang gibt, Delta Q A, gebliebiges A
gleich Q Strich, dann haben wir die Regel Q kann ersetzt werden durch
A Q Strich.
Sieht gut aus.
Kann aussehen der Regel.
Jetzt schauen wir also mal ein Eingabewort W an.
Das Wort W1 bis WN und wir schauen uns an, was AL bei Abarbeitung
dieses Wortes macht.
AL durchläuft Zustände, beginnen von Q0, enden bei einem Endzustand,
das seien jetzt mal Zustände Q0 bis QN können Zustände doppelt drin
vorkommen, aber einfach, die sind jetzt nummeriert danach, als wieviel
der Zustand in dem Abarbeiten von W1 bis WN der Zustand besucht wurde.
QN ist in F.
Ja, wenn man das einfach dann übersetzt, was da passiert in die
entsprechenden Regeln, die wir in unsere Grammatik reingepackt haben,
dann heißt das ja, wir haben die Regel Q0 wird ersetzt durch W1Q1 und
da wir dann die Regel haben, Q1 wird ersetzt durch W2Q2, kann man also
W1Q1 weiter ableiten zu W1W2Q2 und so weiter alle diese Regeln bis zu
WQN wird abgeleitet zu W, weil QN Endzustand ist also durch Y ersetzt
werden.
Und natürlich gilt für alle Ableitungen der Grammatik, die wir da
gerade definiert haben, dass es eine entsprechende akzeptierende
Berechnung des Ausgangsautomaten D, A, AL gibt.
Und zur anderen Richtung, das ist ähnlich leicht, wir müssen also
jetzt zu einer Typ 3 Grammatik GL einen endlichen Automaten angeben,
der dieselbe Sprache akzeptiert, die durch die Grammatik erzeugt wird,
und dann machen wir uns das Leben wieder leicht, indem wir einen NEA
angeben.
Die Zustandsmenge des NEA entspricht gerade der Variablenmenge unserer
Grammatik, der Anfangszustand entspricht der Startvariablen unserer
Grammatik, die Endzustandsmenge entspricht gerade den Variablen A aus
V, für die gilt, es gibt eine Regel, A wird ersetzt durch Y.
Und die Übergangsfunktionen, die können wir einfach, also alle
möglichen Übergänge können wir einfach an den Regeln ableiten, die
ablesen.
Die Regeln unserer Grammatik sehen ja alle so aus, links ist eine
Variable A und rechts ein Wort, klein a b.
Und für jede dieser Regeln tun wir b, sagen wir b soll der
Folgezustand sein entsprechend Delta, wenn wir im Zustand a, klein a
lesen.
Also Delta groß a, klein a ist gerade Menge der b, für die gilt, a
nach klein a b ist eine Regel in unserer Grammatik.
Das ist jetzt hier nicht deterministisch, aber das macht ja nichts,
weil es Wahlmöglichkeiten geben kann.
So, und jetzt gucken wir uns also ein Wort aus der Sprache der
Grammatik GL an.
Dieses Wort lässt sich also mit Anwendung der Regeln aus der Grammatik
GL ableiten, und so eine Ableitung sieht also so aus, wenn das Wort w1
bis wn ist, dann geht es los mit dem Startsymbol s, von s kann w1 a1
abgeleitet werden, a1 kann man weiter zu w2 a2 ableiten, und so
weiter.
Also durch solche Regelanwendungen kommen wir zu w von s aus, so muss
das sein, weil die Regeln von GL gerade diese eingeschränkte Form
haben.
Wenn wir dann jetzt gucken, was der entsprechende Automat, den wir
gerade definiert haben, dann bei Eingabe dieses Wortes w macht, dann
ist das nichts anderes als dass es vom Startsymbol durch Lesen von w1
nach a1 geht, von a1 durch Lesen von w2 nach a2, und so weiter, und
schließlich bei an endet, und an ist gerade nach unserer Definition
ein Endzustand, also wird dann w akzeptiert.
Und natürlich kann es auch nur für
Worte, die mit Regeln von GL ableitbar sind, überhaupt solche
akzeptierenden Berechnungen in dem von uns definierten Automaten ARL
geben.
Okay.
Was wir jetzt gelernt haben, ist erstmal, dass eben die Typ 3
Grammatiken gerade zu den endlichen Automaten gehören.
Und das sind gerade die regulären Sprachen.
Wir wissen aber, dass die regulären Sprachen sehr eingeschränkt sind,
dass zum Beispiel die Sprache der korrekten Klammerausdrücke nicht
regulär ist.
Wir hatten ja im Zusammenhang mit regulären Sprachen das Pumping
Lemma, um für nicht reguläre Sprachen, wenn es gut läuft, zu beweisen,
dass sie nicht regulär sind, und eben für die Sprache der korrekten
Klammerausdrücke kann man etwa mit dem Pumping Lemma beweisen, dass
sie nicht regulär ist.
Aber Programmiersprachen sollten schon so gebaut sein, dass
korrekte Klammerausdrücke sozusagen überprüft werden können, ob sie
korrekt sind.
Das heißt, Typ 3 Grammatiken sind viel zu eingeschränkt, als dass sie
als Grundlage für Programmiersprachen herhalten können.
Das heißt, wir haben jetzt sehr schnell abgeklärt, die interessanten
Grammatiken müssen zwischen Typ 0 und Typ 3 liegen, also Typ 1, Typ 2,
da müssen wir genauer hingucken.
Gut, dann gucken wir mal Typ 1 an, oder Chomsky 1, oder
Kontextsensitive Grammatiken.
Da müssen wir jetzt ein bisschen ausholen.
Wir schauen uns jetzt mal ein bisschen anders, als wir in dem Kapitel
Komplexitätstesten gemacht haben, bezüglich der Komplexität einer
Aufgabe nicht die Laufzeit an, die man benötigt, sondern den
Speicherplatz.
Und dazu nehmen wir an, dass unsere Turing-Maschine so ein Arbeitsband
hat.
Die Eingabe steht auf einem Band, das read-only ist, und wenn die
Turing -Maschine arbeitet, was schreibt oder so, macht sie das auf dem
Arbeitsband.
Und was an Speicherbedarf für eine Berechnung benötigt wird, liest man
an dem Arbeitsband ab, und zwar wie viele Zellen des Arbeitsbandes
werden maximal benötigt.
Und dann kann man wieder Komplexitätsklassen definieren, in
Abhängigkeit davon, was an Speicheraufwand notwendig ist, um eine
Sprache zu akzeptieren oder eine bestimmte Aufgabe zu lösen.
Und dann kann man auch wieder unterscheiden zwischen deterministischen
und nicht-deterministischen Turing-Maschinen.
Und folgende Klassen sind jetzt für uns interessant.
D-Tape S von N, erstmal für eine beliebige Funktion S von N, soll
sein, die Klasse der Sprachen L, für die es eine deterministische
Turing -Maschine gibt, die Platzbedarf S von N hat, bei Eingabelänge
N, welche L akzeptiert.
Und N-Tape S von N kann man genauso definieren als die Klasse der
Sprachen L, für die es eine nicht-deterministische Turing-Maschine mit
Platzbedarf S von N gibt, die L akzeptiert.
Und jetzt interessiert uns hier vor allem D-Tape und N-Tape für
Funktionen, die linear sind.
Erstmal ist natürlich offensichtlich, dass D-Tape S von N eine
Teilmenge von N-Tape S von N ist, für beliebige Funktionen S von N.
Weil unter die nicht-deterministischen Turing-Maschinen kann man
natürlich auch die deterministischen packen.
Dann kann man beweisen, dass N-Tape N dasselbe ist wie N-Tape F von N,
mit F ist eine lineare Funktion, also mit F in Theta von N.
Also ob hier N steht oder Konstante mal N macht keinen Unterschied.
Das ist so.
Das nehmen wir jetzt einfach mal so hin.
Und dann kann man beweisen, und das nehmen wir jetzt auch mal einfach
so hin, dass die Klasse der von Chomsky 1-Grammatiken erzeugten
Sprachen gerade die Klasse N-Tape N ist.
Jetzt haben wir vielleicht noch kein Gefühl dafür, was N-Tape N für
eine Klasse ist, was da alles an Sprachen reinfällt, wie komplex die
sein können, bezüglich dem, was wir typischerweise bei Komplexität
betrachten, nämlich Laufzeit.
Die Klasse der von Chomsky 1-Grammatiken erzeugten Sprachen stimmt mit
der Klasse der Sprachen überein, für die gilt, es gibt eine nicht
deterministische Turing-Maschine mit Platzbedarf N.
Die braucht so viel Platz auf dem Arbeitsband, wie die Länge der
Eingabe ist, aber nicht mehr.
Sieht bescheiden aus.
Auf dem Arbeitsband nur so viel Platz, wie die Länge der Eingabe, aber
das ist eine Riesenklasse.
Es ist nicht bekannt, ob N-Tape N gleich D-Tape N ist.
Bezüglich Speicherbedarf N, Eingabelänge, gleich Eingabelänge, dass es
einen Unterschied gibt zwischen deterministischer und nicht
deterministischer Berechnung.
Und wir schauen uns jetzt ein Problem an, was in D-Tape N ist.
Das Klickproblem.
Jetzt sind wir wieder plötzlich im letzten Kapitel.
Wir betrachten Graphen und klicken in Graphen.
Das ist ein vollständiger Teilgraph.
Das Klickproblem besteht darin, gegeben ein Graph und ein Parameter k
k kleiner gleich Anzahl der Knoten des Graphen, gibt es eine Clique
der Größe mindestens k.
Gibt es einen vollständigen Graphen in G der Größe mindestens k.
Dieses Problem gehört zu D-Tape N.
Wenn dem so ist, dann sind in D-Tape N auch entweder vollständige
Probleme, das heißt also Chomsky 1 Sprachen enthalten auch endlich
vollständige Sprachen.
Das Klickproblem gehört zu D-Tape N.
Das ist eigentlich trivial.
Wir müssen uns angucken, wie wir mit einer deterministischen
Turingmaschine das Klickproblem lösen können unter Benutzung nur von
einem Speicherbedarf auf dem Arbeitsband, der so groß ist wie die
Eingabe.
Hier nutzen wir eine klein bisschen andere Sichtweise auf Klicken,
also unser Graph enthalte Knoten 1 bis N, die sind durchnummeriert,
und der Parameter k ist irgendwo zwischen 1 und N.
Und wir benutzen jetzt Vektoren, 0,1 Vektoren der Länge N, um
Teilmengen von V zu beschreiben und insbesondere Klicken.
Also wir haben so einen N-Vektor c aus 0,1 hoch N, mit der Bedeutung,
dass für eine Menge c Teilmenge von V gilt, ci ist 1 genau dann, wenn
der Knoten i in der Knotenmenge c ist.
Und um jetzt zu testen, ob g eine Klicke der Größe k hat, kann man
einfach alle Vektoren klein c über 0,1 hoch N durchtesten, welche zu
irgendeiner Teilmenge c aus V gehören.
Und einfach nachgucken, erstens enthält diese Teilmenge überhaupt
mindestens k Knoten.
Das macht man, indem man einfach die Einsen in klein c zählt.
Und zweitens sind die entsprechenden Knotenpaare durch eine Kante
verbunden.
Das macht man einfach, indem man immer guckt, für ci und cj, mit ci
gleich cj gleich 1, auf dem Eingabeband ist ij eine Kante.
Also auf dem Arbeitsband braucht man da immer nur einen N-Vektor c.
Den überschreiben wir immer.
Wir nehmen den ersten, den zweiten und so weiter.
Einfach irgendwie lexikografisch geordnet.
That's all.
Vektoren c aus 0,1 hoch N werden nacheinander beginnend mit 0,0
durchgetestet.
Wenn ja rauskommt, dann wissen wir, unser Graph hat eine Clique der
Größe, Größe gleich K und ansonsten, wenn da bis zum Schluss immer
Nein rauskommt, dann eben nicht.
Gleicher Bedarf dabei ist linear, der ist insbesondere sogar nur so
groß wie die Anzahl der Knoten.
Das ist trivial.
Da war jetzt nichts besonders Schwieriges zu erfüllen.
Das ist also so, dass falls p und gleich np ist, das Wortproblem für
kontextsensitive Grammatiken im Allgemeinen nicht in Polynomialzeit
entschieden werden kann.
Das ist sozusagen das Fazit.
Wir haben also gezeigt, es gibt eine np-vollständige Sprache, die zu
der Klasse der Sprachen gehört, die durch kontextsensitive Grammatiken
erzeugt werden.
Das heißt also, bei kontextsensitiven Grammatiken-sprachen können sie
nicht davon ausgehen, im Allgemeinen, dass das Wortproblem in
Polynomialzeit gelöst wird.
Ok, also kontextsensitiv ist zu mächtig.
Vielleicht noch eine Bemerkung zu kontextsensitiven Grammatiken.
Die Einschränkungen an das Aussehen der Regeln, die waren ja nicht
sehr stark.
Auf der linken Seite sollte also nur ein Wort stehen, was aus
Variablen besteht und auf der rechten Seite ein beliebiges Wort, das
nicht kürzer ist als das Wort da links.
Was wir im Zusammenhang mit kontextsensitiven Grammatiken sagen
können, aber auch bei kontextfreien Grammatiken dann feststellen
werden, ist, dass man, ich sag mal, verlustfrei das Aussehen der
Regeln einschränken kann.
Bei kontextsensitiven Grammatiken in dem Sinne, dass man sagen kann,
zu jeder kontextsensitiven Grammatik, oder Chomsky 1 oder Typ 1
Grammatik, gibt es eine, bei der die Regeln nur diese Form haben.
Das hier ist deutlich eingeschränkter als das, was noch nach
Definition von kontextsensitiv denkbar wäre.
Weil hier haben Sie außer bei dieser Regeln sollte links sogar nur
eine Variable stehen, wie bei den kontextfreien.
Das also nur als Bemerkung beweisen wir hier nicht.
Man könnte jetzt auf die Idee kommen, na jetzt schränke ich irgendwie
die kontextsensitiven Grammatiken weiter ein und komme dann zu einer
Sprachklasse, die zwar noch nicht so eingeschränkt ist wie
kontextfreie Sprachen, die durch kontextfreie Grammatiken erzeugt
werden, aber vielleicht eingeschränkt genug, dass das Wortproblem
nicht zu komplex wird.
Aber schon wenn man so einschränkt, Aussehen der Regeln so
einschränkt, kommt man nicht sozusagen auf eine kleinere Klasse als
die Klasse der kontextsensitiven.
Das ist praktisch die Anzeige.
So, wir werden jetzt oft folgende Notation verwenden.
Anstatt einfach zu sagen, es gibt die Regel, S wird ersetzt durch
Alpha und es gibt die Regel, S wird ersetzt durch Beta.
Schreiben wir auf S kann ersetzt werden durch Alpha oder Beta, indem
wir einfach das oder durch so einen denkrichten Strich markieren.
So, und jetzt gucken wir uns kontextfreie Grammatiken genauer an.
Nach Definition sind das also Grammatiken, bei denen die
Ableitungsregeln ausschließlich die Form haben.
Links steht eine Variable, rechts ein Wort V, das beliebig sein kann.
Das kann auch das leere Wort sein, ein beliebig gemischtes Wort aus
Symbolen aus V vereinigt sind.
Und jetzt gucken wir uns einfach mal ein paar Beispiele an.
Wir hatten ja im Zusammenhang mit den regulären Sprachen diese
korrekten Klammerausdrücke angeguckt und noch eingeschränktere
Sprache, wie man so interpretieren kann, erstmal haben sie N-Klammern
auf und dann gefolgt von N-Klammern zu.
Das sind bestimmte korrekte Klammerausdrücke und wir haben
festgestellt, dass diese Sprachen alle schon nicht mehr regulär sind.
Also nicht nur die Sprache der korrekten Klammer Ausdrücke ist nicht
regulär, sondern auch diese Sprache.
0 hoch N, 1 hoch N.
Und jetzt schauen wir mal, ob man dafür eine Typ 2 Grammatik angeben
kann.
Also Sprache L gleich 0 hoch N, 1 hoch N, N größer gleich 1.
Ja, kann man.
Wir brauchen nur eine Variable, S plus S.
Dachtvariable S.
Sigma ist 0,1.
Und wir brauchen nur folgende Regeln, S kann ersetzt werden durch 0,1
und S kann ersetzt werden durch 0,S,1.
Klar, dass sie mit diesen Regeln
alle Wörter 0 hoch N, 1 hoch N produzieren können.
Okay, weiteres Beispiel die Sprache der Palindrome.
Das ist im Zusammenhang mit kontextfreien Grammatiken wichtig.
Was sind Palindrome?
Wir nehmen jetzt mal Palindrome über dem Alphabet 0,1.
Das sind Wörter aus 0,1 Stern, für die gilt das Wort von vorne gelesen
sieht genauso aus wie das Wort von hinten gelesen.
Also W aus 0,1 Stern, W gleich W oben R.
Und W oben R heißt einfach, dass ist W umgedreht.
Wie kann man Palindrome beschreiben?
0,1 und Y sind Palindrome.
Falls W ein Palindrome ist über 0,1, dann auch 0W0 und 1W1.
Und beliebige Palindrome lassen sich durch eine endliche Anwendung von
diesen beiden Regeln erzeugen.
Beliebige Palindrome angucken und kriegen sie dieses entsprechende
Wort immerhin, indem sie irgendwie hier starten mit etwas 0 oder 1
oder Y und dann diese Regeln zwei paar Mal anwenden.
Entsprechend können sie leicht eine zugehörige kontextfreie Grammatik
angeben.
Die Variablenmenge besteht nur aus den Startvariablen S unser Alphabet
ist 0,1, wir betrachten Palindrome über 0,1 und folgende Regeln
brauchen wir praktisch eins zu eins diese Beobachtung hier übersetzt
in Regeln S kann ersetzt werden durch Y oder durch 0 oder durch 1 und
S kann ersetzt werden durch 0S0 und S kann ersetzt werden durch 1S1.
Drittes Beispiel sei L die Sprache aller W aus 0,1 plus, also das
leere Wort ist nicht dabei, bei denen die Anzahl der Nullen gleich der
Anzahl der Einsen ist.
Sowohl bei den Palindromen als auch bei der Sprache ist klar, dass sie
nicht regulär sind.
Also...
L sei die Sprache aller Wörter über 0,1 für die gilt, Anzahl der
Nullen ist gleich Anzahl der Einsen.
Folgende Grammatik kann man dafür angeben.
Als Variablenmenge nehmen wir SAB
und folgende Regeln haben wir.
S kann ersetzt werden durch 0B und durch 1A und dann kann A ersetzt
werden durch 0 oder durch 0S oder durch 1AA und B ersetzt werden durch
1 oder durch 1S oder durch 0BB.
Wir wissen, wenn wir bei S angefangen haben und entweder 0B oder 1A
erzeugt haben, dann müssen wir in dem Fall, wenn wir 0B erzeugt haben,
diese 0, die wir erzeugt haben, irgendwann durch eine Eins
ausgleichen.
Das heißt also, Ersetzen von B muss bewirken, dass wir eine Eins
bekommen.
Und genauso, wenn S zu 1A abgeleitet wurde, dann muss Ersetzen durch A
dafür sorgen, dass wir eine 0 kriegen, um diese Eins auszugleichen.
Entsprechend haben wir also die Regel, A wird abgeleitet durch 0.
Diese erste Eins, durch die überhaupt A ins Spiel kam, auszugleichen
durch 0.
Aber möglicherweise wollen wir noch mehr machen.
Insofern könnten wir auch sagen, naja gut, ich leite A ab, oder
ersetze A durch 0S, dann habe ich die Eins ausgeglichen und kann mit
dem S wieder neu weitermachen.
Oder ich kann A ersetzen durch 1AA, das heißt also, ich habe noch eine
weitere Eins dazugebaut, dann muss ich aber zwei Einsen ausgleichen,
deshalb hier zwei As.
Und analog die Ableitungsregeln, bei denen links B steht.
Dann kann man leicht durch Induktion über die Länge der durch G
erzeugten Wörter zeigen, dass eben L von G gerade die Wörter, die
Sprache der Wörter ist über 0,1, für die gilt Anzahl der Nullen ist
gleich Anzahl der Einsen.
Und für dieses Jahr von mir, also Sie haben ja noch eine Übung, aber
zumindest nicht mehr für eine Vorlesung, dann wünsche ich Ihnen schöne
Weihnachten, gutes neues Jahr und wir sehen uns nächstes Jahr wieder.