{"id":1883,"date":"2013-06-04T11:20:21","date_gmt":"2013-06-04T09:20:21","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=1883"},"modified":"2025-11-25T23:05:25","modified_gmt":"2025-11-25T22:05:25","slug":"tib-kontextfreie-sprachen-und-kellerautomaten-lernziele-ke7-13","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=1883","title":{"rendered":"TIB: Kontextfreie Sprachen und Kellerautomaten (Lernziele KE7 1\/3)"},"content":{"rendered":"

Update<\/strong>: Fl\u00fcchtigkeitsfehler rausgenommen.<\/p>\n

Das ist nun die letzte Kurseinheit der theoretischen Informatik B. Traurig? \ud83d\ude09<\/p>\n

In dieser Kurseinheit geht es um kontextfreie Sprachen (also Sprachen, die Typ-2 und -3 erzeugen). Am besten man betrachtet die letzten drei Kurseinheiten gemeinsam, ggf. erstelle ich eine kleine Zusammenfassung der Kernaussagen bei Gelegenheit um aus den Puzzleteilen wenigstens teilweise ein Gesamtbild zu bekommen.<\/p>\n

Lernziel 1<\/h2>\n

Wann ist eine Grammatik in Chomsky-Normalform und wie konstruiert man eine solche aus einer beliebigen kontextfreien Grammatik?<\/em><\/p>\n

Zun\u00e4chst geht es um die Eliminierung von \\(\\epsilon\\)-Regeln. Unserem leeren Wort, welches als Abschluss einer Ableitung fungiert, indem man ein Nonterminal durch \\(\\epsilon\\) ersetzt. D.h. was wir wollen, ist es die\u00a0\\(\\epsilon\\)-Regeln (z.B.\u00a0\\(A\\rightarrow\\epsilon\\)) loszuwerden um eine „effektive“ Notation zu bekommen. Aber der Reihe nach:<\/p>\n

Chomsky Normalform:<\/strong><\/p>\n

Eine Chomsky Normalform liegt dann vor, wenn alle Regeln\/Produktionen die Form \\((A\\rightarrow a)\\) oder\u00a0\\((A\\rightarrow BC)\\) besitzen mit \\(A,B,C\\in\\Pi\\) und \\(a\\in\\Sigma\\).<\/p><\/blockquote>\n

D.h. wir d\u00fcrfen hier keine \\(\\epsilon\\)-Regeln haben und die rechte Seite der Produktion darf entweder nur aus einem Symbol (noch aus mehreren) aus unserem Alphabet oder aus einer Kombination von maximal zwei Nonterminalen bestehen.<\/p>\n

Die Frage ist: wie kommen wir von einer kontextfreien Grammatik zu einer in Chomsky Normalform? Ich finde, dass so etwas am besten an einem Beispiel (aus dem Buch von Dirk W. Hoffmann) gezeigt wird.<\/p>\n

Beispiel<\/strong>: Grammatik \\(G\\) mit Regelmenge<\/p>\n

\\(S\\rightarrow AB\\)<\/p>\n

\\(S\\rightarrow ABA\\)<\/p>\n

\\(A\\rightarrow aA\\)<\/p>\n

\\(A\\rightarrow a\\)<\/p>\n

\\(B\\rightarrow Bb\\)<\/p>\n

\\(B\\rightarrow\\epsilon\\)<\/p>\n

1. Elimination der \\(\\epsilon\\)-Regeln<\/strong><\/p>\n

Hier entfernen wir zun\u00e4chst alle Regeln der Form \\(A\\rightarrow\\epsilon\\). Wir man sehen kann, wird das Nonterminal \\(B\\) in unseren regeln durch \\(\\epsilon\\) ersetzt. Diese Ersetzung k\u00f6nnen wir durch Hinzuf\u00fcgen neuer Regeln „vorwegnehmen“.<\/p>\n

\\(S\\rightarrow AB\\)<\/p>\n

\\(S\\rightarrow A\\)<\/p>\n

\\(S\\rightarrow ABA\\)<\/p>\n

\\(S\\rightarrow AA\\)<\/p>\n

\\(A\\rightarrow aA\\)<\/p>\n

\\(A\\rightarrow a\\)<\/p>\n

\\(B\\rightarrow Bb\\)<\/p>\n

\\(B\\rightarrow b\\)<\/p>\n

H\u00e4tten wir z.B. mit der initialen Regelmenge die Ableitungssequenz \\(S\\Rightarrow ABA\\Rightarrow AA\\) (Regel 2, Regel 6), so haben wir nun nur noch die Sequenz:\u00a0\\(S\\Rightarrow AA\\) (Regel 4). Die Ersetzung von \\(B\\) durch \\(\\epsilon\\) wurde durch neue Regeln obsolet und wir sind der Chomsky Normalform, wo eben \\(\\epsilon\\) kein Teil der Sprache ist, ein Schritt n\u00e4her.<\/p>\n

2. Elimination von Kettenregeln<\/strong><\/p>\n

Nun k\u00fcmmern wir uns um die Kettenregeln. Regeln, die von einem Nonterminal auf ein Nonterminal (\\(S\\rightarrow A\\rightarrow a\\)) zeigen sind ebenfalls unn\u00f6tig. Wir gehen vor wie in Schritt eins.<\/p>\n

\\(S\\rightarrow AB\\)<\/p>\n

\\(S\\rightarrow aA\\)<\/p>\n

\\(S\\rightarrow a\\)<\/p>\n

\\(S\\rightarrow ABA\\)<\/p>\n

\\(S\\rightarrow AA\\)<\/p>\n

\\(A\\rightarrow aA\\)<\/p>\n

\\(A\\rightarrow a\\)<\/p>\n

\\(B\\rightarrow Bb\\)<\/p>\n

\\(B\\rightarrow b\\)<\/p>\n

3. Separation von Terminalzeichen<\/strong><\/p>\n

Jetzt sind die Terminalzeichen dran. Wir brauchen auf der rechten Seite nur Zweier-Kombinationen aus Nonterminalen oder ein einzelnes Terminal. Wir ersetzen also z.B. \\(aA\\) durch \\(\\Pi_a A\\), wobei \\(\\Pi_a\\) ein neues Nonterminal ist, welches mit einer neuen Regel auf \\(a\\) zeigt. Aus \\(S\\rightarrow aA\\) wird also \\(S\\rightarrow\\Pi_a A\\) und \\(\\Pi_a\\rightarrow a\\).<\/p>\n

\\(S\\rightarrow AB\\)<\/p>\n

\\(S\\rightarrow \\Pi_aA\\)<\/p>\n

\\(S\\rightarrow a\\)<\/p>\n

\\(S\\rightarrow ABA\\)<\/p>\n

\\(S\\rightarrow AA\\)<\/p>\n

\\(A\\rightarrow \\Pi_aA\\)<\/p>\n

\\(A\\rightarrow a\\)<\/p>\n

\\(B\\rightarrow B\\Pi_b\\)<\/p>\n

\\(B\\rightarrow b\\)<\/p>\n

\\(\\Pi_b\\rightarrow b\\)<\/p>\n

\\(\\Pi_a\\rightarrow a\\)<\/p>\n

4. Elimination der Nonterminalketten<\/strong><\/p>\n

Letzter Schritt: zu lange Nonterminalketten auf die Maximall\u00e4nge von \\(2\\) verkleinern. Das Vorgehen kennt ihr ja schon, es wird einfach eine neue Zwischenregel eingef\u00fcgt. Aus \\(S\\rightarrow ABA\\) werden also \\(S\\rightarrow S_{2}A\\) und\u00a0\\(S_2\\rightarrow AB\\):<\/p>\n

\\(S\\rightarrow AB\\)<\/p>\n

\\(S\\rightarrow \\Pi_aA\\)<\/p>\n

\\(S\\rightarrow a\\)<\/p>\n

\\(S\\rightarrow S_{2}A\\)<\/p>\n

\\(S_2\\rightarrow AB\\)<\/p>\n

\\(S\\rightarrow AA\\)<\/p>\n

\\(A\\rightarrow \\Pi_aA\\)<\/p>\n

\\(A\\rightarrow a\\)<\/p>\n

\\(B\\rightarrow B\\Pi_b\\)<\/p>\n

\\(B\\rightarrow b\\)<\/p>\n

\\(\\Pi_b\\rightarrow b\\)<\/p>\n

\\(\\Pi_a\\rightarrow a\\)<\/p>\n

Fertig! Aus eindeutigen Grammatiken lassen sich auch eindeutige Chomsky-Grammatiken erstellen.<\/p>\n

Vorteile<\/strong>? Jedes Wort \\(\\omega\\) mit \\(\\mid\\omega\\mid=n\\) braucht \\(2n-1\\) Ableitungsschritte, da jeder Ableitungsbaum (bis auf die letzte Ebene) f\u00fcr die Chomsky-Normalform ein Bin\u00e4rbaum ist und wg. \\(n\\) Bl\u00e4ttern genau \\(n-1\\) innere Knoten hat!<\/p>\n

(Weiterhin im Skript wurde die Greifach-Normalform angesprochen. Ebenso eine reduzierte Grammatik. Die reiche ich sp\u00e4ter nach, da sie nicht Teil der Lernziele sind.)<\/p>\n

Antwort zum Lernziel:\u00a0<\/strong>Eine Grammatik ist in Chomsky Normalform wenn\u00a0alle Regeln\/Produktionen die Form \\((A\\rightarrow a)\\) oder\u00a0\\((A\\rightarrow BC)\\) besitzen mit \\(A,B,C\\in\\Pi\\) und \\(a\\in\\Sigma\\) ist. Aus einer beliebigen kontextfreien Grammatik l\u00e4sst sich eine Chomsky Normalform-Grammatik erstellen indem man die \\(\\epsilon\\)– und Kettenregeln eliminiert, die Terminalzeichen separiert und die Nonterminalketten mit mehr als drei Nonterminalen mittels Zwischenregeln auf maximal zwei Nonterminale verk\u00fcrzt.<\/p>\n

 <\/p>\n

Lernziel 2<\/h2>\n

Was besagt das Pumping-Lemma f\u00fcr kontextfreie Sprachen und wie wendet man es an?<\/em><\/p>\n

Wie in dem letzten Beitrag zu KE6<\/a> angedroht, gibt es auch ein Pumping-Lemma f\u00fcr kontextfreie Sprachen. Wir erinnern uns: mit dem Pumping-Lemma k\u00f6nnen wir ein Teilwort \\(v\\), der Zerlegung \\(uvw\\) \u00a0eines Wortes \\(\\omega\\) durch einen Zyklus im endlichen Automaten beliebig aufpumpen. Jedes Wort einer (unendlichen) regul\u00e4ren Sprache verf\u00fcgt ab einer bestimmten Wortl\u00e4nge \u00fcber diese Eigenschaft. Bei endlichen Wortl\u00e4ngen k\u00f6nnen wir es uns einfacher machen, indem wir f\u00fcr jedes Wort einen akzeptierenden Zustand definieren und Zack! ist die Sprache regul\u00e4r. Das ist der Grund warum alle endlichen Sprachen regul\u00e4r sind.<\/p>\n

K\u00fcmmern wir uns nun um das Pumping-Lemma f\u00fcr kontextfreie Sprachen (nicht vergessen: auch regul\u00e4re Sprachen sind kontextfrei, aber nicht alle kontextfreien Sprachen sind regul\u00e4r – regul\u00e4re Sprachen sind eine echte Teilmenge der kontextfreien Sprachen). Ich schreibe die Definition (wieder aus dem Buch von Dirk W. Hoffmann) einfach mal hin und dann schauen wir sie uns genauer an:<\/p>\n

F\u00fcr jede kontextfreie Sprache \\(L\\) existiert ein \\(j\\in\\mathbb{N}\\), so dass sich alle W\u00f6rter \\(\\omega\\in L\\) mit \\(\\mid\\omega\\mid\\geq j\\) in der folgenden Form darstellen lassen:<\/p>\n

\\(\\omega=uvwxy\\) mit \\(\\mid vx\\mid\\geq 1\\) und \\(\\mid vwx\\mid\\leq j\\).<\/p>\n

Mit \\(\\omega\\) ist auch \\(uv^{j}wx^{j}y\\) f\u00fcr alle \\(j\\in\\mathbb{N}_0\\) in \\(L\\) enthalten.<\/p><\/blockquote>\n

Alle W\u00f6rter ab einer gewissen L\u00e4nge \\(j\\) (unsere Pumping Zahl) enthalten Teilw\u00f6rter \\(v\\) und \\(x\\), die sich aufpumpen lassen und eines davon ist nicht leer (\\(\\mid vx\\mid\\geq 1\\)). Seht Ihr den Unterschied zum Pumping Lemma f\u00fcr regul\u00e4re Sprachen<\/a>? Dort haben wir gefordert, dass wir in der Zerlegung \\(uvw\\) nur \\(v\\) beliebig aufpumpen k\u00f6nnen. Hier m\u00fcssen es \\(v\\) und \\(x\\) sein. Das liegt an der evtl. fehlenden rechtslinearen Struktur der Ableitungsb\u00e4ume, die nur regul\u00e4re Sprachen inne haben. Im Beispiel weiter unten wird das gleich deutlicher.<\/p>\n

Achtung<\/strong>: um zu zeigen, dass eine Sprache kontextfrei ist, m\u00fcssen wir nur eine kontextfreie Grammatik die sie erzeugt oder einen Kellerautomaten (kommt im n\u00e4chsten Beitrag) angeben, der sie erkennt. Das Pumping Lemma ist aber dazu gedacht eine Sprache als nicht kontextfrei zu erkennen (was leider auch nicht immer klappt, dazu gleich mehr).<\/p>\n

Erkl\u00e4rung<\/strong><\/p>\n

<\/strong>Wir haben schon massive Vorarbeit geleistet und den Ableitungsbaum einer kontextfreien Sprache in Chomsky-Normalform als bin\u00e4ren Baum entlarvt. Seine Eigenschaften erlauben es uns einige Eigenschaften f\u00fcr ein Wort abzuleiten, dass wir f\u00fcr das Pumping Lemma brauchen. Nehmen wir zun\u00e4chst eine Grammatik \\(G=(\\Pi,\\Sigma,R,S)\\) in Chomsky Normalform. Durch diese Normalform hat der Baum im Inneren die Form eines Bin\u00e4rbaums mit \\(2 ^{\\mid\\Pi\\mid}\\) Bl\u00e4ttern. Wir k\u00f6nnen also einen Pfad w\u00e4hlen, der min. die L\u00e4nge \\(\\mid\\Pi\\mid\\) aufweist. Mit dem Startsymbol zusammen haben wir auf dem Pfad min.\u00a0\\(\\mid\\Pi\\mid +1\\) Nonterminale, so dass eines davon mehrfach aufgetaucht sein muss (erinnert Ihr euch? Unser Zyklus im Automaten!).<\/p>\n

Zur Erinnerung: Das \\(j\\) ist unsere Pumping Zahl. Jeder Ableitungsschritt ist ein durchlaufener Zustand in der Maschine, so dass wir bei einer unendlichen L\u00e4nge an Worten irgendwann durch einen Zyklus bei der Erzeugung eines Wortes laufen m\u00fcssen. Im Ableitungsbaum haben wir somit tats\u00e4chlich mehrmals ein Nonterminal stehen. Nennen wir das Nonterminal einfach mal \\(A\\) und unterteilen das Wort in \\(uvwxy\\).<\/p>\n

Um also aus dem Nonterminal \\(A\\) noch einmal ein \\(A\\) herzustellen, muss min. ein Ableitungsschritt \\(A\\rightarrow BC\\) durchlaufen werden. D.h. eines der Segmente \\(v\\) oder \\(x\\) hat min. ein Terminal drin. Das folgt aufgrund der Regelstruktur in der Chomsky Normalform.<\/p>\n

Wie \\(u\\) oder \\(w\\) aussehen, haben wir keine Ahnung. Macht aber nichts, denn aufgrund dem Doppelvorkommen von \\(A\\) k\u00f6nnen wir die Teilworte \\(v\\) und \\(x\\) aufpumpen und beliebige Worte der Form \\(uv^{i}wx^{i}y\\) erzeugen indem wir die Ableitungssequenz, ausgehend von unserem Nonterminal \\(A\\) mehrfach f\u00fcr das Mittelst\u00fcck wiederholen.<\/p>\n

Dabei wird jedoch nicht nur ein Teil (wie beim Pumping-Lemma f\u00fcr regul\u00e4re Sprachen) wiederholt, sondern zwei.<\/p>\n

Ein Beispiel w\u00e4re wohl sinnig, oder?<\/p>\n

Beispiel<\/strong>: \\(L_1=\\{\\{ab\\}^n\\mid n\\in\\mathbb{N}\\}\\Rightarrow(abababab…)\\)<\/p>\n

Die Sprache besteht aus einer unendlichen Kombination aus \\(ab\\) und ist sogar regul\u00e4r, d.h. wir h\u00e4tten darauf auch das Pumping-Lemma f\u00fcr regul\u00e4re Sprachen anwenden k\u00f6nnen. Da regul\u00e4re Sprachen aber auch kontextfrei sind (und ich zu faul bin mir was neues auszudenken), klappt das Pumping Lemma f\u00fcr kontextfreie Sprachen hier auch.<\/p>\n

Wir suchen also eine Zerlegung \\(uvwxy\\), so dass gilt \\(uv^{i}wx^{i}y\\in L_1\\), mit \\(i\\in\\mathbb{N}_0\\) wobei \\(u\\) und \\(y\\) ruhig leer sein d\u00fcrfen. Au\u00dferdem muss gelten\u00a0\\(\\mid vx\\mid\\geq 1\\) und \\(\\mid vwx\\mid\\leq j\\).<\/p>\n

Dazu brauchen wir unsere Pumping Zahl \\(j\\), die als Mindestl\u00e4nge f\u00fcr das Wort fungiert. Wollen wir einfach mal \\(j=10\\) nehmen. Unser Wort der L\u00e4nge \\(10\\) sieht also wie folgt aus: \\(ababababab\\). Wir zerlegen das willk\u00fcrlich (jede andere Zerlegung, die die Voraussetzungen erf\u00fcllt ist m\u00f6glich) in \\(u=ab,v=ab,w=ab,x=ab,y=ab\\) und pr\u00fcfen ob die oben genannten Voraussetzungen gelten:<\/p>\n

\\(\\mid abab\\mid = 4\\geq 1\\) (passt) und<\/p>\n

\\(\\mid ababab\\mid = 6\\leq 10\\) (passt auch)<\/p>\n

Muss auch nur noch (ich klammere f\u00fcr \u00dcbersichtlichkeit aus)<\/p>\n

\\(\\{ab\\} \\{ab\\}^{i}\\{ab\\}\\{ ab\\}^{i}\\{ab\\}\\in L_1\\) mit \\(i\\in\\mathbb{N}_0\\)<\/p>\n

gelten. Aber das pr\u00fcfen wir zuletzt.<\/p>\n

Eine Regelmenge in Chomsky Normalform, die diese Sprache erzeugt w\u00e4re z.B. die folgende:<\/p>\n

\\(S\\rightarrow\\Pi_a B\\)<\/p>\n

\\(B\\rightarrow\\Pi_b C\\)<\/p>\n

\\(B\\rightarrow C\\)<\/p>\n

\\(C\\rightarrow\\Pi_a B\\)<\/p>\n

\\(\\Pi_a\\rightarrow a\\)<\/p>\n

\\(\\Pi_b\\rightarrow b\\)<\/p>\n

Es ist zwar nicht notwendig sie anzugeben, aber ich w\u00fcrde euch gerne den Ableitungsbaum f\u00fcr das zu zerlegende Wort \\(ababababab\\) zeigen. Das verdeutlicht das Lemma etwas besser.<\/p>\n

\"pumping_2\"<\/a><\/p>\n

Mal nebenbei: aus diesem Grund werden regul\u00e4re Grammatiken auch rechtslineare Grammatiken genannt: der Baum kippt, wie Ihr sehen k\u00f6nnt, nach rechts weg. Das ist der Grund, warum wir im Pumping Lemma f\u00fcr regul\u00e4re Sprachen nicht zwei, sondern nur ein Teilwort aufpumpen m\u00fcssen.<\/p>\n

Es ist leicht einzusehen, dass wir hier bereits ab \\(u\\) einen Zyklus haben, der sich bis \\(y\\) durchzieht. \\(u\\) und \\(y\\) k\u00f6nnten aber auch leer sein, w\u00e4re f\u00fcr unser Lemma egal. Wichtig ist, dass wir \\(v\\) und \\(x\\) wie im Lemma gefordert aufpumpen k\u00f6nnen und das Wort immer noch in \\(L_1\\) liegt.<\/p>\n

Und was w\u00fcrde passieren wenn wir \\(v\\) oder \\(x\\) entfernen (\\(i=0\\)) oder beliebig aufpumpen (\\(i\\geq0\\)) um die letzte Voraussetzung \\(ab ab^{i}ab ab^{i} ab\\in L_1\\) mit \\(i\\in\\mathbb{N}_0\\)\u00a0zu erf\u00fcllen? Probieren wir das mal aus (ich klammere \\(uvwxy\\) der \u00dcbersichtlichkeit halber aus):<\/p>\n

\\(i=0\\Rightarrow\\{ab\\}\\{\\}\\{ab\\}\\{\\}\\{ab\\}\\)<\/p>\n

\\(i=1\\Rightarrow\\{ab\\}\\{ab\\}\\{ab\\}\\{ab\\}\\{ab\\}\\)<\/p>\n

\\(i=2\\Rightarrow\\{ab\\}\\{abab\\}\\{ab\\}\\{abab\\}\\{ab\\}\\)<\/p>\n

\\(…\\)<\/p>\n

Und? Sind die Worte in \\(L_1\\)? Ja, sie sind es. Damit ist die Sprache kontextfrei.<\/p>\n

Wichtig<\/strong>: meine der Faulheit geschuldete Wahl einer regul\u00e4ren Sprache als Beispiel ist aufgrund der rechtslinearen Struktur des Baumes vielleicht nicht optimal gewesen, denn genau das macht – wie eiter oben erw\u00e4hnt – den Unterschied zwischen den beidem Lemmata aus.<\/p>\n

W\u00e4hrend bei einer regul\u00e4ren Sprache der Ableitungsbaum nach rechts kippt und wir nur das \\(v\\), d.h. den rechten Teilbaum in der Zerlegung \\(uvw\\) betrachten m\u00fcssten, so k\u00f6nnte bei einer kontextfreien (aber nicht regul\u00e4ren und damit auch nicht rechtslinearen) Sprache der Ableitungsbaum gleichzeitig nach links und rechts aufspannen. Das ist der Grund, warum wir den Baum nicht in drei, sondern in f\u00fcnf Teile zerlegen (n\u00e4mlich \\(uvwxy\\)) und beide \u00c4ste, links und rechts, mit \\(v\\) und \\(x\\) betrachten m\u00fcssen.<\/p>\n

Denn bei den regul\u00e4ren Sprachen wird mit \\(v\\) nur der rechte Teilbaum aufgepumpt (wir haben ja aufgrund der rechtslinearen Struktur der regul\u00e4ren Sprachen keinen anderen), w\u00e4hrend es bei den kontextfreien (aber nicht unbedingt regul\u00e4ren) Sprachen m\u00f6glich sein muss beide Teilb\u00e4ume \\(v\\) und \\(x\\) verl\u00e4ngern zu k\u00f6nnen. Soweit klar? Evtl. reiche ich ein anderes Beispiel nach um es zu verdeutlichen.<\/p>\n

Lust auf ein Negativbeispiel?<\/p>\n

Beispiel<\/strong>:\u00a0\\(L_2=\\{a^n b^n c^n\\mid n\\in\\mathbb{N}\\}\\Rightarrow(abc,aabbcc,…)\\)<\/p>\n

Auch hier suchen wir einer Zerlegung \\(uvwxy\\) mit den oben genannten Eigenschaften:<\/p>\n

\\(\\mid vx\\mid\\geq 1\\),<\/p>\n

\\(\\mid vwx\\mid\\leq j\\) und<\/p>\n

\\(uv^{i}wx^{i}y\\in L_2\\), mit \\(i\\in\\mathbb{N}_0\\)<\/p>\n

Wir brauchen wieder unsere Pumping Zahl \\(j\\), aber zun\u00e4chst schauen wir uns die Worte doch einmal an f\u00fcr \\(n\\leq3\\):<\/p>\n

\\(n=1\\Rightarrow abc\\)<\/p>\n

\\(n=2\\Rightarrow aabbcc\\)<\/p>\n

\\(n=3\\Rightarrow aaabbbccc\\)<\/p>\n

F\u00e4llt euch schon etwas auf? Versucht doch einmal eine Zerlegung \\(vwx\\) (denn \\(u\\) und \\(y\\) d\u00fcrfen ja ruhig leer sein) z.B. von \\(aaabbbccc\\) mit den oben genannten Kriterien anzugeben. Ich mache einfach mal ein paar Beispielzerlegungen f\u00fcr das Wort der L\u00e4nge \\(6\\), d.h. \\(j=6\\):<\/p>\n

\"zerlegung_1\"<\/a><\/p>\n

W\u00e4hrend Ihr die ersten beiden Kriterien\u00a0\\(\\mid vx\\mid\\geq 1\\) und\u00a0\\(\\mid vwx\\mid\\leq 6\\) noch erf\u00fcllen k\u00f6nnt, sieht es mit\u00a0\\(uv^{i}wx^{i}y\\in L_2\\), mit \\(i\\in\\mathbb{N}_0\\) schon sehr d\u00fcster aus. Versuchen (\\(u\\) und \\(y\\) bleiben einfach mal leer, die sind uns egal. Ich klammere \\(vwx\\) wieder f\u00fcr die \u00dcbersichtlichkeit aus)?<\/p>\n

Zerlegung Nr. 1:<\/strong><\/p>\n

\\(i=0\\Rightarrow\\{u\\}\\{\\}\\{bbb\\}\\{\\}\\{y\\}\\notin L_2\\)<\/p>\n

Bereits mit \\(i=0\\) klappt es nicht. Das erzeugte* Wort ist nicht in unserer untersuchten Sprache. (*was ist das Gegenteil von aufgepumpt? Abgepumpt?)<\/p>\n

\\(i=1\\Rightarrow\\{u\\}\\{aaa\\}\\{bbb\\}\\{ccc\\}\\{y\\}\\in L_2\\)<\/p>\n

Hier geht es noch. Ist aber auch kein Wunder, denn das ist ja unser von Anfang an ausgesuchtes Wort, dass wir zerlegen wollten.<\/p>\n

\\(i=2\\Rightarrow\\{u\\}\\{aaaaaa\\}\\{bbb\\}\\{cccccc\\}\\{y\\}\\notin L_2\\)<\/p>\n

Und ab hier geht es dann nicht mehr weiter. Seht Ihr warum? Wir m\u00fcssen bei der Erh\u00f6hung von \\(i\\) zwei Teile des Wortes verl\u00e4ngern: \\(v\\) und \\(x\\). Dabei bleibt aber ein Teil auf der Strecke, der nicht mit verl\u00e4ngert wird: \\(w\\). Das sind unsere \\(b’s\\). Das ist aber Voraussetzung, denn in der Sprache sind nur Worte, die die gleiche Anzahl \\(a’s\\) wie \\(b’s\\) und \\(c’s\\) haben.<\/p>\n

Zerlegung Nr. 2:<\/strong><\/p>\n

\\(i=0\\Rightarrow\\{u\\}\\{\\}\\{abbb\\}\\{\\}\\{y\\}\\notin L_2\\)<\/p>\n

Auch hier: nix.<\/p>\n

\\(i=1\\Rightarrow\\{u\\}\\{aa\\}\\{abbb\\}\\{ccc\\}\\{y\\}\\in L_2\\)<\/p>\n

Wie gerade eben: unser ausgesuchtes Wort, was nat\u00fcrlich funktioniert.<\/p>\n

\\(i=2\\Rightarrow\\{u\\}\\{aaaa\\}\\{abbb\\}\\{cccccc\\}\\{y\\}\\notin L_2\\)<\/p>\n

Wieder eine unterschiedliche Anzahl an \\(a’s\\), \\(b’s\\) und \\(c’s\\). War also wieder nichts.<\/p>\n

Zerlegung Nr. 3:<\/strong><\/p>\n

\\(i=0\\Rightarrow\\{u\\}\\{\\}\\{bbbc\\}\\{\\}\\{y\\}\\notin L_2\\)<\/p>\n

Nope.<\/p>\n

\\(i=1\\Rightarrow\\{u\\}\\{aaa\\}\\{bbbc\\}\\{cc\\}\\{y\\}\\in L_2\\)<\/p>\n

Erneut: unser ausgesuchtes Wort, was wieder funktioniert.<\/p>\n

\\(i=2\\Rightarrow\\{u\\}\\{aaaaaa\\}\\{bbbc\\}\\{cccc\\}\\{y\\}\\notin L_2\\)<\/p>\n

Auch hier: Wieder eine unterschiedliche Anzahl an \\(a’s\\), \\(b’s\\) und \\(c’s\\). Keine Chance.<\/p>\n

Ich will euch nicht weiter qu\u00e4len: Ihr seht, dass es einfach nicht funktioniert, egal welche Pumping Zahl \\(j\\) und welche Zerlegung wir w\u00e4hlen. W\u00e4hrend wir zwei Teilworte \\(v\\) und \\(x\\) f\u00fcr das Lemma verl\u00e4ngern m\u00fcssen, bleibt eine immer auf der Strecke. D.h. die Zusammensetzung der Elemente ist abh\u00e4ngig von Ihrer Umgebung, ihrem Kontext! Damit ist die Sprache \\(L_2\\) nicht kontextfrei, sondern kontextsensitiv.<\/p>\n

Etwas will ich euch aber nicht vorenthalten: denn das Pumping Lemma funktioniert nicht immer. Es gibt kontextsensitive Sprachen, die das Lemma dennoch erf\u00fcllen! Das Problem liegt in der Startposition der Teilw\u00f6rter der Zerlegung. Denn dazu macht das Lemma keine Aussage (Prefix \\(u\\) und Suffix \\(y\\) k\u00f6nnen ja leer sein). Gelingt es uns den kritischen Abschnitt im Wort (in unserem Beispiel war das \\(w\\)) irgendwie zu umgehen, so haben wir eine evtl. kontextsensitive Sprache, die unser Pumping Lemma trotzdem erf\u00fcllt. Ein Beispiel hierzu ist die\u00a0Sprache:<\/p>\n

\\(L_3=\\{b^k c^l d^m\\mid k,l,m\\in\\mathbb{N}\\}\\cup\\{a^m b^n c^n d^n\\mid m,n\\in\\mathbb{N}\\}\\)<\/p>\n

Hier versagt das Pumping Lemma f\u00fcr kontextfreie Sprachen, den \\(L_3\\) erf\u00fcllt bei einer geschickten Wahl von \\(j\\) und einer Zerlegung \\(uvwxy\\) alle drei Lemma-Kriterien. Ich m\u00f6chte hier nicht n\u00e4her darauf eingehen, da das im Skript nicht behandelt wurde (tue es bei Gelegenheit aber trotzdem wenn etwas Zeit ist). Aber mit Ogdens Lemma<\/a> kann man diese kontextsensitive Sprache auch als eine solche erkennen!<\/p>\n

Antwort zum Lernziel:\u00a0<\/strong>Das Pumping Lemma f\u00fcr kontextfreie Sprachen besagt, dass es bei einem Wort mit Mindestl\u00e4nge \\(j\\) eine Zerlegung \\(uvwxy\\) geben muss, die folgende Kriterien erf\u00fcllt:<\/p>\n

\\(\\mid vx\\mid\\geq 1\\),<\/p>\n

\\(\\mid vwx\\mid\\leq j\\) und<\/p>\n

\\(uv^{i}wx^{i}y\\in L_2\\), mit \\(i\\in\\mathbb{N}_0\\)<\/p>\n

Dabei werden die Teilworte \\(v\\) und \\(x\\) beliebig aufgepumpt. Sollte keine Zerlegung diese Kriterien erf\u00fcllen, so ist die Sprache auch nicht kontextfrei.<\/p>\n

Angewandt wird es, indem man sich zun\u00e4chst ein Wort aus der zu untersuchenden Sprache sucht und eine Zerlegung angibt, welche die oben genannten Kriterien f\u00fcr alle \\(i\\in\\mathbb{N}_0\\) erf\u00fcllt. Liegt das neue Wort mit den aufgepumpten Teilworten \\(v\\) und \\(x\\) dann nicht in der Sprache, zu der das Ursprungswort geh\u00f6rte, so ist die Sprache auch nicht kontextfrei.<\/p>\n

Es gibt jedoch Sprachen, die nicht kontextfrei sind und das Lemma dennoch erf\u00fcllen. Mit Ogdens Lemma kann man diese jedoch als nicht kontextfrei nachweisen.<\/p>\n

Das war Teil 1 von 3 der Kurseinheit 7.<\/p>\n

Bei Fehlern wieder die gro\u00dfe Bitte: ab damit in die Kommentare damit ich das schleunigst berichtigen kann. Vor allem in mathematischen Kursen sind Fehler eine ungemein frustrierende Lernbehinderung, wie ich in Computersysteme 1 und 2 erfahren durfte: da zweifelt man schon tagelang an seinem Rechenweg weil im Skript ein anderes Ergebnis rauskommt. Das ist nervig!<\/p>\n","protected":false},"excerpt":{"rendered":"

Update: Fl\u00fcchtigkeitsfehler rausgenommen. Das ist nun die letzte Kurseinheit der theoretischen Informatik B. Traurig? \ud83d\ude09 In dieser Kurseinheit geht es um kontextfreie Sprachen (also Sprachen, die Typ-2 und -3 erzeugen). Am besten man betrachtet die letzten drei Kurseinheiten gemeinsam, ggf. erstelle ich eine kleine Zusammenfassung der Kernaussagen bei Gelegenheit um aus den Puzzleteilen wenigstens teilweise … <\/p>\n

\u201eTIB: Kontextfreie Sprachen und Kellerautomaten (Lernziele KE7 1\/3)\u201c <\/span>weiterlesen<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-1883","post","type-post","status-publish","format-standard","hentry","category-theoretische-informatik"],"_links":{"self":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1883","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1883"}],"version-history":[{"count":40,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1883\/revisions"}],"predecessor-version":[{"id":3529,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1883\/revisions\/3529"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1883"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1883"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1883"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}