|
Für die Sprache L={aibjck |i,j,k∈IN und k=i+j} zeigen wir mittels des Satzes von Chomsky-Schützenberger ihre Kontextfreiheit.
Ist die Sprache kontextfrei, so können wir eine Dycksprache Dn, einen Regulären Ausdruck R und einen Homomorphismus h angeben, so dass:
h(R∩Dn) = L
0. L lässt sich schreiben als L= {aibjci+j} = {aibjcjci} .
So sind die Abhängigkeiten zwischen den Wortteilen deutlich zu erkennen.
Es gibt zwei ordentlich ineinander verschachtelte Paare (ausgedrückt durch gleiche Potenz)
1. R = {a1*b1*b2*a2*}
Die erkannten Paare wurden in einem Regulären Ausdruck beschrieben.
Das Vokabular hat sich dabei verändert, denn an dieser Stelle ist lediglich die Abfolge einzelner Zeichen im Wort wichtig.
Ein RA kann nur die Reihenfolge der Zeichen, nicht ihre Anzahl und evtl. Abhängigkeiten bestimmen, dies wird erst durch einen Schnitt mit einer Dycksprache erreicht.
2. R muss mit D2 geschnitten werden.
Wir haben oben zwei zusammengehörige Paare anhand ihrer übereinstimmenden Potenz erkannt.
Damit ist n=2. Öffnende Klammern tragen den Index 1, die schließenden den Index 2.
Somit bilden a1 und a2, sowie b1 und b2 jeweils ein Paar.
3. (R∩D2) = {a1mb1nb2na2m}
Der Schnitt mit der Dycksprache sorgt für die gleiche Anzahl öffnender und schließender Klammern eines Paares.
Deutlich durch den Index zu erkennen.
4.
| a |
a1 |
b1 |
a2 |
b2 |
|---|
| h(a) |
a |
b |
c |
c |
Ein Homomorphismus muss nun vom Alphabet der Schnittmengensprache in das Alphabet von L abbilden.
5. h(R∩D2)={ambncncm}
Die Ausgangssprache L ist bereits zu erkennen. Es fehlt nur noch eine kleine Anpassung bei der Bezeichnung der Potenzen.
| 
1
2
3
4
5
6
Weitere Beispiele