So, schönen guten Tag.
Ich begrüße Sie zur Fortsetzung der Vorlesung Grundlagen der
Informatik II.
Hat ein bisschen länger gedauert, weil das Netz nicht so richtig
wollte, wie wir das eigentlich wollten.
Verbindungen waren nicht richtig da.
Manchmal gibt es solche Probleme.
Haben wir alles gelöst und jetzt können wir uns also beschäftigen mit
den Themen, die wir letztes Mal intensiv angeguckt haben schon.
Also wir hatten uns mit den kontextfreien, also mit den
Kellerautomaten und kontextfreien Grammatiken beschäftigt.
Sie erinnern sich an all diese Folien, die ich hier noch ganz kurz
durchrauschen lasse.
Da ging es einerseits darum, dass man einen Kellerautomaten für eine
vorgegebene Sprache formuliert.
Das hatten wir gemacht.
Wir hatten nicht deterministische Kellerautomaten uns angeschaut.
Da war es eben wichtig zu sehen, dass man einige Sprachen oder
zumindest diese eine Sprache hier, der Palindrome, nicht erkennen kann
mit einem deterministischen Kellerautomaten, aber mit einem nicht
deterministischen Kellerautomaten.
Das heißt, wir können tatsächlich die Sprache akzeptieren mit einem
nicht deterministischen Kellerautomaten.
Und das heißt, dass die Mächtigkeit der beiden Automatentypen
unterschiedlich ist.
Wir können nicht deterministisch mehr machen als deterministisch,
anders als bei den endlichen Automaten.
Wir hatten dann gesehen, dass wir ganz allgemein auch zeigen können,
dass wir bei den kontextfreien Grammatiken in der Lage sind, zu jeder
kontextfreien Grammatik, deren Ableitung wir über Ableitungsbäume
beschreiben können, in der Lage sind, das kommt hier gleich, das muss
ich, wo bin ich jetzt, da bin ich, genau, das waren die
Ableitungsbäume, und wir hatten Beispiele gesehen für Ableitungsbäume,
für Darstellung von Sprachen noch mal wiederholt.
Ich hatte Ihnen dieses Beispiel gegeben für ein, das sieht schon etwas
mehr aus wie ein Programm.
Wir haben die Struktur als Syntagsbaum uns angeschaut oder als
Ableitungsbaum.
Ich hatte Ihnen erzählt, dass man Rechtsableitungen und
Linksableitungen unterscheidet.
Und wir hatten dann gesehen, dass man auch arithmetische Ausdrücke
beschreiben kann und schließlich, dass man zu einer kontextfreien
Grammatik immer einen äquivalenten Kellerautomaten definieren kann,
der deterministisch ist dadurch, dass wir auf der rechten Seite eines
Nicht -Terminalzeichens bei den Regeln der Grammatik eventuell mehrere
hier, das war an der einen Stelle, für jede Regel A auf V aus der
Produktionsmenge, das war hier der wesentliche Punkt, müssen wir einen
Zustandsübergang machen, bei dem wir im Keller im Prinzip das Nicht
-Terminalsymbol ersetzen durch die rechte Seite und das eben für jede
mögliche rechte Seite, das heißt wir haben hier den Nicht
-Determinismus drin, der einfach erzeugt wird durch den im Prinzip
Nicht -Determinismus der Grammatik, bei der wir ja für eine linke
Seite mehrere rechte Seiten haben können.
Das war die sehr einfache Art, wie wir in der Lage waren, eine
Ableitung durch eine kontextfreie Grammatik auf einem Keller zu
simulieren, immer das oben stehende Nicht-Terminalsymbol ersetzen
durch eine mögliche rechte Seite und sobald ein Terminalsymbol dort
steht, einfach dieses Terminalsymbol auf dem Keller, was dort oben
drauf steht, vergleichen mit dem aktuellen Symbol auf dem Eingabeband,
wenn die übereinstimmen, dann sind wir auf der richtigen Spur, dann
können wir das entsprechend löschen und ansonsten ist es halt keine
erfolgreiche Ableitung beziehungsweise kein erfolgreiches Akzeptieren
gewesen.
Das waren die Möglichkeiten, wie man das aufeinander abbilden konnte
und wir hatten dann gesehen, dass wir auch noch eine Normalform
angeben können, wir konnten eine lambdafreie Grammatik angeben, mit
dem wir alle Regeln rausgeworfen haben, bei denen auf der rechten
Seite das leere Wort steht und wir hatten dann als nächstes gesehen,
dass wir eine Normalform angeben können, bei der wir auf der rechten
Seite nur zwei Nicht-Terminalzeichen haben oder ein Terminalzeichen,
das heißt eine zunächst mal sehr starke Einschränkung der
Möglichkeiten und wir hatten gesehen, dass wir in der Lage sind,
trotzdem beliebige Regeln zu erzeugen.
Wir hatten nämlich gesehen, dass wir, das war auf der nächsten Folie,
hier hatten wir gesehen, wir können im Prinzip, wo haben wir das denn
stehen gehabt, wir hatten hier gesagt, dass wir einfach zunächst mal
jedes, also wenn auf der rechten Seite ein Terminalzeichen steht, dass
wir das Terminalzeichen ersetzen durch ein neues Nicht
-Terminalzeichen, das nur auf dieses Terminalzeichen abgebildet wird
und dann hatten wir gesagt, wenn wir eine längere Regel haben, müssen
wir dafür sorgen, dass diese längere Regel in mehreren Schritten
abgeleitet werden kann.
Und das ist der Punkt, den wir auf dieser Seite dann dargestellt
haben.
Wenn wir eine beliebige Regel haben, A auf B1 bis BN, dann haben wir
die einfach dadurch simuliert, durch Regeln der Art, bei denen wir
jeweils rechts nur zwei Zeichen haben, dass wir einfach jeweils das
erste Nicht-Terminalzeichen, das noch zu erzeugen ist, hingeschrieben
haben.
Das erste Nicht-Terminalzeichen und dann ein praktisch Merkvariable
dafür, dass wir noch weitermachen müssen.
Und diese Merkvariable kommt halt nur in Zusammenhang mit der
Ableitung dieser einen Folge von Zeichen B1 bis BN vor, ansonsten
überhaupt nicht.
Und dann haben wir halt die Möglichkeit, genau die Regel, die in der
ursprünglichen Grammatik stand, A auf B1 bis BN zu ersetzen durch eine
Ableitungsfolge.
A wird abgeleitet auf B1 bis BN durch Regeln, die nur die Form haben,
dass rechts zwei Nicht-Terminalzeichen stehen.
Und wir hatten gesehen, damit sind wir tatsächlich in der Lage, genau
die gleichen Wörter zu erzeugen, keine weiteren.
Und das heißt, wir haben damit eine Chomsky-Normalform.
Wir hatten das am Beispiel gesehen unserer Grammatik für wohlgeformte
Klammerausdrücke und hatten dann auch kurz gesehen bei der Greibach
-Normalform, dass man eine weitere Normalform angeben kann, bei der
ähnlich wie bei den rechtslinearen Grammatiken als erstes Zeichen
immer ein Terminalzeichen steht und dann danach jetzt nicht nur ein
Nicht -Terminalzeichen, sondern eine mögliche Folge von Nicht
-Terminalzeichen, dieses V, das bei einer rechtslinearen Grammatik,
die Länge 1 hat, bei der Greibach-Normalform beliebig groß sein kann.
Und das also nur zu diesen beiden Normalformen, die sich so
eingebürgert haben.
Und dann kamen wir zu dem wesentlichen Punkt einer Strukturaussage,
die wir im Prinzip schon einmal gesehen hatten bei den rechtslinearen
Grammatiken bzw.
Sprachen, die von endlichen Automaten akzeptiert werden können.
Das war jetzt die Überlegung zur struktur-kontextfreien Sprachen, bei
der wir wieder uns einen Prozess überlegen, der beliebig lang ist und
bei dem wir wissen, wir können nur endlich viele Situationen
unterscheiden, können also darauf bauen, dass wir wieder irgendeine
Wiederholung da drin haben.
Und der Prozess, den wir hier anschauen, ist der einer Ableitung,
dargestellt durch einen Ableitungsbaum einer kontextfreien Grammatik.
Also ein Ableitungsbaum, bei dem wissen wir, wir haben nur endlich
viele Nicht-Terminalzeichen zur Verfügung.
Wenn der Ableitungsbaum groß genug ist, also die Ableitung lang genug,
dann heißt das, es gibt hier einen Pfad drin, der mehr Zeichen
enthält, als wir Nicht-Terminalzeichen zur Verfügung haben.
Und damit muss mindestens ein Zeichen doppelt vorkommen.
Wenn es doppelt vorkommt, muss wegen der Form der Grammatik, die wir
hier angenommen haben oder die wir einfach annehmen können, als eine
Grammatik, bei der Regeln der Art, also was für Regeln können
auftauchen.
Wir haben hier ja eine, also zunächst mal noch keine spezielle
Struktur vorgesehen, aber wir können davon ausgehen, dass so etwas in
der Art A auf B oder also eine einfache Ersetzung einer Variablen
sowas gar nicht vorkommt.
Insbesondere bei der Chomsky-Normalform sind rechts immer zwei Nicht
-Terminalzeichen und das heißt, wenn wir aus einem Zeichen A
irgendwann wieder auf ein A kommen, dann müssen links und rechts
daneben mindestens ein paar weitere Zeichen entstanden sein, also
mindestens ein weiteres Zeichen muss dort entstanden sein.
Und das heißt, dass wir im Prinzip eine Struktur haben, wie sie hier
angedeutet ist.
Wir haben ein gewisses Teilwort erzeugt auf dem Weg bis zu dem ersten
A.
Das entsprach hier dieser Darstellung, von S kommen wir über
irgendeine Ableitung auf das Teilwort V1 A V2.
Da ist das U, also das entspricht dann den Markierungen an den
Blättern dieses Teilbaumes, der aus V1 erzeugt werden kann.
Dann kommen wir irgendwann wieder zu einem A, und das heißt, wir haben
dann irgendetwas weiteres erzeugt, und zwar sowohl links als auch
rechts.
Rechts war das Y noch hier vorher entstanden auf dem Weg zum A.
Auf dem weiteren Weg zum A wird wieder irgendetwas erzeugt worden
sein, was dann irgendwann auch auf Terminalzeichen abgebildet wird.
Und nach diesem zweiten A wird auch irgendetwas weiteres erzeugt
werden.
Es ist ja ein Wort der Sprache insgesamt, dieses Wort Z gleich UVWXY.
Und wenn man eben diese Struktur einmal sich angeguckt hat, dann weiß
man sofort, dass man daraus dann halt auch eine beliebige Wiederholung
der Situation machen kann.
Wenn ich einmal zu dem A zurückkehren kann, dann kann ich den gleichen
Ableitungsprozess nochmal durchführen oder ihn auch ganz weglassen.
Und damit habe ich die Möglichkeiten zu zeigen, dass eben aus der
Aussage, dass das UVWXY, dieses Ausgangswort, dass das ein Element der
Sprache ist, dann muss auch jedes andere Wort, bei dem ich V und X
gleichzeitig hochzähle, auch zur Sprache gehören.
Weil ich einfach im Ableitungsbaum diese Teile beliebig einbauen kann.
Wie gesagt, ich hatte Ihnen versprochen, beim Pumping Lämmer für
endliche Automaten, Sie werden noch ein weiteres kennenlernen, bei dem
der Prozess, den wir anschauen, und die unterschiedlichen Situationen,
die wir anschauen, etwas komplizierter sind als bei dem Pumping Lämmer
für endliche Automaten.
Da waren das nur unterschiedliche Zustände, die wir angeschaut hatten.
Hier sind es jetzt unterschiedliche Nicht-Terminalzeichen auf einem
Pfad im Ableitungsbaum.
Und die kompliziertere Situation ergibt sich dadurch, dass wir uns
anschauen, was ist dann insgesamt für ein Wort entstanden über den
Terminalzeichen, wenn eben in der Ableitung sich ein solches Nicht
-Terminalzeichen wiederholt.
Und damit haben wir also diese Aussage, bei der wir wissen, wir können
an zwei Stellen Synchron-Teilwörter beliebig oft hinschreiben.
Das also zu dieser Darstellung dieses Pumping Lämmers.
Und damit ist der Rest eigentlich klar.
Das hatte ich letztes Mal Ihnen schon dargestellt.
Es gibt dann ein paar Fragen, die man stellen muss.
Wie lang muss das Wort sein?
Wie sieht das mit den anderen Teilen überall aus?
Wir machen diese Abschätzung mit dem Wort über die Chomsky-Normalform.
Wir nehmen an, dass wir zu der Sprache eine Grammatik in Chomsky
-Normalform haben.
Dann können wir eben die Abschätzung machen, sodass wir mindestens
eine Länge 2 hoch n brauchen für n verschiedenen Nicht
-Terminalzeichen, die in der Grammatik vorkommen.
Und damit, nach der Beantwortung dieser Fragen, die ich Ihnen letztes
Mal hier angegeben habe, wissen wir jetzt auch, wie groß dieses V und
X sein müssen.
Und das ergab dann das Pumping-Lämmer für kontextfreie Sprachen in der
Formulierung, wie es hier steht, oder auch in der Umkehrung.
Also für jede kontextfreie Sprache gibt es eine Länge, eine Schranke
K, sodass jedes Wort der Sprache, das mindestens diese Länge hat, eine
Zerlegung hat in Teilwörter U, V, W, X, Y, bei der diese Teilwörter V,
W, X eine Länge haben, maximal K, dass V und X zusammen nicht leer
sind.
Also links oder rechts wird mindestens ein Zeichen erzeugt.
Und wir können dann sagen, dass jedes Wort U, V hoch I, W, X hoch I, Y
auch in der Sprache ist.
Das haben wir gerade vorbereitet durch die Überlegung auf den letzten
Folien.
Und wie beim Pumping-Lämmer für endliche Automaten auch hier die
Umkehrung, die wir eigentlich dann verwenden, wenn wir zeigen wollen,
dass eine bestimmte Sprache nicht von einer kontextfreien Grammatik
erzeugt werden kann.
Genauso hatten wir bei den endlichen Automaten gesagt, wir verwenden
das Pumping-Lämmer, um zeigen zu können, dass eine bestimmte Sprache
nicht von einem endlichen Automaten akzeptiert werden kann.
Wir mussten das auf diesem Wege machen, weil eben das Pumping-Lämmer
keine Genau-dann-wenn-Beziehung ist, sondern es ist eine notwendige
Bedingung, also diese Bedingung mit der Existenz einer Pumpstelle oder
hier mit zwei Pumpstellen ist eine notwendige Bedingung, keine
hinreichende.
Das heißt, es kann durchaus Sprachen geben, die diese Eigenschaft
haben hier unten, aber nicht kontextfrei sind.
Für kontextfreie Sprachen muss das gelten.
Aber ich kann nur sagen, wenn diese Bedingung hier nicht gilt, und das
ist das, was hier unten steht, wenn es also für eine beliebige
Sprache, für jede mögliche Schranke ein Wort konstruiert werden kann,
das länger ist als diese Schranke, dann kann ich für jede mögliche
Zerlegung in irgendeiner Form mit diesen Eigenschaften vwx kleiner
gleich k und vx ungleich lambda eine solche Potenz von v und x
konstruieren, bei der das uv hoch iwx hoch iy nicht aus L ist.
Das ist wie gesagt wieder nur die einfache Umdrehung, Umkehrung,
Kontraposition des Pumping-Lämmers und für die praktische Nutzung ist
hier unten die Folgerung, die Formulierung, die wir verwenden, um zu
zeigen, dass bestimmte Sprachen halt nicht kontextfrei sind.
Und hier gibt es schon die erste Anwendung, das Beispiel dafür.
Wie gesagt, wir nehmen uns irgendeine Sprache her, jetzt in diesem
Fall die Sprache a hoch n, b hoch n, c hoch n.
Da hatte ich Ihnen schon so intuitiv begründet, warum die wohl nicht
von Kellerautomaten akzeptiert werden kann.
Ja, das war ja so, dass wir sagten, beim Kellerautomaten, da können
wir zählen, wie oft ein Zeichen aufgetaucht ist, weil wir zum Beispiel
eben sehen können, wie oft sind hier irgendwelche a's aufgetaucht.
Danach können wir, da haben wir eine gewisse Zahl von a's in den
Keller reingeschrieben, danach können wir die alle wieder
rausstreichen, weil wir in der Zwischenzeit genügend viele b's gesehen
haben, also bei dem Wort a hoch n, b hoch n, c hoch n, jeweils also
gleich viele a's, b's und c's.
Könnten wir überprüfen, ob genauso viele b's da sind, aber dann ist
die Information über die Anzahl der a's oder b's weg und wir können
eben nicht mehr überprüfen, ob die Anzahl der c's auch ausreicht.
Dafür bräuchten wir im Prinzip einen zweiten Keller, in den wir erst
die a's reinschreiben, dann würden wir hier die b's reinschreiben und
dann könnten wir überprüfen, ob auch gleich viele c's da sind.
Wenn wir bei das machen könnten, hätten wir zwei Keller und mit zwei
Kellern können Sie wesentlich mehr machen, als nur mit einem
Kellerautomaten, da könnten Sie beliebige Sprachen im Prinzip
erkennen.
Wir kommen gleich darauf, dass zwei Keller genauso mächtig sind wie
ein langes Band, auf dem man beliebige Dinge schreiben kann, nicht mal
mit den Einschränkungen, dass man nur das oberste Kellerzeichen
anschauen kann.
Mit zwei Kellern könnten Sie problemlos so arbeiten, dass Sie einfach
da hin und her bewegen die Inhalte und dann können Sie auf jede
Position in dem Kellerinhalt zugreifen.
Also das wäre das Gleiche, als wenn Sie ein langes Band haben, auf dem
Sie beliebig arbeiten können.
Das werden wir heute noch sehen, dann die Turing-Maschine werden.
Also noch ein weiteres Modell für die Sprachen, die oben drüber sind.
Jetzt aber zurück zu dem, was wir hier tatsächlich können.
Wir können also überprüfen, ob genauso viele a's wie b's da sind, aber
eben nicht, ob so viele c's da sind.
Und jetzt können wir aufgrund dieser Strukturaussage zeigen, es gibt
keine kontextfreie Grammatik, mit der wir genau diese Sprache erkennen
können.
Und das liegt eben daran, dass wir uns einfach jetzt für irgendein
beliebiges k, für jedes beliebige k, müssen wir ein Wort angeben
können, das mindestens so lang ist wie k.
Nehmen wir einfach das Wort a hoch k, b hoch k, c hoch k, das ist
sogar dreimal so lang wie k.
Also offensichtlich länger als k.
Jetzt müssen wir zeigen, egal welche Aufteilung mit diesen
Eigenschaften, die hier stehen, wir nehmen, egal welche Aufteilung,
wir finden eine Potenz, also dass wir v und x hochzählen, sodass das
u, v hoch i, w, x hoch i, y nicht aus l ist.
Also wir haben uns ein Wort aus der Sprache genommen.
Es ist natürlich wichtig, dass ein Wort der Sprache l ist.
Und jetzt müssen wir schauen, wir wählen eine beliebige Zerlegung.
Jetzt haben wir hier unser schönes Wort, a hoch n, b hoch n, c hoch n.
So, hier stehen nur a's, da stehen nur b's, natürlich nicht hoch n,
sondern das sind jeweils k a's, b's und c's.
Und jetzt wählen wir eine beliebige Zerlegung mit den Eigenschaften,
die hier oben stehen.
Also v, w, x hat eine Länge kleiner gleich k und v und x enthalten
mindestens ein Element.
So, wenn das kleiner gleich k ist in der Länge, dann heißt das doch,
wo kann dieses v, w, x auftauchen?
Das kann sein, dass das hier in diesem Bereich liegt.
Es könnte genau in dem Bereich liegen, könnte genau in dem Bereich
liegen, dann würde v, w, x nur aus a's bestehen oder nur aus b's
bestehen oder nur aus c's bestehen.
Es kann aber auch sein, dass dieses v, w, x sich über die Grenze
erstreckt zwischen b's und c's oder sich über die Grenze erstreckt
zwischen a's und b's.
Es kann also durchaus sein, dass dieses v, w, x ein irgendwie a hoch
r, b hoch s ist oder ein b hoch r, c hoch s oder irgend so was.
Es kann also zwei Buchstaben enthalten.
Aber was wir ausschließen können, ist, dass in dem v, w, x alle drei
Zeichen a, b und c drin sind.
Denn das würde nur gehen, wenn dieses Wort v, w, x sich ja vollständig
hier rüber erstrecken würde, wenn das also Teile in a enthalten würde
aus b und auch noch ein c, dann müsste es ja länger als k sein.
Es ist aber maximal so lang wie k.
Das heißt, es können dort a's und b's drin sein, es können b's und c's
drin sein oder auch nur a's oder nur b's oder nur c's, aber eben nicht
mehr als zwei verschiedene Buchstaben.
Das ist also die wesentliche Eigenschaft, die wir hier jetzt erkannt
haben.
Und damit sind wir eigentlich fertig.
Denn wenn dieses v, w, x maximal zwei verschiedene Buchstaben enthält,
dann wissen wir doch, weil das v, x eine nicht leere Länge hat, das
heißt, in dem v, x, also v, w, x hat eine Länge kleiner gleich k, es
könnte also sein, dass bei dem v oder bei dem x ein a und ein b drin
ist, kann auch sein, dass es nur a's sind oder nur b's, aber es können
eben nicht a, b und c drin sein.
Das heißt, wenn wir jetzt das v und x rausstreichen oder erhöhen oder
irgendeine andere Potenz nehmen, dann haben wir die Anzahl der a's und
b's verändert.
Für jedes i und gleich eins ist also für mindestens ein Buchstaben
oder für maximal zwei Buchstaben in diesem a hoch k, b hoch k, c hoch
k die Anzahl des Auftauchens verändert und damit stimmt es nicht mehr
überein, wir haben nicht die gleiche Anzahl und damit liegt es nicht
in der Sprache L.
Das heißt, diese Potenz von u, v, i, w, x, y kann nicht in L liegen.
Egal, welche Schranke k wir betrachten, egal, welche Zerlegung wir
betrachten, wir finden auf jeden Fall ein i, eine Potenz, sogar sehr
viele, für die das Wort u, v, i, w, x, y nicht in der Sprache ist und
damit wissen wir, dann kann diese Sprache keine kontextfreie Sprache
sein.
Das ist genau diese Aussage.
Dann ist L nicht kontextfrei.
Und damit ist also a hoch n, b hoch n, c hoch n nicht kontextfrei.
Wir wissen also, dass was wir wollten, dass wir jetzt diese Sprache,
jetzt geht das schon einen Schritt weiter, dass also die Menge der
kontextfreien Sprachen echt kleiner ist als die Menge aller Sprachen.
Wir haben eine Sprache gefunden, die oben drüber liegt.
Gut, jetzt kommen wir zum nächsten Punkt.
Also wie gesagt, das mit dem Pumping Lemma, das ist eine ganz
wesentliche Erkenntnis, hatte ich Ihnen schon bei den endlichen
Automaten gesagt.
Diese Überlegungen, einen langen Prozess betrachten, bei dem ich nur
endlich viele Situationen unterscheiden kann, erlaubt mir,
Strukturaussagen zu machen über diesen langen Prozess, weil da einfach
Wiederholungen dran sind.
Und das reicht vor allen Dingen, ein Anfangsstück zu betrachten, bis
zu dieser Länge k, die dort halt vorkommt.
Allein dadurch haben wir Informationen über das, was in den weiteren
Prozessen überhaupt noch passieren kann.
Das sind also die wesentlichen Konsequenzen, dass wir auf diese Art
und Weise Eigenschaften ableiten können.
Jetzt kommen wir zu einem weiteren Verfahren, das ich Ihnen noch kurz
vorstellen möchte, das ein Problem bearbeitet, an dem wir natürlich
immer interessiert sind.
Wir wollen wissen, ob ein Wort von einer kontextfreien Grammatik
erzeugt werden kann.
Wir nehmen mal an, die ist in Chomsky-Normalform.
Also wir wollen im Prinzip für jede kontextfreie Grammatik entscheiden
können, ob ein Wort von der Grammatik erzeugt wird oder nicht.
Wir wissen, wir könnten das mit den Kellerautomaten machen.
Im Prinzip wollen wir einen Kellerautomaten konstruieren.
Ich mache das aber jetzt hier ein bisschen anders und gebe Ihnen einen
anderen Ansatz, wie wir das machen können.
Das ist ein Algorithmus von drei Wissenschaftlern, Kocke, Janga und
Kazami, die einfach sich angeguckt haben, wie man durch Ausnutzung
dieser Struktur der Chomsky-Normalform-Regeln und der Struktur der
Ableitungsbäume entscheiden kann, ob ein Wort zur Sprache gehört oder
nicht.
Und die Idee ist, wenn ich irgendein Wort habe meiner Sprache,
dann komme ich da irgendwie hin aus, im Prinzip irgendwann mal habe
ich das hier abgeleitet, komme da irgendwann auf dieses Wort, leite
das ab durch eine Folge von Ableitungen aus dem S, aus meinem
Startsymbol.
Dann habe ich das ganze Wort W hier erzeugt.
Jetzt kann es natürlich sein, das ist ja klar, wir hatten ja auch
unsere Ableitungsbäume.
Ich male jetzt mal das doch ein bisschen anders.
Unser Ableitungsbaum, ich male es Ihnen ganz anders auf.
Ich muss das nochmal neu machen.
Hier unten male ich immer dieses Wort hin.
Und hier oben ist unser Startsymbol.
Und wir wissen, wir kommen da irgendwie über eine Folge von
Ableitungen oder eine Folge von Schritten, das sind alles irgendwelche
Symbole, nicht Terminalsymbole, und hier gehen wir irgendwie weiter,
da gehen wir irgendwie weiter.
Und wir haben dann hier irgendein Teilwort, das aus einem Nicht
-Terminalzeichen A abgeleitet wird.
Vereinfachte Situation hatten wir gerade betrachtet bei dem Pumping
Lemma.
Das heißt, ich kann mir umgekehrt anschauen.
Ich betrachte mir hier irgendein Teilstück.
Ich sage mal einfach hier, das ist mein Wort W.
Dann habe ich hier mein Wegen X, Y und Z.
Und jetzt gucke ich mir so ein Teilstück Y an und frage mich, welche
Nicht -Terminalzeichen können eigentlich dieses Teilstück Y erzeugen?
Es mag ja sein, dass das mehrere sind.
Es muss mindestens ein Nicht-Terminalzeichen geben, das dieses
Teilstück erzeugen kann.
Und wenn ich mir dieses W genauer angucke, dann weiß ich natürlich,
ich schreibe mir das jetzt nochmal oben drüber, als E1 und so weiter
bis EN, so wie das da oben auch steht, dann weiß ich natürlich zum
Beispiel, jedes einzelne EI, also so ein E1, das wird natürlich aus
einem Zeichen, ich schreibe mal jetzt groß E1, erzeugt.
Chomsky-Normalform.
Alle Regeln sind von der Form entweder A auf BC oder A auf kleines A,
also A auf zwei Nicht-Terminalzeichen oder A auf irgendein
Terminalzeichen.
Also jedes Zeichen, das hier am Ende steht, das wird erzeugt durch, da
steht dann irgendein, ich nenne das mal einfach EN, das Nicht
-Terminalzeichen.
Und wenn hier ein E1 steht, dann muss das natürlich, und hierneben
steht ein E2, um das Zeichen E2 zu erzeugen, da müssen natürlich E1
und E2 erzeugt worden sein aus irgendeinem, nenne ich mal jetzt B, aus
irgendeinem Nicht-Terminalzeichen, das gerade diese E1, E2
nebeneinander geschrieben hat.
Nur solche Regeln habe ich zur Verfügung.
Und schon weiß ich, aus dem B kann ich E1, E2 ableiten.
Und so schaue ich mir für jedes Teilstück eines Wortes an, für jedes
Teilstück E, I bis I plus J minus 1, das heißt, ich gucke mir hier an,
ein Teilstück der Länge J und beginne bei I, E, I bis E, I plus J
minus 1, ein Teilstück der Länge J, schaue ich mir an, welche Nicht
-Terminalzeichen habe ich eigentlich zur Verfügung, um dieses
Teilstück meines Wortes abzuleiten.
Und die Vorgehensweise können Sie sich jetzt schon vorstellen.
Wir fangen mit den einfachen Aussagen an.
Die einfachen Aussagen sind, naja, ich weiß ja, dass ich hier ein E, I
habe und das E, I abzuleiten und so weiter und so weiter.
Ich fange bei den kleinen an.
Aus Einzelvariablen kann ich Einzelkonstanten oder Einzel
-Terminalzeichen erzeugen.
Ich gucke mir also an, aus welchen Variablen kann ich Wörter der Länge
1 ableiten, die hier auftauchen.
Und dann schaue ich mir an, aus welchen Nicht-Terminalzeichen kann ich
irgendein Wort der Länge 2 ableiten.
Naja, ein Wort der Länge 2 muss über zwei Nicht-Terminalzeichen
erzeugt worden sein, aus irgendeiner Variablen.
Da mag es verschiedene Möglichkeiten für geben und dann sind
entsprechend die Variablen draus entstanden, aus denen ich das
Terminalzeichen ableiten konnte.
Das heißt, ich kann mich dann beschränken, darauf zu schauen, aus
welchen Nicht-Terminalzeichen kann ich Kombinationen der Länge 2 auf
dieser Ebene erzeugen.
Das sind alle Wörter der Länge 2.
Und dann schaue ich mir an, wie sieht das denn aus mit den Wörtern der
Länge 3?
Welche Möglichkeiten gibt es, ein Wort der Länge 3 zu erzeugen?
Naja, da muss ich am Ende drei Variablen erzeugt haben und das kann
ich über verschiedene Regeln der Grammatik vermutlich tun, bei denen
ich jeweils zwei Zeichen rechts stehen habe.
Und ich kann dafür die Informationen ausnutzen.
Wenn ich ein Wort der Länge 3 ableiten möchte, muss ich natürlich ein
Wort der Länge 2 ableiten können, über diese Regeln A auf B, C.
Und dann muss ich noch eine weitere rechte Seite erzeugt haben, also
einer von diesen Variablen noch eine weitere Variable.
Und das kann sein, dass ich erst das linke Stück und dann das rechte
Paar oder erst das linke Paar und dann die rechte Variable daneben
noch erzeuge.
Gibt schon verschiedene Möglichkeiten vermutlich.
Wenn ich das gemacht habe, für alle Möglichkeiten, Wörter der Länge 3
zu erzeugen, mache ich das für alle Wörter der Länge 4.
Und das war ein Ansatz, den haben wir schon mal kennengelernt, als wir
uns angeschaut haben, die Möglichkeiten, wie man für endliche
Automaten feststellen kann, ob zwei Zustände äquivalent sind oder
nicht.
Da hatten wir uns überlegt, wir machen das ganz einfach.
Wir überlegen erst mal, welche sind eigentlich nicht nulläquivalent.
Das war ganz einfach.
Da mussten wir nur Wege der Länge 0 betrachten im Automaten.
Dann hatten wir Wege der Länge 1 betrachtet und festgestellt, welche
sind nicht einzäquivalent.
Dann hatten wir im weiteren Schritt festgestellt, wenn ich mir jetzt
anschaue, wie ich mit einem Schritt auf Paare kommen kann, die nicht
iäquivalent sind, dann weiß ich, die sind auch nicht i plus 1
äquivalent.
Und genauso gehen wir jetzt hier vor, praktisch schrittweise nach oben
in diesem Baum, dass wir uns im Prinzip für jede Länge des Baumes
anschauen oder für jede Länge der Teilwörter anschauen wollen, welche
Möglichkeiten habe ich, irgendein Wort der Länge J abzuleiten.
Und das geht nur, wenn ich ein Wort der Länge J habe.
Das muss irgendwie aufgeteilt worden sein in zwei Hälften.
Und diese zwei Hälften, da gibt es verschiedene Möglichkeiten, wie ich
das aufteilen kann.
Das sehe ich dann im Prinzip aus meiner Struktur, die ich schon vorher
abgeleitet habe.
Und ich kann die Erkenntnisse aus den vorherigen Schritten alle
nutzen.
Das ist wieder der Ansatz der dynamischen Programmierung.
Also im Prinzip ist der Algorithmus von Koki-Yanga-Kazami ein
Algorithmus, der das Prinzip des dynamischen Programmierens wieder
ausnutzt.
Also Erkenntnisse für kleine Probleme geeignet kombinieren, um
Antworten für größere Probleme zu finden.
Das ist das dynamische Programmieren.
Und hier ist das formal aufgeschrieben.
Wir sind in der Lage, ein Wort EI bis EI plus J minus 1, also der
Länge J, aus einem Nicht-Terminalzeichen A abzuleiten, genau dann,
wenn wir eine Regel finden können, bei der wir aus A Nicht-Terminale B
und C ableiten und B erzeugt gerade den ersten Teil, also ein Teilwort
der Länge K.
Wir sind interessiert an dem Teilwort der Länge J, EI bis EI plus J
minus 1.
Und da müssen wir halt irgendein Teilwort der Länge K erst mal
erzeugen und hier ein Teilwort der Länge J minus K.
Und dieses wird aus B erzeugt, das aus C.
Und aus A können wir B und C ableiten, dann sind wir fertig.
Und wir wissen halt, das B ist bereits in VIK, das C ist in VI plus K,
J minus K, das ist genau ein Teilwort der Länge J minus K, ab der
Position I plus K.
Und damit ist dieses Teilwort EI bis EI plus J minus 1 aus A
ableitbar.
Also das ist dieses Ausnutzen von Eigenschaften, die man bereits für
kleinere Probleme abgeleitet hat.
Daraus schließe ich dann die Eigenschaft für die nächste Größe.
Und wenn ich jetzt wissen will, ob das Wort in der Sprache ist, muss
ich nur schauen, ob das gesamte Wort hier aus S ableitbar ist.
Das heißt, ich mache eigentlich viel mehr.
Eigentlich will ich ja nur feststellen, ist das Wort aus S ableitbar.
Hier mache ich viel mehr.
Hier überlege ich mir, was sind die variablen Mengen, aus denen ich
irgendwelche Teilwörter ableiten kann.
Sie werden sehen, dass wir dadurch zu einem Verfahren kommen, das eine
gewisse Komplexität hat, nämlich N hoch 3, also Länge des Wortes hoch
3, aber damit wissen wir, mehr Zeit als die Zeit müssen wir nicht
investieren.
In Zeit N hoch 3 können wir für jede kontextfreie Sprache das
Wortproblem lösen.
Das wird das Ergebnis sein, das Algorithmus, den ich Ihnen jetzt
genauer vorstelle.
Das war so ein bisschen Vorbemerkung, um Ihnen zu sagen, wie die Idee
hinter dem Verfahren ist, und das führen wir jetzt genauer aus.
Also Prinzip der dynamischen Programmierung, und hier ist der
Algorithmus, der genau das macht, was ich Ihnen gerade eben
vorgestellt habe.
Wir wollen also eine Grammatik uns hernehmen in Chomsky-Normalform.
Ein Wort, E1 bis En, aus nicht T natürlich, sondern T-Stern, dafür
Stern.
Und der Output soll sein, war, falls das W von G ist, falsch,
andernfalls.
Und da setzen wir einfach zunächst mal alle diese möglichen
Variablenmengen vij auf leer.
Und anschließend fangen wir mit der ersten Schicht an.
Also vi1 wird zunächst mal gesetzt für jedes Zeichen aus dem Wort,
schreibe ich im Prinzip hier mir entsprechend, ich nenne das jetzt mal
hier E1 bis En, die suche ich mir die Nicht-Terminalzeichen raus, aus
denen ich e1 bis, also e1 bis en erzeugen kann.
Es kann sein, dass diese Mengen schon mehr als ein Zeichen enthalten.
Sie werden auf jeden Fall mindestens ein Zeichen enthalten, ansonsten
könnte ja ein solches Terminalzeichen nicht enthalten sein in dem
Wort, das ich hier habe.
Wenn ich also hier feststelle, ich kann ein Zeichen ei nicht aus
irgendeinem Nicht-Terminalzeichen erzeugen, dann bin ich schon fertig,
dann kann ich das Wort auch nicht abgeleitet haben aus dem
Startsymbol.
Also das ist zunächst mal die Menge der Nicht-Terminale, aus denen ich
das Zeichen ei ableiten kann.
Und dann habe ich also den Anfang für Wörter der Länge 1 schon mal
alles erledigt und jetzt kommen die Wörter der Länge 2 dran,
beziehungsweise am Ende bis zu den Wörtern der Länge n.
Und dann muss ich halt sehen, dass ich für jedes solche Wort, also das
ist mein gesamtes Wort, e1 bis en, und nun muss ich für jedes solche
Wort der Länge j überprüfen, welche Nicht-Terminalzeichen erlauben
mir, dieses Teilwort abzuleiten.
Deswegen vor i gleich 1 zur n minus j plus 1, das ist jeweils hier die
Anfangsposition i und dann gehe ich halt bis i plus j minus 1 und habe
dann genau dieses hier wieder ei bis ei plus j minus 1, muss also
sehen, wie sieht die Menge vij aus.
Und die Menge der vij ist genau das, was wir auf der vorigen Folie
schon formuliert hatten, da werden alle Nicht-Terminalzeichen drin
sein, für die es eine Regel gibt, a wird auf bc abgeleitet und es ist
b aus einem vik und c aus vik j minus k.
Also es gibt, ich muss dazu noch schreiben, dass es eben auch ein k
gibt, sodass das b aus vik ist und c aus vi plus k j minus k.
Hier steht, ach richtig, muss ich nicht hinschreiben, sondern hier
wird einfach für jedes k das überprüft.
Also für jedes k, also für jede Position hier zwischen, das könnte ja
an irgendeiner Stelle sein, irgendwo kann so ein k sein, für jedes k
überprüfe ich, ob es solche Regeln gibt, a auf bc, sodass das b aus
vik ist und c aus vi plus k j minus k.
Also ich überprüfe alle möglichen Teilwörter, muss da sukzessive
durchgehen, nur das erste Zeichen abspalten, das erste und zweite,
erste, zweite, dritte und den Rest und so weiter.
Also immer irgendeine Aufteilung der Länge k und j minus k.
Wenn ich die beiden, also jede mögliche Aufteilung, wenn es solche
Regeln gibt, bei denen bereits Variablen b und c auftauchen, die ich
ableiten kann aus a, dann bin ich fertig.
Und das ist hier formuliert als Algorithmus, den ich so ausführen
kann.
Jetzt machen wir das Ganze dann gleich auch noch visuell und schauen
uns an, was für eine Tabelle wir eigentlich aufbauen.
Dann ist natürlich klar, wenn wir sagen, wir bilden solche Mengen vij,
dann bauen wir im Prinzip eine Tabelle auf, bei der wir hier jeweils
alle unsere v11 bis v1n hinschreiben.
Entschuldigung, vn1.
Und dann am Ende haben wir hier irgendein vn1.
Und das vn1, das wird also hier unsere Tabelle werden.
Da stehen die ganzen vij drin.
Und diese Tabelle hat am Ende ganz unten einen Eintrag vn1.
Und wenn da... Entschuldigung, nicht vn1.
Ich wollte v1n hinschreiben.
Von 1 anfangend ein Wort der Länge n.
Hier oben stand vn1, weil wir hier für das Zeichen en ein Teil der
Länge 1 betrachten.
Hier unten steht, wird v1n stehen.
Die nächste Zeile ist v12.
Das heißt, wir gehen hier sukzessive in der Länge der Teilwörter hoch
und haben also hier 1, 2, 3 bis irgendwann Länge der Teilwörter n.
Das heißt, wir haben die Menge v1n zu betrachten.
Und wenn da das Element s drin ist, dann sind wir fertig.
Das heißt, wir geben zurück als Ergebnis dieses Algorithmus die
Abfrage oder das Ergebnis dieser Abfrage, ist das s aus v1n.
Wenn das s aus v1n ist, dann ist dieser Ausdruck wahr.
Ansonsten, wenn s nicht aus v1n ist, ist dieser Ausdruck falsch.
Das heißt, wir bekommen entweder wahr oder falsch als Ergebnis.
Das heißt, das, was hier am Ende rausgegeben wird, ist eine Abfrage,
ist das s aus v1n.
Und dann ist das Wort ein Element der Sprache.
Und das machen wir jetzt an diesem Beispiel hier mit dieser Tabelle
für eine natürlich wie immer sehr einfache Grammatik.
Ansonsten könnte ich das hier nicht auf der Folie so Ihnen darstellen.
Also, einfache Grammatik, einfaches Wort.
Eine Grammatik sehen Sie hier.
Wir haben relativ wenige Zeichen, s, a, b, c.
Wir haben zwei Terminalzeichen, a und b.
Und unser Startsymbol s.
Und die Regeln sind hier angegeben.
Und jetzt nehmen wir uns einfach irgendein Wort her, zufällig
ausgewählt.
Gerade dieses Wort b, a, a, b, a.
Und wir wollen feststellen, ist dieses Wort ein Wort der Sprache, die
wir mit der Grammatik erzeugen können.
Sie können kurz überprüfen, dass diese Grammatik tatsächlich Chomsky
-Normalform ist.
Rechts stehen jeweils entweder zwei Nicht-Terminalzeichen oder ein
Terminalzeichen.
Sie sehen, dass das a zum Beispiel hier sowohl aus a als auch durch c
erzeugt werden kann.
Wenn wir also...
Und hier wollte ich eigentlich überall j stehen haben.
Da habe ich irgendetwas...
Ja, ich weiß schon, woran das liegt.
Da habe ich nur teilweise etwas verändert gegenüber einer Version, die
wir in früheren Jahren verwendet haben.
Da müsste eigentlich j stehen, analog zu dem, was wir auf der vorigen
Folie hatten.
Da hatten wir die Längen der Wörter mit der Variablen j
gekennzeichnet.
Darauf bezieht sich das hier.
Wir betrachten also jetzt erst mal Wörter der Länge 1.
Wie kann ich das Zeichen b erzeugen?
Na ja, schauen wir in die Regeln.
Dann kann ich das nur erzeugen aus dem Zeichen b.
Jetzt müsste ich ja eigentlich eine Mengenklammer hinschreiben, das
spare ich mir.
Das Zeichen a kann ich sowohl aus a als auch aus c erzeugen.
Das heißt, hier schreibe ich rein a und c.
Dann schaue ich mir an, wieder das Zeichen a.
Na, da steht natürlich auch a und c drin.
Da steht natürlich das große b drin.
Da steht wieder a und c drin.
Und ich bin damit schon mal fertig.
Alle Wörter der Länge 1 weiß ich jetzt, wie ich die erzeugen kann.
Jetzt kommen die Wörter der Länge 2 dran.
Also das ist hier, wie Sie sehen, habe ich hier auch schön alles in
Schönschrift aufgemalt.
Dann kann ich mir das hier so wieder wegwischen.
Jetzt schauen wir uns an, Wörter der Länge 2.
Wie machen wir das denn, Wörter der Länge 2?
Wir wollen also sehen, können wir zum Beispiel dieses Wort hier
erzeugen und das müssen wir hinschreiben in dieses Feld.
Wie können wir das Wort der Länge 2 erzeugen?
Ja nur dadurch, dass es eine Regel geben muss, aus der wir für jede
beliebige Aufteilung dieses Wortes in zwei Hälften in der Lage sind,
zwei Nicht-Terminalzeichen zu erzeugen, die jeweils diese Wörter der
Länge 1 erzeugen.
Da gibt es nur eine mögliche Aufteilung.
Wir müssen sehen, gibt es eine Möglichkeit B-A oder B-C zu erzeugen.
Und Sie sehen, wir können B-A erzeugen aus A.
Wir können B-C erzeugen aus S.
Ja, das reicht schon.
Mehr haben wir hier nicht, das sind die einzigen Möglichkeiten.
Weitere Alternativen gibt es nicht.
Das heißt, dieses Feld haben wir auch ausgefüllt.
Jetzt schauen wir uns das nächste Feld an, dieses Feld hier.
Da geht es um jetzt das nächste Teilwort der Länge 2, das ist dieses
Teilwort.
Da müssen wir uns anschauen, gibt es eine Möglichkeit A-A zu erzeugen
oder A-C oder C-A oder C-C.
Wir stellen fest, es gibt eine Möglichkeit, ich kann aus B C-C
erzeugen.
Es gibt also eine Regel B auf C-C und das C ist aus entsprechend den
jeweiligen Teilmengen, mit denen ich diese Teilwörter hierbei erzeugen
kann.
Und so geht es weiter und dann habe ich hier entsprechend die anderen
Möglichkeiten mit drin, die ich hier schon angedeutet habe.
Und jetzt kommen wir zu den Wörtern der Länge 3.
Das heißt, jetzt müssen wir uns anschauen, und das machen wir für
dieses erste Feld,
aus welchen Nicht-Terminalzeichen kann ich ein paar von Nicht
-Terminalzeichen erzeugen, sodass ich irgendeine Aufteilung dieses
Wortes der Länge 3 erzeugen kann.
Irgendeine Aufteilung, schauen wir uns mal die Länge 1 plus 2 an.
K gleich 1.
Jetzt weiß ich, das Teilwort der Länge 1, da steht hier etwas drin.
Für das Teilwort der Länge 2, das dann nachkommt, steht hier etwas
drin.
Das heißt, ich muss mir anschauen, kann ich aus einem Nicht
-Terminalzeichen die Folge BB erzeugen.
BB taucht hier rechts nicht auf.
Das heißt, hier muss die leere Menge stehen.
Ich kann das Teilwort BAA nicht erzeugen, dadurch, dass ich zunächst
mal das linke Zeichen B ableite und dann durch eine andere Variable AA
ableite.
Das funktioniert nicht.
Wir sind aber noch nicht fertig.
Das war nur diese eine Möglichkeit.
Das war die erste Möglichkeit, die ich überprüfen muss.
Die zweite Möglichkeit, die ich überprüfen muss, ist, dass ich mir
dieses Feld anschaue und das mit diesem Feld vergleiche.
Weil ich nämlich aus diesem Feld AS, also das Leere lasse ich nochmal
weg, wir haben zumindest noch keine Variable gefunden, das AS, aus dem
kann ich das BA erzeugen.
Nun ist die Frage, gibt es ein Nicht-Terminalzeichen, das A oder S als
erstes Zeichen ableitet und dann das A oder C, sodass ich das Zeichen
A noch dazufügen kann.
Ich musste also zuerst die beiden Felder, die mit 1 gekennzeichnet
sind, anschauen und dann die beiden Felder, die mit 2 gekennzeichnet
sind.
So, also AA geht nicht, AC taucht das auf, auch nicht.
SA gibt es auch nicht, SC gibt es auch nicht.
Also habe ich irgendwas übersehen?
Habe ich glaube ich nicht.
Wir müssen tatsächlich die leere Menge reinschreiben.
Kommen wir zum nächsten Feld, hier.
Jetzt mache ich mal hier diese Nummerierung wieder weg.
Was müssen wir anschauen, wenn wir dieses Feld hier ausfüllen wollen?
Dann schauen wir uns genauso zunächst mal die beiden Felder an, wobei
wir diese drei Zeichen angucken, danach müssen wir die beiden Felder
anschauen.
Also können wir AS erzeugen irgendwo?
Geht nicht.
Können wir AC erzeugen?
Auch nicht.
Können wir CS erzeugen?
Auch nicht.
Können wir CC erzeugen?
Ja.
CC lässt sich mit B erzeugen.
Schauen wir uns jetzt die andere Kombination 2,2 an.
Können wir BB erzeugen?
BB geht gar nicht.
Also es bleibt bei dem B, es kommt nicht mehr dazu.
Entsprechend für das nächste Feld, das taucht dann nochmal das B auf.
Jetzt kommt das hier wieder alles weg und wir machen weiter, die
nächsten Felder ausfüllen.
Nächsten Felder ausfüllen, das heißt jetzt Teilwörter der Länge 4.
Um Teilwörter der Länge 4 anzugucken, das ist also dieses Teilwort
hier, die erste Möglichkeit, gibt es drei Möglichkeiten, das
aufzuteilen.
Ja, wir können hier abschneiden, dort abschneiden oder dort
abschneiden.
Das erste Abschneiden heißt, wir müssen uns anschauen, dieses Feld und
dieses Feld.
Weil das Feld da oben für das B zuständig ist, dieses Feld hier unten
ist zuständig für die restlichen drei Zeichen.
Schauen wir uns die beiden an, BB können wir nicht ableiten, passiert
also nichts.
Dann müssen wir ein Teilwort der Länge 2 betrachten als Anfangsstück
und dazu gehört entsprechend dieses Feld.
Müssen wir mit dem vergleichen, können wir AS erzeugen?
Nein.
Können wir AC erzeugen?
Nein.
Können wir SS erzeugen?
Nein.
Können wir SC erzeugen?
Nein.
Immer noch nichts.
Jetzt gucken wir ein Teilwort der Länge 3 an und entsprechend hier
auch ein Teilwort der Länge 3.
Jetzt steht hier vorne schon eine leere Menge, das heißt überhaupt
keine Chance.
Wir haben überhaupt kein, ups, nicht da, das wäre fatal.
Wir haben kein Zeichen gefunden, aus dem wir BAAB ableiten können.
Hört man schon nervös, ob wir überhaupt das ganze Wort ableiten können
oder nicht.
Schauen wir uns das Feld daneben an.
Nochmal.
Sie sehen, ich kann wieder durchnummerieren.
Offensichtlich geht das ganz einfach mit dem Durchnummerieren.
Das ist hier mein Feld, das ich betrachte.
Da muss ich ja nur hier schreiben 1, 2, 3 und hier 1, 2, 3.
Das ist ja ganz einfach.
Ich muss von oben anfangen 1, 2, 3 und dann hier nochmal 1, 2, 3
hinschreiben auf der Diagonale von dem Feld.
Und dann schaue ich mir die gleichartig nummerierten Felder an.
1, 1, da steht A, B.
A, B kann ich ableiten, da steht ein S.
Hervorragend, das S haben wir hier.
A, B.
Dann habe ich noch C, B.
C, B taucht nicht auf.
Dann muss ich mir 2, 2, die beiden Felder, die mit 2 markiert sind,
anschauen.
B, A, kann ich das ableiten?
Das geht.
Ich kann also das A auch noch reinschreiben.
Kann ich B, S ableiten?
Das geht nicht.
Bleibt es bei dem A jetzt.
Dann müssen wir noch 3 und 3 vergleichen.
Haben wir B und A, können wir ableiten.
B und A kann ich aus A ableiten, das steht schon drin.
B und C kann ich auch ableiten.
Von dem S steht auch schon drin.
Das heißt, jetzt habe ich hier S, A drin stehen.
Entschuldigung, ich habe hier...
Da hätte ich...
Was habe ich denn jetzt hier gemacht?
Nochmal.
Richtig, jetzt gucken wir dieses Feld hier an, das gucken wir an.
Was fehlt jetzt noch?
1, 2, 3, das war richtig.
Ja, was fehlt noch?
S, A.
Schauen wir uns das nochmal an.
Wir haben hier A, B, das C fehlt noch.
Vielen Dank.
Ja, das war das erste.
Ich kann ja das A, B aus S und aus C ableiten.
Vielen Dank für den Hinweis.
Da stehen also S, A und C drin.
Also, das war hier das zweite Wort der Länge 4.
Und jetzt können wir das wieder alles, nachdem wir uns das hier
gemerkt haben, können wir das wieder alles wegwischen.
Und jetzt füllen wir das entscheidende letzte Feld aus.
Und bei dem letzten Feld machen wir wieder alles genauso wie vorher.
Nummerieren die Felder bis dahin mit 1, 2, 3, 4.
Und entsprechend auf der Diagonale 1, 2, 3, 4.
Und kombinieren jetzt entsprechend die gleich nummerierten Felder.
Das sind nämlich genau die Teilmengen, die ich angucken muss, um
rauszufinden, welche Paare von Nicht-Terminalzeichen erzeugt worden
sein könnten.
Und Sie sehen, wir haben hier jetzt die Frage, können wir B, S
ableiten?
Nein.
Können wir B, C ableiten?
Ja.
Damit sind wir eigentlich schon fertig.
Das S ist hier drin und wir können sagen, das Wort ist insgesamt
ableitbar.
Wir können es aber auch noch weiterführen.
Wir können gucken, ob das B, A ableitbar ist.
Da müsste also das A auch noch rein.
Und dann geht es um die nächsten Felder.
A, A oder A, S oder S, A oder S, S.
Geht alles nicht abzuleiten.
Ups, falsch war das.
A, B.
Hier, 2, 2.
A, B oder S, A.
A, B ist ableitbar.
Da kommt das S nur wieder mit rein oder auch das C.
Und da haben wir also hier auch S, A und C drin stehen.
Und entsprechend müssen wir die Dreierfelder anschauen.
Das ist jetzt leere Menge und dieses Feld.
Hier steht auch leere Menge und das Feld.
Das heißt, mehr kommt nicht dazu.
Und wir haben als letztes also hier das Ergebnis S, A, C dort stehen.
Und damit wissen wir, wir können dieses Wort B, A, A, B, A aus drei
verschiedenen Variablen ableiten, nämlich aus S, aus A und aus C.
Und da wir das aus S ableiten können, wissen wir, dass das W ein Wort
der Sprache ist, die wir durch diese Grammatik erzeugen können.
Und damit habe ich Ihnen eine sehr einfache Veranschaulichung gegeben,
wie man systematisch vorgeht, um irgendein Feld auszufüllen.
Sie nummerieren einfach die Felder von oben nach unten aufsteigend und
dann auf der Diagonalen, die davon ausgeht, auch aufsteigend und
müssen einfach die Paare von Feldern vergleichen beziehungsweise die
Nicht -Terminale da drin und gucken, gibt es Regeln, bei denen genau
Paare aus diesen beiden Feldern erzeugt werden und das entsprechende
Nicht -Terminalzeichen muss ich da reinschreiben.
Jetzt gibt es hier eine Frage.
Woher weiß man, welche Felder kombiniert werden müssen?
Genau diese Frage habe ich Ihnen gerade eben beantwortet.
Und das ist nämlich genau diese Überlegung, wenn ich hier irgend so
ein Wort der Länge J betrachte, dann schaue ich mir irgendeine
Aufteilung an, in ein Teilwort der Länge K und ein Teilwort der Länge
J minus K und dann habe ich insgesamt das Teilwort der Länge J
betrachtet mit irgendeinem solchen Eintrag und ich muss halt von K
gleich 1 bis J minus 1 gehen, weil das genau die Anzahl der Aufteilung
ist, die ich machen kann.
Und damit weiß ich, wie ich das hier machen muss, damit habe ich die
Nummerierungen, weil das erste Zeichen bezieht sich entweder auf ein
Teilwort der Länge 1, 2, 3 oder 4, das ist also das Hochzählen des Ks
und das zweite, damit so kombinierende Feld ergibt sich dann
entsprechend daraus, oder muss ich dann entsprechend hier über die
Diagonale gehen, weil das gerade die restlichen Mengen sind, die sich
auf das entsprechende weitere Teilwort beziehen.
Damit ist also ein wichtiger Algorithmus Ihnen vorgestellt und ich
hoffe, dass Sie das nachvollziehen konnten, die Vorgehensweise ist
wirklich sehr einfach.
Zur Komplexität, wie komplex, gehen wir mal kurz zurück, was ist denn
hier für ein Aufwand?
Sie können das im Algorithmus ableiten, wenn Sie uns hier den
Algorithmus anschauen, da steht es ja genau drin, wir haben hier eine
dreifach geschachtelte Schleife und damit sind wir eigentlich schon
fertig, 2 bis n, 1 bis n minus j plus 1, 1 bis j minus 1, das ist
Größenordnung, dreifach geschachtelte Schleife, jeweils bis
Größenordnung n, also n hoch 3, wir sind fertig, Sie können sich das
auch hier nochmal angucken, hier müssen Sie jedes Feld ausfüllen, das
sind n Quadratfelder und der Aufwand pro Feld ist linear.
Sie müssen nur n viele oder j viele Felder dort jeweils betrachten.
Damit wissen wir, dass die Komplexität in n hoch 3 ist und das war
sehr einfach festzustellen, n mal Anzahl der Regeln, die Berechnung
von vij, das ist also deswegen linear in der Berechnung von vij und
weniger als n Werte für k, genau, das ist jeweils linear und n mal p
ist auf jeden Fall eine immer gültige Abschätzung nach oben und ich
muss weniger als n Quadrat betrachten, nämlich genau eine Hälfte der
ganzen Matrix, eine Dreiecksmatrix und damit habe ich also insgesamt
einen Aufwand von n hoch 3 und ich weiß damit, dass sich das
Wortproblem in der Zeit n hoch 3 lösen kann.
Damit bin ich zufrieden und auch wieder nicht zufrieden, denn Aufwand
n hoch 3 ist mir viel zu viel, um tatsächlich damit eine Basis zu
haben, Programme zu beschreiben oder Programmiersprachen zu
beschreiben, denn das war unsere Ausgangsfragestellung, was ist das
formale Modell, das es mir erlaubt, möglichst effizient zu überprüfen,
ob ein Programm richtig beschrieben ist, also richtig aufgeschrieben
ist, das war das Wortproblem und n hoch 3 ist mir viel zu groß.
Und wir wissen bei den Kellerautomaten, da hatten wir schon mal
gesagt, bei nicht deterministischen Kellerautomaten, da ist es nicht
linear, wenn wir Pech haben, also da geht es eben auch in n hoch 3.
Jetzt wissen wir, für kontextfreie Grammatiken generell geht das in n
hoch 3, aber es wäre natürlich gut, wenn wir generell bei den
Programmiersprachen, die wir beschreiben, uns auf lineare Zeit für das
Wortproblem beschränken können.
Wenn wir also die Komplexität der Grammatiken, die wir aufschreiben,
so reduzieren können, dass das Wortproblem in linearer Zeit lösbar
ist.
Und bei den Kellerautomaten, bei den Akzeptoren, über die
Unterscheidung deterministisch oder nicht deterministisch, bei den
Grammatiken kann man das tatsächlich auch hinbekommen.
Und da ist es eine Notation, die nennt sich LRK-Grammatiken.
LR von K-Grammatiken.
Das will ich Ihnen nur ganz kurz andeuten, was da eigentlich passiert
bei LRK-Grammatiken.
Wir haben bei LRK-Grammatiken, die deswegen LRK genannt, von links
nach rechts durch ein Wort durchgehen.
Left to right passing.
Passing heißt also überprüfen der Syntax dieses Wortes.
Von links nach rechts.
Und wir wollen eine Rechtsableitung ableiten.
Links nach rechts lesen und dabei eine Rechtsableitung simulieren.
Das war schwierig.
Sie erinnern sich, unsere einfache Art, wie wir das Ableiten von
Wörtern einer Sprache durch kontextfreie Regeln mit einem
Kellerautomaten simuliert haben.
Das war ja überprüfen von ausgehend von einem Wort, wie ist das Ding
abgeleitet worden.
Das war ganz einfach, das mit der Linksableitung zu machen.
Da mussten wir nur im Keller irgendwas tun, bis wir also wieder ein
Terminalzeichen erzeugt haben.
Da haben wir aber im Prinzip immer die linkeste Variable ersetzt.
Und jetzt müssen wir schauen, wir wollen eine Ableitung hinbekommen,
eine Rightmost Derivation, eine Rechtsableitung.
Eine Rechtsableitung heißt immer, die rechteste Variable, die noch
übrig ist, wird ersetzt.
Das heißt aber auch, dass das Zeichen hier vorne als letztes ersetzt
wird.
Und danach werden irgendwelche anderen Wörter ersetzt.
Das heißt, sukzessive werden wir durch das Wort durchwandern und
werden immer feststellen können, welche anderen Regeln da angewendet
sein können.
Und man stellt fest, beim sukzessiven Abarbeiten meines Wortes, bei
dem ich also hier irgend so ein Zeichen mir anschaue, da habe ich in
der Simulation meiner Ableitung im Keller im Prinzip etwas stehen, wo
ich nur dann schließen kann auf die Regel, die angewendet worden sein
muss bei der Ableitung, wenn ich mir eine gewisse Vorausschau K gönne.
Das heißt, ich habe eine gewisse Vorausschau von K-Zeichen nach rechts
und dadurch, dass ich in meinem Terminalwort auf dem Eingabeband ab
der aktuellen Position noch so K-Zeichen vorausschauen darf, kann ich
entscheiden, welches die letzte Regel war, die hier angewendet worden
sein kann in meiner Ableitung des Wortes.
Das ist jetzt etwas kompliziert, formal ist es hier aufgeschrieben.
Ich soll also Rechtsableitungen ableiten oder nachsimulieren und ich
soll aus einem Wort W die Rechtsableitung generieren und dabei darf
ich an jeder Position maximal K-Zeichen vorausschauen.
Und das, was hier formal gilt, ist an dieser Stelle genau
aufgeschrieben und ich möchte einfach an dieser Stelle dieses Thema
einfach dabei belassen, dass ich Ihnen sage, man kann durch diese
Formulierung, die hier steht, ich habe also rechts, wenn ich also zwei
verschiedene Wörter hätte, nehmen wir mal, ich hätte zwei verschiedene
Wörter, bin in einer gewissen Position und rechts, dieses Stück an
dieser Position ist identisch, dann kann ich daraus schließen, welche
Regel angewendet worden sein muss.
Das ist also eine Regel A auf Beta, hier dieses A auf Beta abgeleitet
worden sein muss.
Ich nehme einfach an, es könnte auch eine andere Ableitung gegeben
haben, bei der ich ein B auf ein Delta abgeleitet habe und es ist dann
hier etwas rausgekommen, was aber im Anfangsstück gleich ist, so etwas
kann nicht passieren, sondern ich kann aus der Gleichheit des
Anfangsstücks der Länge K, das ich hier sehen kann, dieses Stück hier
schließen, welche Regel angewendet worden sein muss.
Das ist hier formal aufgeschrieben, ich gehe hier nicht in die
weiteren Einzelheiten, ich muss ein bisschen auf die Zeit schauen und
dass die LRK-Grammatiken mit ihren Einzelheiten sind auch nicht
wirklich Gegenstand von expliziten Fragen in den Klausuren, weil das
hier einfach zu weit führen würde, da müsste man ein bisschen mehr
darüber wissen.
Das, was hier steht, ist alles ausreichend, um das im Prinzip
nachzuvollziehen, aber ich will an dieser Stelle das abkürzen und
eigentlich nur darauf hinweisen, dass genau dieses hier die
Grammatiken sind, die den deterministischen Kellerautomaten
entsprechen.
Man kann sogar zeigen, dass man hier auf das K gleich 1 sich
reduzieren kann.
Also jede LRK-Grammatik hat eine äquivalente LR1-Grammatik, das heißt,
ich muss nur mir das nächste Zeichen anschauen können und das nächste
Zeichen, da geht es im Prinzip nur darum, ob das Wort zu Ende ist oder
nicht.
Das heißt, das geht sogar relativ einfach.
Aber das sind alles weiterführende Dinge, die ich hier nicht im
Einzelnen ausführen kann.
Das wäre Thema einer Vorlesung über Compilerbau, wo man dann auch noch
LL -Grammatiken hinschreiben kann, LL von K und so weiter.
Es gibt viele interessante Dinge, die man hier noch machen kann, mit
denen ich Sie aber nicht mehr jetzt konfrontieren möchte.
Und damit sind wir am Ende dieses Kapitels über kontextfreie
Grammatiken und Kellerautomaten und Sie haben gesehen, das sind
gleichartige Konzepte.
Wir können zu jeder kontextfreien Grammatik einen Kellerautomaten
konstruieren, der die gleiche Sprache akzeptiert, die die Grammatik
erzeugt.
Und wir können sogar für die deterministischen Kellerautomaten
äquivalente Grammatiken finden, nämlich die LRK-Grammatiken.
Und das sind genau die Sprachklassen, die wir brauchen, genau diese
Klasse der LRK-Grammatiken und der deterministischen Kellerautomaten,
die von denen erzeugt oder akzeptiert werden.
Das sind die formalen Modelle, die wir für Programmiersprachen
brauchen.
Das ist die wesentliche Erkenntnis dieses Kapitels.
Insbesondere werden wir eben sehen, wenn wir darüber hinausgehen, wird
es erst recht schwierig.
Wir hatten schon gesehen, bei den nicht deterministischen
Kellerautomaten sind wir in einem Bereich, wo es schwierig wird, wo es
aufwendig wird und es wird noch aufwendiger, wenn wir weiter darüber
hinausgehen.
Das machen wir jetzt im nächsten Kapitel, bei dem es geht um die
kontextsensitiven Sprachen.
Und erlauben Sie mir, dass ich direkt weitermache.
Übrigens wollte ich noch einen Hinweis geben darauf, dass wir jetzt
den ersten Umfrageteil ins Netz stellen.
Das müsste auf den Webseiten der Vorlesung angekündigt sein, wo Sie
genau nachsehen können, wo Sie sich diesen sogenannten Survey
anschauen können.
Da sind eine ganze Reihe Aufgaben, die werden entweder jetzt schon
oder im Laufe der Woche Ihnen bereitgestellt, sodass Sie dann über
unsere Werkzeuge dort eine Reihe von Aufgaben beantworten können.
Aufgaben, die in ähnlicher Form auch in Klausuren auftauchen könnten.
So, dann zur Präsentation des nächsten Kapitels, Kapitel 4,
kontextsensitive Sprachen, allgemeine Sprachen und Turing-Maschinen.
Wir wollten hier die Chomsky-Hierarchie vollständig abarbeiten.
Es fehlen noch die nächsten beiden Klassen, Typ 1 und Typ 0.
Und bei Typ 1-Sprachen fangen wir jetzt tatsächlich mit den
Grammatiken an, nicht mit den Automaten wie bei den anderen beiden
Klassen.
Wir haben übrigens auch bei den kontextfreien die operationelle
Charakterisierung weggelassen.
Auch das könnte man noch alles machen.
Ich könnte Ihnen eine abstrakte Sprachfamilie über Operation
definieren, die genau die kontextfreien Sprachen beschreibt.
Das lassen wir aber raus.
Und wir kommen jetzt zu den kontextsensitiven Sprachen.
Und Sie erinnern sich, was war kontextsensitiv?
Das bedeutete, ich habe eine Ableitung zu machen, ich möchte ein
Zeichen A ersetzen durch eine rechte Seite, eine Regel, aber der
Kontext, der ist in dem Fall wichtig, Vieh 1, Vieh 2, Vieh 1, Vieh 2.
Das heißt, die Regeln meiner kontextsensitiven Grammatik sehen so aus,
dass ich ein Nicht-Terminalzeichen nur in einem gewissen Kontext
ersetzen kann.
Und ich hatte Ihnen auch gezeigt, dass man das noch verallgemeinern
kann, das kommt gleich noch, dass man sagen kann, die müssen
mindestens monoton sein.
Die Monotonie, die ergibt sich eben daraus, dass die rechte Seite
dieses Psi immer nicht leer ist.
Und das heißt, ich kann dieses Nicht-Terminalzeichen nur durch eine
Zeichenfolge ersetzen, die aus mindestens einem Zeichen besteht.
Also ist die rechte Seite meiner Regel niemals kürzer als die linke
Seite der Regel.
Typische Beispiele sind hier angegeben, also es kann links irgendetwas
stehen, Sie sehen, hier habe ich also einen Kontext für das Zeichen a,
da steht ein kleines a, b links daneben und ein großes b, und ich
ersetze das große a durch ein kleines a.
Oder hier steht das a, b wird durch klein a, b ersetzt, oder hier das
a, b, c, da wird das Wort oder die Variable b durch ein klein b
ersetzt, aber nur im Kontext a und c.
Das sind die kontextsensitiven Regeln.
Beispiele für nicht-kontextsensitive Regeln sind hier angegeben, da
habe ich also a, b links stehen und c, d rechts.
Da taucht der Kontext nicht wieder auf.
Ich habe also kein Nicht-Terminalzeichen, das ich hier ersetze durch
ein Wort und der Kontext ist noch da, es taucht weder das b noch das a
auf, das ist nicht kontextsensitiv.
Genauso a, b auf b, a.
Es taucht hier zwar das a wieder auf, aber rechts von dem b, das passt
nicht, andersrum genauso.
Das a, b, c durch b, c geht auch nicht, da ist die rechte Seite
kürzer.
Und genauso hier c, d auf klein c geht auch nicht, da ist die rechte
Seite kürzer.
Das ist nicht erlaubt.
Also das sind nicht-kontextsensitive Regeln.
Und diese, ja, was hier oben drüber steht, jede Regel von der Form a
auf phi mit phi aus n vereinigt t Stern, äh nicht t Stern, sondern t
Plus.
Das ist natürlich auch eine kontextsensitive Regel, bei der der
Kontext links und rechts daneben leer ist.
Deswegen ist das so eine kontextfreie Regel.
Also jede kontextfreie Regel mit einer nicht-leeren rechten Seite ist
natürlich auch eine kontextsensitive Regel.
Und damit können wir dann auch noch diese andere Definition uns kurz
anschauen.
Es gibt eine andere Definition, die sagt, eine Grammatik nennt man
monoton, wenn bei allen Regeln die rechte Seite mindestens so lang ist
wie die linke Seite.
Und es ist offensichtlich, dass jede kontextsensitive Regel monoton
ist.
Tatsächlich ist es so, dass sich zu jeder monotonen Grammatik auch
eine äquivalente kontextsensitive Grammatik erzeugen kann.
Das heißt, ich kann tatsächlich aus jeder Regel, bei der die rechte
Seite mindestens so lang ist wie die linke Seite, eine Grammatik
konstruieren, sodass ich also genau diese Form habe mit dem Kontext,
das nur ein Nicht-Terminalzeichen ersetzt wird in einer bestimmten
Umgebung.
Ich kann sogar, und das ist interessant, ich kann sogar das so machen,
dass für alle Regeln folgendes gilt, natürlich dieses kleiner gleich
psi und das hier kleiner gleich zwei.
Das ist aber eine gewaltige Einschränkung.
Sie erinnern sich, Chomsky-Normalform.
Ich habe also im Prinzip sogar für die kontextsensitiven Regeln so
etwas Ähnliches wie die Chomsky-Normalform.
Ich kann das sogenannte Gewicht zwei dort reinschreiben.
Jede rechte Seite hat maximal zwei Zeichen, jede linke Seite natürlich
damit auch.
Und ich kann tatsächlich zeigen, dass sich jede kontextsensitive
Sprache, die von einer beliebigen Grammatik erzeugt wird, die
kontextsensitiv ist oder monoton, eine Äquivalente finden kann, bei
der die Zeichen rechts oder alle vorkommenden Zeichenfolgen in den
Regeln maximal die Länge zwei haben.
Sieht zunächst aus wie eine ganz starke Einschränkung, man kann das
aber hinbekommen.
Hier ist der Aufwand, um das zu tun, das zu zeigen, etwas
umfangreicher als das, was wir bei der Chomsky-Normalform gemacht
haben, deswegen stelle ich Ihnen den Satz nicht vor, aber das wäre
eine interessante Übungsaufgabe, das zu machen.
Kleines Beispiel, wir betrachten eine monotone Grammatik.
Und diese monotone Grammatik, warum ist die nicht kontextsensitiv?
Hier sehen Sie, die meisten Regeln haben eine schöne Form.
Hier links nur ein Nicht-Terminalzeichen, das ist sogar kontextfrei.
Das hier ist kontextsensitiv, da haben wir bei Fb stehen, das ist eben
nicht kontextsensitiv.
Fb auf Bf ist eine Umstellung der beiden Zeichen und diese
Vertauschung von Zeichen ist keine kontextsensitive Regel.
Das heißt, diese Regel ist nicht kontextsensitiv, wir müssen daran
irgendwas tun.
Und die anderen sind alle kontextsensitiv.
Das heißt, nur diese eine zwar monotone, aber nicht kontextsensitive
Regel stört das Bild.
Wir müssen uns anschauen, wie man die jetzt umordnen oder umbauen
könnte.
Nur kurz als Bemerkung, wenn Sie sich anschauen, was hier gemacht
wird, Sie erzeugen hier aus dem Startsymbol, wenn Sie damit anfangen,
durch Anwenden dieser Regel, S auf A, E, B, C.
Aha, ein A, rechts daneben ein B, C.
Und aus E können Sie, was können Sie da erzeugen?
Aus E können Sie nochmal A und B erzeugen und ein F.
Das heißt, Sie können dann das beliebig weiter fortführen, das E
taucht ja hier rekursiv auf.
Sie haben also durch die erste Regel, S auf A, E, B, C, dafür gesorgt,
dass ganz rechts ein C steht und ein B.
Und dann können Sie über wiederholte Anwendung dieser Regel E auf A,
E, B, F dafür sorgen, dass Folgendes passiert, dass Sie hier eine
beliebige Folge von As haben, gefolgt von einer genauso langen Folge
von Bs und Fs daneben.
Das heißt, Sie haben dann immer abwechselnd B und F daneben stehen und
jetzt können Sie die Fs und die Bs miteinander vertauschen.
Sie können also alle Fs ganz nach rechts rüberschieben.
Dann haben Sie hier stehen A hoch I plus 1, B hoch I plus 1 mal F hoch
I und ein C daneben.
Das geschieht also über diese Regeln.
Und dann dürfen Sie jedes F, das links neben einem C steht, durch ein
C ersetzen.
Wenn Sie das oft genug machen, kommen Sie auf A hoch I plus 1, B hoch
I plus 1, C hoch I plus 1.
Das heißt, Sie können mit dieser Grammatik solche Wörter erzeugen, die
wir vorher mit kontextfreien Regeln nicht erzeugen konnten, nämlich A
hoch I plus 1, B hoch I plus 1, C hoch I plus 1.
Und der Trick dabei war, dass wir einfach nicht erst diese I plus 1 As
mit I plus 1 Bs zusammen erzeugen, sondern im Prinzip zu jedem A auch
gleichzeitig ein B und C bzw.
B und F.
Das ist hier dieser Trick.
Und dann dafür sorgen, dass wir diese Fs alle loswerden können.
Also ein Wort dieser Art, bei der Sie immer abwechselnd so ein Beat,
wenn Sie also A hoch N, so eine Sprache, A hoch N und dann B, C hoch
N, die wäre natürlich problemlos durch eine kontextfreie Grammatik
erzeugbar, weil Sie jeweils nur zwei Zeichen zu jedem A entsprechend
dazufügen müssen.
Das wäre gar kein Problem, auch durch den Kellerautomaten zu erkennen.
Wir hatten gesehen, das Problem ist in dem Augenblick, wo die Bs und
Cs ganz voneinander getrennt sind.
Und genau das macht man hier durch das Umsortieren.
Das ist also der wesentliche Teil, der über die Kontextfreiheit
hinausgeht, das wir umordnen können.
So, nun müssen wir zeigen, dass wir diese Regel kontextsensitiv machen
können.
Ja, also das ist klar.
Das ist hier eine Ableitung.
Ich habe Ihnen das gerade eben dargestellt, wie man das im Prinzip
machen kann.
Das ist also klar, dass das diese Sprache ist.
Wir müssen uns jetzt überlegen, wie kann man diese eine Regel
umwandeln.
Und das geht sehr einfach.
Wie kann man das machen?
Ich baue einfach die Regel.
Die Regel, die uns störte, war die Regel fb auf bf.
Und diese Regel ersetzt sich einfach durch eine solche Regel fb auf
f1b.
Ich habe also neue Nicht-Terminalzeichen zugefügt.
Dann ist das hier kontextsensitiv.
Das f wird durch f1 ersetzt in den Kontext b.
Wenn das f1 neben einem b steht, wird das b durch ein f ersetzt.
Und das f1 bleibt stehen.
Und wenn das f1 neben einem f steht, kann ich daraus das f1 durch ein
b ersetzen.
Und das große b darf ich durch ein kleines b ersetzen.
Und damit habe ich durch diese Regeln hier mir die Möglichkeit
geschaffen, aus fb durch eine Folge von Ableitung bf zu erzeugen.
Und man kann sich überlegen, dass mich auch nur dieses ableiten kann.
Wenn ich es anders anwende, wenn ich es anders kombiniere, kann ich
kein Wort erzeugen, das tatsächlich nur noch Terminalzeichen enthält.
Und damit bin ich dann fertig und habe gezeigt, diese Grammatik hier
ist dann kontextsensitiv.
Das ist die Art, wie ich also aus monotonen kontextsensitiven
Grammatiken machen kann.
Und wenn Sie jetzt noch dafür sorgen müssen, dass rechts tatsächlich
immer die Größe Länge 2 bleibt, wird das noch aufwendiger.
Das wären noch interessante Aufgaben für die Übungen.
Und damit haben wir also gezeigt, dass die Menge der kontextsensitiven
Sprachen umfangreicher ist als die Menge der kontextfreien Sprachen,
dass diese Sprache A-Hoch-N, B-Hoch-N, C-Hoch-N dort drin ist.
Und wie das dann oben drüber aussieht, das ist ein Thema nicht für den
Mittwoch.
Mittwoch gibt es keine Vorlesung Grundlagen der Informatik 2.
Mittwoch, das ist der 20.11.2013, keine Vorlesung.
Und zwar ist am Mittwoch der sogenannte Uni-für-Einsteiger-Tag und da
wird der Hörsaal gebraucht, ab 8 Uhr morgens.
Deswegen können wir dort leider die Vorlesung nicht machen.
Wir nutzen das aus am Lehrstuhl, um dann gleichzeitig eine
Lehrstuhlklausur zu machen, wo wir uns intensiv zusammensetzen, um
Wissenschaft zu betreiben.
Ich danke Ihnen für die Aufmerksamkeit, das war es für heute.