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

Update<\/strong>: Fehler im Automaten behoben.<\/p>\n

Letzter Beitrag zum Thema… ich tippe besonders langsam, versprochen \ud83d\ude09<\/p>\n

Lernziel 5<\/span><\/p>\n

Was sind determinierte Kellerautomaten?<\/em><\/p>\n

Wir k\u00f6nnten zwar mit nichtdeterministischen Kellerautomaten leben und w\u00fcrden es sogar. Aber es gibt da ein Problem: wir k\u00f6nnen sie technisch nicht realisieren.<\/p>\n

Den determinierten Kellerautomaten hatten wir im vorherigen Beitrag<\/a> auch bereits definiert.\u00a0Uns interessiert deshalb nicht was<\/em> sie sind, sondern vielmehr wie<\/em> sie sich von nichtdeterministischen Kellerautomaten unterscheiden und was das f\u00fcr Auswirkungen auf die erkannte Sprachklasse hat.<\/p>\n

Eine echte Teilmenge der von nichtdeterminierten Kellerautomaten erkannten, kontextfreien Sprachen ist die deterministische kontextfreie Sprache:<\/p>\n

Deterministisch kontextfrei<\/strong><\/p>\n

Eine Sprache ist deterministisch kontextfrei wenn es einen determinierten Kellerautomaten gibt, der sie erkennt.<\/p><\/blockquote>\n

Das Erkennen<\/strong> bedeutet folgendes:<\/p>\n

Wenn \\(L\\subseteq\\Sigma^{*}\\) eine deterministisch kontextfreie Sprache ist, dann gibt es einen Kellerautomaten \\(A=(\\Sigma,\\Gamma,\\$,Q,q_0,\\{q_{+}\\},\\delta)\\) mit einem Zustand \\(q_{-}\\in Q\\), so dass f\u00fcr alle Worte \\(\\omega\\in\\Sigma\\) gilt:<\/p>\n\\(\\omega\\in L\\Leftrightarrow (q_0,\\omega\\$,\\$)\\vdash^{*}(q_{+},\\$,\\epsilon)\\)\n

Das Wort \\(\\omega\\) ist Teil der deterministisch kontextfreien Sprache wenn es eine \u00dcberf\u00fchrungsfolge im Automaten \\(A\\) gibt, die ausgehend vom Anfangszustand in einen akzeptierenden Endzustand m\u00fcndet und die Eingabe zu Ende gelesen wurde, wobei der Keller leer ist.<\/em><\/p>\n\\(\\omega\\notin L\\Leftrightarrow (q_0,\\omega\\$,\\$)\\vdash^{*}(q_{-},\\$,\\epsilon)\\)\n

Das Wort \\(\\omega\\) ist nicht Teil der deterministisch kontextfreien Sprache wenn es eine \u00dcberf\u00fchrungsfolge im Automaten \\(A\\) gibt, die ausgehend vom Anfangszustand in einen nicht-akzeptierenden Endzustand m\u00fcndet und die Eingabe zu Ende gelesen wurde, wobei der Keller leer ist.<\/em><\/p><\/blockquote>\n

Sie ist zudem auch noch eindeutig:<\/p>\n

Jede deterministisch erkannte Sprache ist eindeutig*.<\/p><\/blockquote>\n

* erinnert Ihr euch noch an die Eindeutigkeit? Fall nicht: jedes abgeleitete Wort einer eindeutigen Sprache\/Grammatik hat nur einen einzigen Ableitungsbaum.<\/p>\n

Wir zeigen gleich, dass die deterministischen Automaten weniger leistungsf\u00e4hig sind. Folgende \u00dcberlegungen sind notwendig:<\/p>\n

1. ein deterministischer Kellerautomat akzeptiert nur Worte, die er zu Ende liest. Wir m\u00fcssen daher unseren deterministischen Automaten entsprechen ummodellieren und die Szenarien vermeiden, wo der Automat nicht weiterlesen kann:<\/p>\n

a) Keller leer bevor Eingabe zu Ende.<\/p>\n

L\u00f6sung<\/strong>: neues Keller-Leerheits-Zeichen, dass nie gel\u00f6scht wird.<\/p>\n

b) keine Folgekonfiguration f\u00fcr aktuelle Konfiguration vorhanden<\/p>\n

L\u00f6sung<\/strong>: Vervollst\u00e4ndigen von \\(\\delta\\), so dass wir zu jeder M\u00f6glichkeit einen Folgezustand haben<\/p>\n

c) das Erreichen eines Zyklus, wo der Kopf nicht bewegt wird<\/p>\n

L\u00f6sung<\/strong>: Erkennen und vermeiden des Zyklus.<\/p>\n

2. Wir haben einen ausgezeichneten, positiven Endzustand: entweder er akzeptiert das Wort und wir landen in \\(q_{+}\\) oder nicht und wir landen in\u00a0\\(q_{-}\\in Q\\).<\/p>\n

Mit der Vorarbeit aus dem letzten Beitrag, ist es nicht schwer diese weiteren Einschr\u00e4nkungen nachzuvollziehen.<\/p>\n

Der Beweis f\u00fcr die Komplementbildung<\/strong> gelingt durch simples Vertauschen der Zust\u00e4nde\u00a0\\(q_{+}\\) und\u00a0\\(q_{-}\\), so dass wir diese Eigenschaft zusammenfasen k\u00f6nnen:<\/p>\n

Sei \\(L\\subseteq\\Sigma^{*}\\) deterministisch kontextfrei, so ist es auch \\(\\Sigma^{*}\\setminus L\\).<\/p><\/blockquote>\n

Antwort zum Lernziel:\u00a0<\/strong>Kellerautomaten (PDAs) sind endliche Automaten, die durch einen Kellerspeicher erweitert wurden. Bei einem Kellerautomaten wird ein Wort dann erkannt wenn der Keller leer ist oder der Automat in einem Endzustand landet (oder beides gleichzeitig).<\/p>\n

F\u00fcr einen determinierten Kellerautomaten gilt zudem, dass es f\u00fcr jedes Eingabezeichen und jedes oberste Kellerzeichen nur einen Zustands\u00fcbergang gibt, so dass der Kellerautomat den Berechnungsweg nicht zuf\u00e4llig w\u00e4hlen kann. Ist das nicht der Fall und gibt es zu einem Eingabezeichen und einem obersten Kellerzeichen mehrere m\u00f6gliche Folgezust\u00e4nde, so ist der Kellerautomat nichtdeterministisch.<\/p>\n

F\u00fcr eine deterministisch kontextfreie Sprache \\(L\\) bedeutet es, dass wir in jedem Fall f\u00fcr ein Wort \\(\\omega\\in L\\) nach endlich vielen Schritten die Endkonfiguration \\((q_{+},\\$,\\epsilon)\\) (ausgewiesener Endzustand, Ende der Eingabe, leerer Keller) oder f\u00fcr ein Wort\u00a0\\(\\omega\\notin L\\)\u00a0\\((q_{-},\\$,\\epsilon)\\)\u00a0(beliebiger Zustand aus \\(Q\\), Ende der Eingabe, leerer Keller)\u00a0erreichen.<\/p>\n

 <\/p>\n

Lernziel 6<\/h2>\n

Ist jede kontextfreie Sprache deterministisch? Mit Begr\u00fcndung!<\/em><\/p>\n

Ein (f\u00fcr mich) etwas verst\u00e4ndlicheres Beispiel habe ich in den Folien der HU-Berlin<\/a> gefunden und w\u00fcrde das hier gerne anbringen. Nehmen wir zwei deterministisch kontextfreie Sprachen (DCFL), die von einem determinierten Automaten erkannt wird, z.B.<\/p>\n

\\(L_1=\\{a^i b^j c^k\\mid i\\neq j\\}\\in DCFL\\) sowie<\/p>\n

\\(L_2=\\{a^i b^j c^k\\mid j\\neq k\\}\\in DCFL\\).<\/p>\n

Beide Sprachen sind deterministisch kontextfrei. Wir k\u00f6nnen also einen deterministischen Kellerautomaten angeben, der sie erkennt.<\/p>\n

Um \\(L_1\\) zu entscheiden, k\u00f6nnen wir uns z.B. darauf beschr\u00e4nken die \\(a’s\\) einzulesen, \\(A’s\\) in den Keller zu schreiben und anschlie\u00dfend die \\(b’s\\) einzulesen und die \\(A’s\\) aus dem Keller zu entfernen. Es sind drei F\u00e4lle zu unterscheiden:<\/p>\n

1. Gab es weniger \\(a’s\\) als \\(b’s\\), so haben wir noch \\(b’s\\) auf dem Eingabeband, w\u00e4hrend der Keller bereits leer ist und alles ist gut.<\/p>\n

2. Gab es mehr \\(a’s\\) als \\(b’s\\), so haben wir keine \\(b’s\\) auf dem Eingabeband, w\u00e4hrend noch \\(A’s\\) im Keller sind und alles ist immernoch gut.<\/p>\n

3. Gab es die gleiche Anzahl \\(a’s\\) und \\(b’s\\), so haben wir einen leeren Keller just in dem Moment, wo wir keine \\(b’s\\) auf dem Eingabeband haben und das Wort wird abgelehnt.<\/p>\n

Das gleiche Verfahren klappt auch mit \\(L_2\\) (nur mit \\(b’s\\) und \\(c’s\\) statt mit \\(a’s\\) und \\(b’s\\)).<\/p>\n

Schauen wir uns doch eine weitere Sprache an:<\/p>\n

\\(L_1\\cup L_2 = \\{a^i b^j c^k\\mid i\\neq j\\) oder \\(j\\neq k\\}\\in CFL\\setminus DCFL\\).<\/p>\n

Wie man sieht, ist das eine Vereinigung der beiden Sprachen \\(L_1\\) und \\(L_2\\). Um das etwas anschaulicher zu machen, schauen wir uns die Mengen doch einmal mit \\(1\\leq i,j,k\\leq 2\\) an:<\/p>\n

\\(L2_1=\\{abbc,abbcc,aabc,aabcc\\}\\)<\/p>\n

\\(L2_2=\\{abcc,abbc,aabcc,aabbc\\}\\)<\/p>\n

\\(L2_1\\cup L2_2 = \\{abbc,abbcc,aabc,aabcc,abcc,aabbc\\}\\)<\/p>\n

W\u00e4hrend wir f\u00fcr f\u00fcr \\(L2_1, L2_2\\) und die Vereinigung der beiden Sprachen \\(L2_1\\cup L2_2\\) sogar einen endlichen Automaten angeben k\u00f6nnen, der sie erkennt (wir erinnern uns: das ist genau der Grund warum alle endlichen Sprachen sogar regul\u00e4r sind, ein akzeptierender Zustand pro Wort reicht im endlichen Automaten aus um die Sprachen zu erkennen), gelingt es uns bei \\(i,i,k\\in\\mathbb{N}\\) nur f\u00fcr \\(L_1\\) sowie \\(L_2\\) einen Kellerautomaten anzugeben, der die Sprache erkennt (wir m\u00fcssen die Anzahl der Buchstaben beobachen k\u00f6nnen und k\u00f6nnen das nur mindestens mit einem Kellerautomaten. Mindestens weil Turingmaschinen als st\u00e4rkstes Berechnungsmodell selbstverst\u00e4ndlich auch gehen, denn sie k\u00f6nnen ja selbst Typ-0-Sprachen erkennen).<\/p>\n

Weit mehr Probleme macht uns die Vereinigung! Das Problem mit ihr ist: sie ist zwar kontextfrei, aber nicht deterministisch kontextfrei. Denn daf\u00fcr k\u00f6nnen wir keine deterministische Kellermaschine angeben, sie sie erkennt.<\/p>\n

Woran liegt das? Wie wir oben gesehen haben, beobachten wir mit dem Keller nur eine Variable (die Anzahl unserer ersten, eingelesenen Buchstaben) und k\u00f6nnen so eine andere abh\u00e4ngig von dieser entscheiden. Das ist bei den Sprachen \\(L_1\\) und \\(L_2\\) ja kein Problem. Bei \\(L_1\\cup L_2\\) haben wir jedoch drei Variablen, die von einander abh\u00e4ngig sind. Denn wir m\u00fcssen \\(j\\) in Abh\u00e4ngigkeit von \\(i\\) und \\(k\\) in Abh\u00e4ngigkeit von \\(j\\) pr\u00fcfen. Das war’s also mit dem Determinismus, denn wir haben mehrere Wege, die wir beschreiten m\u00fcssen um am Ende einen zu finden, der funktioniert.<\/p>\n

Die kontextfreie Grammatik<\/a> f\u00fcr\u00a0\\(L_1\\cup L_2\\) ist:<\/p>\n

\\(S\\rightarrow{DC \\mid AE \\mid B}\\)<\/p>\n\\(D\\rightarrow{F\\mid G}\\)\n\\(F\\rightarrow{aF \\mid aFb \\mid a}\\)\n\\(G\\rightarrow{Gb \\mid aGb\\mid b}\\)\n\\(C\\rightarrow{cC\\mid\\epsilon}\\)\n

\\(A\\rightarrow{aA\\mid\\epsilon}\\)<\/p>\n\\(E\\rightarrow{H\\mid I}\\)\n\\(H\\rightarrow{bH\\mid bHc\\mid b}\\)\n\\(I\\rightarrow{Ic \\mid bIc \\mid c}\\)\n

\\(B\\rightarrow{J \\mid K}\\)<\/p>\n\\(J\\rightarrow{aJ\\mid aJc\\mid aL}\\)\n\\(K\\rightarrow{Kc\\mid aKc\\mid Lc}\\)\n\\(L\\rightarrow{bL\\mid\\epsilon}\\)\n

Und daraus k\u00f6nnen wir den zugeh\u00f6rigen Automaten nach dem Schema aus dem vorherigen Beitrag<\/a> bauen:<\/p>\n

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

Download: AiBjCk_NPDA_JFLAP-Datei<\/a><\/p>\n

<\/a><\/p>\n

Damit haben wir auch eine wesentliche Aussage f\u00fcr das n\u00e4chste Lernziel herausgearbeitet: dass wir keinen deterministischen Automaten f\u00fcr \\(L_1\\cup L_2\\) angeben k\u00f6nnen liegt daran, das\u00a0die deterministisch kontextfreien Sprachen zwar abgeschlossen sind bzgl. Schnitt und Komplement, aber nicht<\/strong> gegen Vereinigung, Durchschnitt, Spiegelung und Konkatenation! Und das obere Beispiel war die Vereinigung. Beispiele f\u00fcr Durchschnitt, Spiegelung und Konkatenation \u00fcberlasse ich erstmal euch \ud83d\ude09<\/p>\n

Zusammengefasst: Wir haben mit dem deterministischen Kellerautomaten, welche die Sprache erkennt, tats\u00e4chlich eine Beschneidung der M\u00f6glichkeiten, die uns ein nichtdeterministischer Kellerautomat bietet: wir k\u00f6nnen nicht mehr zwischen Berechnungspfaden w\u00e4hlen\u00a0und sind an unsere Wahl „gebunden“. War sie falsch, so landen wir in einer Sackgasse und damit war es das. Bei einem nichtdeterministischen Automaten haben wir w\u00e4hrenddessen (durch mehrere Folgekonfigurationen f\u00fcr eine Konfiguration) bereits andere Wege parallel beschritten, wo uns einer (wenn wir einen korrekten Automaten angegeben haben) schon zur L\u00f6sung f\u00fchren wird. War eine Berechnung falsch, so landen wir auf diesem einen Weg in einer Sackgasse und … es ist uns egal. Wir haben ja noch genug andere Wege, die wir parallel beschreiten.<\/p>\n

Hauptsache wir k\u00f6nnen beweisen, dass min. einer dieser Wege zu einem Ergebnis f\u00fchrt und entscheidet ob ein Wort sich in der Sprache befindet. Tut es das nicht, kann der nichtdeterministische Automat von uns aus solange weiterrechnen, bis er schwarz wird.<\/p>\n

Ein Blick aus einer anderen Brille: Um bei der Sprache \\(L_1\\cup L_2\\) entscheiden zu k\u00f6nnen ob ein Wort tats\u00e4chlich zur Sprache geh\u00f6rt oder nicht, ist der Algorithmus wirklich einfach: Wir z\u00e4hlen die \\(a’s\\), \\(b’s\\) und \\(c’s\\), speichern die Anzahl auf dem Hilfsband und vergleichen die drei Variablen nachdem wir die Eingabe vollst\u00e4ndig eingelesen haben miteinander. Ihr habt sicher schon eine TM im Kopf, die das macht. W\u00e4hrend wir das also mit einer DTM problemlos machen k\u00f6nnen, schaffen wir das mit einem PDA durch die Einschr\u00e4nkungen leider nicht.<\/p>\n

Antwort zum Lernziel<\/strong>: Nicht jede kontextfreie Sprache ist deterministisch. Es gibt kontextfreie Sprachen, die aufgrund ihrer Struktur nicht von einem PDA erkannt werden k\u00f6nnen weil ihr Aufbau von mehreren Variablen abh\u00e4ngt, diese jedoch nicht durch einen einzigen Kellerspeicher deterministisch abgebildet werden k\u00f6nnen. Erst durch das Beschreiten mehrerer Berechnungspfade ist es m\u00f6glich auch mehrere Variablen in die Betrachtung einzubeziehen und aus der so generierten Vielzahl an Pfaden die Aussage zu treffen, dass einer in jedem Fall zum Ziel f\u00fchrt wenn das Wort sich in der Sprache befindet.<\/p>\n

Eine solche kontextfreie, aber nicht deterministische Sprache l\u00e4sst sich durch Vereinigung, Konkatenation, Durchschnitt oder Spiegelung einer oder mit mehreren deterministisch kontextfreien Sprachen erzeugen, da die Sprachklasse der deterministisch kontextfreien Sprachen nicht abgeschlossen gegen diese Operationen ist.<\/p>\n

Lernziel 7<\/h2>\n

Sind die kontextfreien bzw. deterministisch kontextfreien Sprachen abgeschlossen unter Vereinigung, Durchschnitt, Komplement und Schnitt mit regul\u00e4ren Mengen?<\/em><\/p>\n

Was soll ich hier schreiben? Reicht die Tabelle aus dem Skript? \ud83d\ude09 Ihr solltet euch noch einmal vor Augen f\u00fchren, wie die Sprachklassen zusammenh\u00e4ngen und die Beziehungen zwischen Unter- und Oberklasse sind. Dann wird euch auch deutlich warum diese gegen gewisse Operationen nicht abgeschlossen sein k\u00f6nnen. Vielleicht schreibe ich sp\u00e4ter noch ein paar S\u00e4tze dazu, aber bis dahin:<\/p>\n

Antwort zum Lernziel:<\/strong><\/p>\n\n<\/colgroup>\n<\/colgroup>\n<\/colgroup>\n\n\n\n\n\n\n\n\n
<\/td>\nkontextfrei<\/b><\/td>\ndeterministisch<\/b><\/td>\n<\/tr>\n
Vereinigung<\/td>\n+<\/td>\n–<\/td>\n<\/tr>\n
Durchschnitt<\/td>\n–<\/td>\n–<\/td>\n<\/tr>\n
Komplement<\/td>\n–<\/td>\n+<\/td>\n<\/tr>\n
Konkatenation<\/td>\n+<\/td>\n–<\/td>\n<\/tr>\n
Stern<\/td>\n+<\/td>\n–<\/td>\n<\/tr>\n
Schnitt mit regul\u00e4ren Mengen<\/td>\n+<\/td>\n+<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Lernziel 8<\/h2>\n

Welche der folgenden Probleme sind f\u00fcr kontextfreie Grammatiken entscheidbar\/unentscheidbar? Wortproblem, Endlichkeitsproblem, Leerheitsproblem?<\/em><\/p>\n

Hier sollten wir einige Probleme auf den Mengen entscheiden k\u00f6nnen, diese sind:<\/p>\n