{"id":1920,"date":"2013-06-08T16:06:02","date_gmt":"2013-06-08T14:06:02","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=1920"},"modified":"2025-11-25T23:13:41","modified_gmt":"2025-11-25T22:13:41","slug":"tib-kontextfreie-sprachen-und-kellerautomaten-lernziele-ke7-23","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=1920","title":{"rendered":"TIB: Kontextfreie Sprachen und Kellerautomaten (Lernziele KE7 2\/3, Update 2)"},"content":{"rendered":"

Update 2<\/strong>: Einzel- und Mehrschrittrelationen, sowie \u00dcberf\u00fchrungsfunktion genauer erkl\u00e4rt.<\/p>\n

Gro\u00dfes Update: <\/strong>Fehlerbeseitigung und langes Beispiel zum Beweisverfahren Sprache zu Automat(en) zu Grammatik zu Sprache (Lernziel 4).<\/p>\n

Lernziel 3<\/h2>\n

Wie sind Kellerautomaten und die von ihnen akzeptierte Sprache definiert?<\/em><\/p>\n

Noch einmal zur Auffrischung: alle Sprachen, die ein endlicher Automat akzeptiert sind regul\u00e4r. Haben wir aber eine nicht regul\u00e4re Sprache, von was wird sie dann akzeptiert? Ein sch\u00f6nes Beispiel gab es (schon wieder) im Buch von Dirk W. Hoffmann mit der Sprache:<\/p>\n

\\(LC_2=\\{a^n b^n\\mid n\\in\\mathbb{N}\\}\\)<\/p>\n

Wir brauchen also einen Automaten, der unsere Sprache akzeptiert. Mit dem\u00a0Pumping Lemma f\u00fcr regul\u00e4re Sprachen<\/a>\u00a0sehen wir sofort, dass sie nicht regul\u00e4r ist. Auch wenn wir es versuchen, so gelingt es uns nicht einen endlichen Automaten f\u00fcr diese Sprache zu bestimmen. Wir schaffen das immer nur f\u00fcr eine endliche Teilmenge der Sprache (durch akzeptierende Zust\u00e4nde f\u00fcr jedes Wort aus der Sprache) und wir wissen ja, dass jede endliche Sprache auch regul\u00e4r ist weil wir im schlimmsten Fall einfach nur einen akzeptierenden Zustand f\u00fcr jedes Wort bauen m\u00fcssen.\u00a0Zwar ist das bei einer endlichen Teilmenge unserer Sprache \\(LC_2\\) nicht notwendig; der endliche Automat kommt nur mit einem akzeptierenden Zustand aus, das Prinzip sollte aber klar geworden sein. Jeder akzeptierende Zustand fungiert also als eine Art „Speicher“.<\/p>\n

Was m\u00fcssen wir also tun um einen Automaten zu bekommen, der diese Sprache akzeptiert? Wir m\u00fcssen uns irgendwo die Anzahl der \\(a’s\\) merken und sie mit der Anzahl der \\(b’s\\) vergleichen k\u00f6nnen. Wir brauchen also irgendeinen „unendlichen“ Speicher, da wir ja auch etvl. ein unendlich langes Wort haben. Hier helfen uns die Zust\u00e4nde unseres endlichen Automaten nicht weiter, denn er ist… nunja… endlich. \ud83d\ude09<\/p>\n

Wir erweitern unseren endlichen Automaten einfach, so dass wir noch genau die kontextfreien Sprachen mit ihm akzeptieren\/semi-entscheiden k\u00f6nnen.<\/p>\n

W\u00e4hrend in der Literatur h\u00e4ufig mit einem \\(5\\)-Tupel gearbeitet wird, hat das Skript eigene Vorstellungen und verwendet ein \\(7\\)-Tupel zur Definition eines Kellerautomaten. Zus\u00e4tzlich zu den \u00fcblichen Dingen werden auch noch das Kellerstartsymbol \\(\\\\)$ und die Menge der Endzust\u00e4nde \\(Q_f\\) definiert. Ist vielleicht auch gar nicht schlecht, denn die\u00a0Wikipedia<\/a>\u00a0sieht das \u00e4hnlich. Ich echauffiere mich also in den letzten Z\u00fcgen des Skripts nicht \u00fcber dasselbe. \ud83d\ude09 Wollen wir also formal definieren:<\/p>\n

Kellerautomat<\/strong><\/p>\n

\\(A=(\\Sigma,\\Gamma,\\S,Q,q_0,Q_f,\\delta)\\) mit<\/p>\n

\\(\\Sigma\\) endliches Eingabealphabet<\/p>\n

\\(\\Gamma\\) endliches Kelleralphabet<\/p>\n

\\(\\$\\in\\Gamma\\setminus\\Sigma\\) Kellerstartsymbol und Markierung f\u00fcr Eingabeende<\/p>\n

\\(q_0\\in Q\\) als Anfangszustand<\/p>\n

\\(O_f\\subseteq Q\\Sigma\\) Endzust\u00e4nde<\/p>\n

\\(\\delta\\) Zustands\u00fcbergangsfunktion<\/p><\/blockquote>\n

Kommen wir nun zur Zustands\u00fcbergangsfunktion \\(\\delta\\). Ich w\u00fcrde sagen, dass ich ein paar Beispiele gebe anstatt vollst\u00e4ndig formal zu bleiben:<\/p>\n

\\(\\delta(s_0,a,A):=\\{(s_1,B)\\}\\)\n

Im Zustands \\(s_0\\), lese \\(a\\) aus der Eingabe, nimm \\(A\\) vom Kellerstapel, wechsle in den Zustand \\(s_1\\) und schiebe \\(B\\) auf den Kellerstapel.<\/em><\/p>\n\\(\\delta(s_0,b,A):=\\{(s_1,\\epsilon)\\}\\)\n

Im Zustands \\(s_0\\), lese \\(b\\) aus der Eingabe, nimm \\(A\\) vom Kellerstapel, wechsle in den Zustand \\(s_1\\) und lege nichts in den Kellerstapel. Damit wurde das Zeichen \\(A\\) aus dem Keller gel\u00f6scht. Lag \\(A\\) zu diesem Zeitpunkt nicht auf dem Stapel, kann die \u00dcbergangsfunktion nicht angewandt werden.<\/em><\/p>\n\\(\\delta(s_0,\\epsilon,\\epsilon):=\\{(s_0,\\epsilon)\\}\\)\n

Im Zustands <\/em>\\(s_0\\), lese nichts von der Eingabe, nimm nichts vom Kellerstapel, bleibe im Zustand \\(s_0\\) und lege nichts in den Kellerstapel.\u00a0<\/em><\/p><\/blockquote>\n

Mittels \\(\\vdash\\) und \\(\\vdash^n\\) sowie \\(\\vdash^{*}\\) werden die Einzel- und Mehrschrittrelationen bezeichnet.<\/p>\n

\\((s_0,aaaa,AAA)\\vdash(s_1,aaa,AA)\\)\n

Vom Zustands \\(s_0\\) mit dem Wort \\(aaaa\\) auf dem Eingabeband und \\(AAA\\) im Keller, kann man in einem Schritt den Zustand \\(s_1\\) erreichen, wobei dann nur noch \\(aaa\\) auf dem Eingabeband und \\(AA\\) im Keller steht.<\/em><\/p>\n\\((s_0,ababa,AAA)\\vdash^5(s_1,aaaa,AAAA)\\)\n

Vom Zustands \\(s_0\\) mit dem Wort \\(ababa\\) auf dem Eingabeband und \\(AAA\\) im Keller, kann man in \\(5\\) Schritten den Zustand \\(s_1\\) erreichen, wobei dann \\(aaaa\\) auf dem Eingabeband und \\(AAAA\\) im Keller steht.<\/em><\/p>\n\\((s_0,bb,AB)\\vdash^{*}(s_1,\\$,\\$)\\)\n

Vom Zustands \\(s_0\\) mit dem Wort \\(bb\\) auf dem Eingabeband und \\(AB\\) im Keller, hat man nach dem letzten, m\u00f6glichen Berechnungsschritt den Zustand \\(s_1\\) erreicht, wobei dann nichts auf dem Eingabeband und nichts im Keller steht.<\/em><\/p><\/blockquote>\n

Damit sind wir auch schon fast durch. Es gibt jedoch drei Dinge, die noch wichtig\u00a0sind: der Automat hat zwei Wege eine Sprache zu erkennen<\/p>\n

1.\u00a0mittels Endzustand<\/strong>\u00a0(wir landen in einem Endzustand)<\/p>\n

Formal: \\(L(A) =\\{\\omega\\in\\Sigma^{*}\\mid\\exists q\\in Q_f \\exists X\\in\\Gamma^{*} (q_0,\\omega\\$,\\$)\\vdash^{*}(q,\\$,X)\\}\\)<\/p>\n

„F\u00fcr ein Wort \u00fcber dem Alphabet \\(\\Sigma\\)„, ausgehend vom Startzustand \\(q_0\\), w\u00e4hrend wir das Eingabewort und die Markierung f\u00fcr das Eingabeende auf dem Band haben (\\(\\omega\\\\)$) kommen wir nach endlich vielen Schritten zum Endzustand \\(q\\), w\u00e4hrend auf dem Eingabeband der Kopf \u00fcber dem Eingabeende \\(\\\\)$ ist und irgendwas (\\(X\\)) im Keller steht“<\/em><\/p>\n

2.\u00a0mittels leerem Keller<\/strong>\u00a0(wir landen zwar nicht einem Endzustand, aber der Keller ist leer)<\/p>\n

Formal: \\(L(A) =\\{\\omega\\in\\Sigma^{*}\\mid\\exists q\\in Q (q_0,\\omega\\$,\\$)\\vdash^{*}(q,\\$,\\epsilon)\\}\\)<\/p>\n

„F\u00fcr ein Wort \u00fcber dem Alphabet \\(\\Sigma\\)„, ausgehend vom Startzustand \\(q_0\\), w\u00e4hrend wir das Eingabewort und die Markierung f\u00fcr das Eingabeende auf dem Band haben (\\(\\omega\\\\)$) kommen wir nach endlich vielen Schritten zum beliebigen Zustand \\(q\\), w\u00e4hrend auf dem Eingabeband der Kopf \u00fcber dem Eingabeende \\(\\\\)$ ist und der Keller leer ist (\\(\\epsilon\\))“<\/em><\/p><\/blockquote>\n

Und die Definition des\u00a0Determinismus<\/strong>\u00a0einer Kellermaschine:<\/p>\n

Ein Kellerautomat ist\u00a0determiniert<\/strong>, wenn:<\/p>\n

es zu jedem Eingabezeichen und jedem obersten Kellerzeichen maximal ein Zustands\u00fcbergang gibt.<\/p><\/blockquote>\n

Antwort zum Lernziel:\u00a0<\/strong>die Kellerautomaten bestehen aus einem Eingabe- und einem Kelleralphabet, einem Kellersymbol und der Markierung f\u00fcr das Eingabeende sowie Anfangs- und Endzust\u00e4nden und der Zustands\u00fcbergangsfunktion. Die von ihnen akzeptierte Sprache wird definiert als die Worte, die a) den Automaten entweder in einen Endzustand bringen wenn das Ende des Eingabewortes erreicht ist, wobei egal ist, was im Keller steht oder b) der Keller leer ist wenn das Ende des Eingabewortes erreicht ist, wobei es egal ist, in welchem Zustand sich der Automat zu diesem Zeitpunkt befindet.<\/p>\n

Und das sind genau die kontextfreien Sprachen, die die Typ-2-Grammatiken erstellen k\u00f6nnen.\u00a0Wie wir zu einer kontextfreien Grammatik einen Kellerautomaten basteln, zeigen wir im n\u00e4chsten Abschnitt, indem wir die Produktionsregeln der Grammatik in die \u00dcberg\u00e4nge unseres Kellerautomaten codieren.<\/p>\n

Lernziel 4<\/h2>\n

Wie zeigt man, dass Kellerautomaten genau die kontextfreien Sprachen erkennen?<\/em><\/p>\n

Ich w\u00fcrde hier noch ein paar Kleinigkeiten in eure Erinnerung rufen bevor wir mit den Kellerautomaten richtig loslegen. Das liegt u.a. daran, dass wir bei den vorher betrachteten Sprachen eine \u00c4quivalenz zwischen TM und NTM hatten (wir k\u00f6nnen eine NTM durch eine TM simulieren indem wir einfach alle m\u00f6glichen Berechnungspfade der NTM durchlaufen), bei den Kellerautomaten hier aber strikt trennen m\u00fcssen. Nichtdeterministische Kellerautomaten sind eben nicht \u00e4quivalent zu deterministischen. Letztere spielen aber eine gro\u00dfe Rolle, so dass wir noch sp\u00e4ter auf sie zur\u00fcck kommen werden.<\/p>\n

Um also zu zeigen, dass ein Kellerautomat genau die kontextfreien Sprachen erkennt, m\u00fcssen wir zu einer kontextfreien Grammatik \\(G\\) einen Kellerautomaten \u00a0\\(A\\)\u00a0angeben, der mit seinen zwei Akzeptanzmethoden (leerer Keller und Endzustand) ein Wort \\(\\omega\\) genau dann akzeptiert wenn das Wort mittels der kontextfreien Grammatik \\(G\\) abgeleitet werden kann. Es muss also gelten:<\/p>\n

\\(L(G) = L(A)\\)<\/p>\n

Um zu zeigen, dass wir alle kontextfreien Sprachen durch Kellerautomaten erkennen lassen k\u00f6nnen, m\u00fcssen wir das Regelschema der kontextfreien Grammatiken in ein Zustands\u00fcbergangsschema f\u00fcr Kellerautomaten umwandeln. Nur ein Problem haben wir: Die Frage welche Ersetzung (d.h. die R\u00fcckumwandlung der Ableitung) zu machen ist, m\u00fcssen wir beantworten und tun das mit unserem Nichtdeterminismus, indem wir aus mehreren in Frage kommenden Ersetzungen einfach eine raten!<\/p>\n

Ich w\u00fcrde sagen, dass wir auch hier direkt mit einem Beispiel starten und eine kontextfreie Grammatik in einen Kellerautomaten \u00fcberf\u00fchren.<\/p>\n

Grammatik zum Automat mit einem Zustand<\/strong>: kontextfreie Grammatik \\(G_D=\\{\\Sigma,\\Pi,R,S\\}\\) mit den Regeln \\(R\\)<\/p>\n

\\(S\\rightarrow\\epsilon\\mid SS\\mid [S]\\mid(S)\\)<\/p>\n

soll \u00fcberf\u00fchrt werden in einen Kellerautomaten \\(K_{G_D}=(\\Sigma,\\Gamma,S,Q,q_0,Q_f,\\delta)\\), der die gleiche Sprache \\(L(G_D)\\) akzeptiert.<\/p>\n

Ja, das ist die\u00a0Dyck-Sprache<\/a>. Geklaut aus dem Buch von Dirk W. Hoffmann. Sehr einfaches und leicht verst\u00e4ndliches Beispiel. Wie kommen hier mit \u00a0nur einem Zustand aus und k\u00f6nnen den Kellerspeicher so effizient nutzen. Nun m\u00fcssen wir erstmal \\(\\Sigma,\\Gamma,S,Q,q_0,Q_f,\\delta\\) des Automaten festlegen.<\/p>\n

Kelleralphabet<\/span><\/p>\n

\\(\\Gamma=\\Sigma\\cup\\Pi\\) (unser Kelleralphabet besteht also aus Elementen des Terminal- und des Nonterminalalphabets.<\/p>\n

Zust\u00e4nde<\/span><\/p>\n

Die Regel \\(A\\rightarrow\\omega_1,…,\\omega_n\\) wird zu \\(\\delta(s_0,\\epsilon,A):=\\{(s_0,\\epsilon)\\}\\). In unserem Fall sind das:<\/p>\n

\\(\\delta(s_0,\\epsilon,S):=\\{(s_0,\\epsilon)\\}\\)<\/p>\n

\\(\\delta(s_0,\\epsilon,S):=\\{(s_0,SS)\\}\\)<\/p>\n

\\(\\delta(s_0,\\epsilon,S):=\\{(s_0,[S])\\}\\)<\/p>\n

\\(\\delta(s_0,\\epsilon,S):=\\{(s_0,(S))\\}\\)<\/p>\n

Dazu brauchen wir auch noch Regeln f\u00fcr die Terminalzeichen (\\(\\delta(s_0,a,a):=\\{(s_0,\\epsilon)\\}\\)), so dass nur mit der Verarbeitung weitergemacht werden soll wenn das oberste Zeichen im Keller mit dem eingelesenen Zeichen \u00fcbereinstimmt:<\/p>\n

\\(\\delta(s_0,(,():=\\{(s_0,\\epsilon)\\}\\)<\/p>\n

\\(\\delta(s_0,),)):=\\{(s_0,\\epsilon)\\}\\)<\/p>\n

\\(\\delta(s_0,[,[):=\\{(s_0,\\epsilon)\\}\\)<\/p>\n

\\(\\delta(s_0,],]):=\\{(s_0,\\epsilon)\\}\\)<\/p>\n

Zus\u00e4tzlich m\u00fcssen wir das Kellerstartsymbol durch \\(S\\) ersetzen um loszulegen:<\/p>\n

\\(\\delta(s_0,\\epsilon,\\$):=\\{(s_0,S)\\}\\)<\/p>\n

Achtung<\/strong>: wir haben hier ein Beispiel gezeigt, dass die Sprache mittels leerem Keller akzeptiert und nicht mittels Endzust\u00e4nden! Das ist der Automat, der raus kommt (\\(Z\\) ist das Kellerendzeichen und \\(\\lambda\\) ist unser leeres Wort \\(\\epsilon\\), bzw. beliebiges Zeichen):<\/p>\n

\u00a0\"dyck_leer\"<\/a><\/p>\n

Download:\u00a0Dyck-Sprache JFLAP Datei<\/a><\/p>\n

Der Automat ist nichtdeterministisch angelegt, d.h. es existieren mehrere Berechnungspfade f\u00fcr eine Eingabe. Das werdet Ihr sehen wenn Ihr den Automaten laufen lasst. Es geht uns beim Nichtdeterminismus ja nur darum mindestens\u00a0einen<\/strong>\u00a0Berechnungspfad zu haben, der durchl\u00e4uft. Dass andere evtl. scheitern ist uns in diesem Sinne egal. Die Regeln beim Automaten bedeuten folgendes:<\/p>\n

(1) \\(\\lambda,Z,S\\Rightarrow\\)Wenn auf dem Eingabeband ein Zeichen \\(\\lambda\\) (ein Zeichen nicht aus dem Alphabet) steht\u00a0und<\/strong>\u00a0das oberste Zeichen im Keller das Kelleranfangszeichen \\(Z\\) ist, ersetze es im Keller mit \\(S\\).<\/p>\n

(2)\u00a0\\(\\lambda,S,\\lambda\\Rightarrow\\)Wenn auf dem Eingabeband ein Zeichen \\(\\lambda\\)\u00a0und<\/strong>\u00a0im Keller ein \\(S\\) steht, so ersetze \\(S\\) im Keller mit \\(\\lambda\\). Damit ist der Keller leer, es ist unsere „Endbedingung“. Nicht vergessen: der Keller wird erst dann geleert (auf \\(\\lambda\\) gesetzt) wenn wir fertig mit dem Einlesen (es steht \\(\\lambda\\) auf dem Eingabeband)\u00a0und<\/strong>\u00a0am Ende im Keller nur ein \\(S\\) stand, d.h. dass wir einen korrekten Berechnungspfad hatten und damit das Wort richtig abgeleitet wurde.<\/p>\n

(3)\u00a0\\(\\lambda,Z,S\\Rightarrow\\)Wenn auf dem Eingabeband ein Zeichen \\(\\lambda\\) steht\u00a0und<\/strong>\u00a0das oberste Zeichen im Keller das Zeichen \\(S\\) ist, ersetze es im Keller mit \\((S)\\).<\/p>\n

(4)\u00a0\\(\\lambda,Z,S\\Rightarrow\\)Wenn auf dem Eingabeband ein Zeichen \\(\\lambda\\) steht\u00a0und<\/strong>\u00a0das oberste Zeichen im Keller das Zeichen \\(S\\) ist, ersetze es im Keller\u00a0mit \\([S]\\).<\/p>\n

(5) \\(\\lambda,Z,S\\Rightarrow\\)Wenn auf dem Eingabeband ein Zeichen \\(\\lambda\\) steht\u00a0und<\/strong>\u00a0das oberste Zeichen im Keller das Zeichen \\(S\\) ist, ersetze es im Keller\u00a0mit \\(SS\\).<\/p>\n

Sp\u00e4testens jetzt habt Ihr ein Fragezeichen \u00fcber dem Kopf. Oder Ihr nickt. Oder ihr fragt euch, warum ich um den hei\u00dfen Brei herumrede. Habt Ihr gemerkt? Welche Regel von den letzten drei wird nun angewendet wenn\u00a0auf dem Eingabeband das Zeichen eines leeren Wortes \\(\\lambda\\) steht\u00a0und<\/strong>\u00a0das oberste Zeichen im Keller das Zeichen \\(S\\) ist? Wird da nun ein \\((S), [S]\\) oder \\(SS\\) draus? Tja, das genau ist der Nichtdeterminismus. Es kann alles sein. Und wenn wir den falschen Pfad w\u00e4hlen, k\u00f6nnen wir evtl. nie aus der Berechnung raus. Und wisst Ihr was? Es ist uns egal! Hauptsache es existiert ein Pfad, das reicht uns.<\/p>\n

Nun kommen die wichtigsten Regeln:<\/p>\n

(6)\u00a0\\(],],\\lambda\\Rightarrow\\)Wenn auf dem Eingabeband das Zeichen \\(]\\) steht\u00a0und<\/strong>\u00a0das oberste Zeichen im Keller ebenfalls \\(]\\) ist, ersetze es im Keller mit \\(\\lambda\\).<\/p>\n

(7)\u00a0\\([,[,\\lambda\\Rightarrow\\)Wenn auf dem Eingabeband das Zeichen \\([\\) steht\u00a0und<\/strong>\u00a0das oberste Zeichen im Keller ebenfalls \\([\\) ist, ersetze es im Keller mit \\(\\lambda\\).<\/p>\n

(8)\u00a0\\((,(,\\lambda\\Rightarrow\\)Wenn auf dem Eingabeband das Zeichen \\((\\) steht\u00a0und<\/strong>\u00a0das oberste Zeichen im Keller ebenfalls \\((\\) ist, ersetze es im Keller mit \\(\\lambda\\).<\/p>\n

(9)\u00a0\\(),),\\lambda\\Rightarrow\\)Wenn auf dem Eingabeband das Zeichen \\()\\) steht\u00a0und<\/strong>\u00a0das oberste Zeichen im Keller ebenfalls \\()\\) ist, ersetze es im Keller mit \\(\\lambda\\).<\/p>\n

Wir leeren mit diesen Regeln also unseren Keller. Es f\u00e4llt euch wahrscheinlich schwer, zu verstehen was der Automat tut. Ich w\u00fcrde sagen, wir probieren ihn an einem kleinen Beispiel aus.<\/p>\n

Funktionsweise<\/strong>: Wenn wir z.B. den Automaten mit der Eingabe \\(„()“\\) laufen lassen, so passiert folgendes:<\/p>\n

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

Ich habe nicht alle Pfade aufgemalt, sondern nur einen korrekten Pfad bis zum Ende durchgezeichnet. Die mit \\(…\\) beschrifteten Pfade f\u00fchren zu einer weiteren Berechnung (die evtl. auch in einem Ergebnis m\u00fcnden kann). Nach Anwendung der Regel \\(4\\) und \\(2\\) in der zweiten Ableitung gibt es f\u00fcr die Symbolkombination \\(\\lambda,(\\) oder\u00a0\\(\\lambda,\\lambda\\) keinen weiteren \u00dcbergang und wir haben einen undefinierten Automatenzustand.<\/p>\n

Bei den zwei weiteren Pfaden geht es jedoch weiter. Um den Keller zu leeren m\u00fcssen wir als erstes Kellerzeichen und erstes Bandzeichen eines der vier Klammern haben. Da wir immernoch bei \\((\\) als Eingabe sind, m\u00fcssen wir es schaffen auf das Hilfsband eine \u00f6ffnende Klammer \\((\\) zu bekommen, was durch Anwendung der Regel 3 gut funktioniert. Bei den anderen drei Pfaden f\u00fchrt einer wieder in die Sackgasse, da wir keinen Folgezustand f\u00fcr die Symbolkombination \\(\\lambda,[\\) oder \\((,[\\) haben und die beiden anderen zu weiteren Berechnungspfaden.<\/p>\n

Der f\u00fcr uns spannende Pfad wird durch Regel 3 verfolgt: es wird mit Regel 8 anschlie\u00dfend ein Zeichen auf dem Hilfsband gel\u00f6scht und wir lesen das n\u00e4chste Zeichen, unsere schlie\u00dfende Klammer \\()\\) oder \\(\\lambda\\) ein und suchen f\u00fcr die Symbolkombination \\(\\lambda,S\\) oder \\(), S\\) die n\u00e4chsten, passenden Regeln. Es kommen wieder vier Berechnungspfade in Frage, die wir nun nicht weiter verfolgen. Sonst w\u00e4re die Grafik riesig geworden.<\/p>\n

Mit Anwendung der Regel 2 ersetzen wir das \\(S\\) im Keller durch \\(\\lambda\\) und k\u00f6nnen nun die einzig passende Regel \\(9\\) f\u00fcr die Symbolkombination \\(),)\\) anwenden um das n\u00e4chste Zeichen (wir haben keins mehr) auf dem Eingabeband einzulesen und \\()\\) im Keller zu l\u00f6schen.<\/p>\n

F\u00fcr Die Symbolkombination \\(\\lambda,S\\) haben wir wieder vier m\u00f6gliche Regeln, die passen k\u00f6nnten. Aber nur Regel 2 f\u00fchrt uns zu einem leeren Keller beim erreichen des Eingabeendes. Und damit haben wir einen Pfad erfolgreich gefunden.<\/p>\n

Wir haben hier zeigen k\u00f6nnen, dass wir mit nur einem Zustand auskommen. Daher sollte der wichtige Satz<\/p>\n

F\u00fcr jeden Automaten, der eine Sprache \\(L\\) mittels Endzustand akzeptiert, existiert ein Automat, der die \\(L\\) mittels leerem Keller akzeptiert und umgekehrt (Vorsicht: das gilt nicht f\u00fcr deterministische Kellerautomaten!).<\/p><\/blockquote>\n

nicht vergessen werden!<\/p>\n

Wie konstruieren wir denn aus einem Automaten mit mehreren Zust\u00e4nden einen mit nur einem Zustand? Ganz einfach:<\/p>\n

1. Aus dem Automaten mit mehreren Zust\u00e4nden wird eine kontextfreie Grammatik erzeugt (nach\u00a0Rechenberg<\/a>\u00a0ist das immer m\u00f6glich, hat aber keine praktische Bedeutung und wird deshalb in der Literatur ausgelassen. Tats\u00e4chlich habe ich in vier B\u00fcchern, die ich zur Hand habe den Weg anhand eines konkreten Beispiels nicht gefunden. Wer etwas findet, bitte Info an mich. Mit dem JFLOP k\u00f6nnt Ihr einen Automaten in eine Grammatik wandeln, evtl. schreibe ich das Verfahren einfach nochmal hierhin)<\/p>\n

2. Aus der kontextfreien Grammatik wird mit dem oben angegebenen Verfahren ein Automat mit nur einem Zustand erstellt<\/p>\n

That’s it.<\/p>\n

Zusammengefasst: Wir k\u00f6nnen also zu einer kontextfreien Sprache eine kontextfreie Grammatik \\(G\\) angeben. Diese Sprache erkennt auch ein Kellerautomat mittels leerem Keller. Auch ein Automat mit Endzustand tut dies. Wir k\u00f6nnen sogar einen Automaten angeben, der nur mit einem Zustand auskommt, da die M\u00e4chtigkeit des Automaten nur von seinem Keller kommt.<\/p>\n

Noch eine Kleinigkeit, die hier von Bedeutung ist: was ist unter einem\u00a0normalisierten Automaten<\/strong>\u00a0zu verstehen ist? Dieser spielt bei bei der Konvertierung von Automat zu Grammatik eine gro\u00dfe Rolle (hier ist ein gutes\u00a0Dokument<\/a>\u00a0der Fakult\u00e4t f\u00fcr Informatik der Uni Illionois, die etwas mehr Details dazu hat, als ich hier wiedergebe):<\/p>\n

1. Es gibt nur einen akzeptierenden Endzustand<\/strong><\/p>\n

Das tun wir, indem wir einen neuen Endzustand einf\u00fchren und einen \\(\\epsilon\\)-\u00dcbergang von den anderen Zust\u00e4nden dorthin zeichnen<\/p>\n

2. Vor der Akzeptanz wird der Keller geleert<\/strong><\/p>\n

Das kann man tun, indem man vor dem Endzustand in einen Zustand geht und alles bis zum Kellerendzeichen (\\(\\\\)$) aus dem Keller schmei\u00dft.<\/p>\n

3.\u00a0Beim \u00dcbergang wird entweder ein Zeichen aus dem Keller entnommen oder eines hineingelegt, aber nicht beides<\/strong><\/p>\n

Hier gibt es zwei F\u00e4lle: a) \u00dcberg\u00e4nge, die ein Element aus dem Keller nehmen und ein neues hinein legen und b) \u00dcberg\u00e4nge, die nichts tun. Beide k\u00f6nnen wir mit neuen Zust\u00e4nden und \u00dcberg\u00e4ngen simulieren. Fall a) handeln wir ab, indem wir zwei neue Zust\u00e4nde einf\u00fchren: einer entnimmt das Zeichen, geht in einen tempor\u00e4ren (neuen) Folgezustand \u00fcber, dann wird ein Zeichen hineingelegt und der eig. Folgezustand eingenommen. Fall b) behandelt wir noch einfacher: wir basteln uns zwei neue \u00dcberg\u00e4nge. Einer nimmt das Zeichen, geht in den tempor\u00e4ren (neuen) Folgezustand und der n\u00e4chste legt es wieder zur\u00fcck. Fertig.<\/p><\/blockquote>\n

Das war jetzt alles wahrscheinlich bisschen viel und verwirrend. Vielleicht hilft eine kurze \u00dcbersicht des Beweisverfahrens?<\/p>\n

Beweisverfahren<\/strong><\/p>\n

Sprache \\(L\\Rightarrow\\)<\/p>\n

Kellerautomat \\(A\\Rightarrow\\)<\/p>\n

normalisierter Kellerautomat \\(\\overline{A}\\Rightarrow\\)<\/p>\n

Grammatik \\(G\\Rightarrow\\)<\/p>\n

Sprache \\(L\\) und\u00a0Kellerautomat mit nur einem Zustand \\(A^{‚}\\Rightarrow\\).<\/p><\/blockquote>\n

Damit schlie\u00dft sich der Kreis. Wir zeigen der Vollst\u00e4ndigkeit halber im letzten Schritt auch noch, dass wir mit dem oben genannten Verfahren aus der erzeugten Grammatik einen Automaten (nach dem oben gezeigten Verfahren) ableiten k\u00f6nnen, der nur einen einzigen Zustand hat und das Wort mittels leerem Keller akzeptiert.<\/p>\n

Wollen wir den ganzen Spa\u00df noch einmal an der Sprache vom Anfang des Beitrags durchspielen:<\/p>\n

Beispiel<\/strong>:\u00a0\\(LC_2=\\{a^n b^n\\mid n\\in\\mathbb{N}\\}\\)<\/p>\n

Sprache zu Kellerautomat<\/span><\/p>\n

Dieser Automat erkennt die Sprache mit einem leeren Keller.<\/p>\n

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

Kellerautomat zu normalisiertem Kellerautomat<\/span><\/p>\n

Dieser Automat erkennt die Sprache mittels Endzustand. So sieht er aus:<\/p>\n

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

Wie wir sehen, haben wir einfach nur einen neuen Endzustand eingef\u00fchrt. Der folgende Automat erkennt also das Wort in einem Endzustand und hat auch noch einen leeren Keller. Also optimale Bedingungen. Damit ist er soweit normalisiert (bis auf den Punkt mit den \u00dcberf\u00fchrungsbedingungen: die tun immer noch zwei Schritte gleichzeitig (Push und Pop). Da sie uns aber bei der Grammatik nicht st\u00f6ren, war hier etwas faul, sorry!).<\/p>\n

Normalisierter Kellerautomat mit Endzustand zu Grammatik<\/span><\/p>\n

Nun wandeln wir die Zustands\u00fcberg\u00e4nge des Automaten in die Regeln f\u00fcr die Grammatik um. Wir k\u00fcmmern uns zun\u00e4chst um alle Regeln, die etwas aus dem Keller entnehmen (nicht vergessen, im Bild ist \\(\\lambda\\) unser \\(\\epsilon\\))<\/p>\n

1. \\(\\delta(s_i,a,A)=\\{(s_j,\\epsilon)\\}\\Rightarrow s_{i}As_{j}\\rightarrow a\\)<\/p>\n

\\(\\delta(s_0,b,A)=\\{(s_1,\\epsilon)\\}\\Rightarrow s_{0}As_{1}\\rightarrow b\\)<\/p>\n

\\(\\delta(s_1,b,A)=\\{(s_1,\\epsilon)\\}\\Rightarrow s_{1}As_{1}\\rightarrow b\\)<\/p>\n

\\(\\delta(s_1,\\epsilon,Z)=\\{(q_2,\\epsilon)\\}\\Rightarrow s_{1}Zq_{2}\\rightarrow\\epsilon\\)<\/p>\n

Jetzt wird es haariger. Was machen wir mit den verbliebenen Regeln? Problem hierbei: wir nehmen was aus dem Keller und legen gleichzeitig was drauf. Erinnert Ihr euch an die Kriterien f\u00fcr die Normalisierung? Nunja, eine haben wir hier nicht erf\u00fcllt: Nr. 3. Aber das macht erstmal nichts, wir generieren einfach ein paar Regeln mehr nach folgendem Muster:<\/p>\n

2.\u00a0\\(\\delta(s_i,a,A)=\\{(s_j,BC)\\}\\Rightarrow s_{j}As_{x}\\rightarrow a(s_{j}Bs_{y})(s_{y}Cs_{x})\\), wobei \\(s_x\\) und \\(s_y\\) alle Zust\u00e4nde im Automaten sind. Wir m\u00fcssen also alle Zustandskombinationen abgrasen, was uns zur folgenden, langen Liste an Regeln f\u00fchrt:<\/p>\n

Regel<\/strong> \\(a,A;AA\\)<\/p>\n

\\(\\delta(s_0,A,s_0)=\\{(s_0,AA)\\}\\Rightarrow s_{0}As_{0}\\rightarrow{a(s_{0}As_{0})(s_{0}As_{0})}\\)<\/p>\n

\\(\\delta(s_0,A,s_0)=\\{(s_0,AA)\\}\\Rightarrow s_{0}As_{1}\\rightarrow{a(s_{0}As_{0})(s_{0}As_{1})}\\)<\/p>\n

\\(\\delta(s_0,A,s_0)=\\{(s_0,AA)\\}\\Rightarrow s_{0}Aq_{2}\\rightarrow{a(s_{0}As_{0})(s_{0}Aq_{2})}\\)<\/p>\n

\\(\\delta(s_0,A,s_0)=\\{(s_0,AA)\\}\\Rightarrow s_{0}As_{0}\\rightarrow{a(s_{0}As_{1})(s_{1}As_{0})}\\)<\/p>\n

\\(\\delta(s_0,A,s_0)=\\{(s_0,AA)\\}\\Rightarrow s_{0}As_{1}\\rightarrow{a(s_{0}As_{1})(s_{1}As_{1})}\\)<\/p>\n

\\(\\delta(s_0,A,s_0)=\\{(s_0,AA)\\}\\Rightarrow s_{0}Aq_{2}\\rightarrow{a(s_{0}As_{1})(s_{1}Aq_{2})}\\)<\/p>\n

\\(\\delta(s_0,A,s_0)=\\{(s_0,AA)\\}\\Rightarrow s_{0}As_{0}\\rightarrow{a(s_{0}Aq_{2})(q_{2}As_{0})}\\)<\/p>\n

\\(\\delta(s_0,A,s_0)=\\{(s_0,AA)\\}\\Rightarrow s_{0}As_{1}\\rightarrow{a(s_{0}Aq_{2})(q_{2}As_{1})}\\)<\/p>\n

\\(\\delta(s_0,A,s_0)=\\{(s_0,AA)\\}\\Rightarrow s_{0}Aq_{2}\\rightarrow{a(s_{0}Aq_{2})(q_{2}Aq_{2})}\\)<\/p>\n

Regel<\/strong>\u00a0\\(a,Z;AZ\\)<\/p>\n

\\(\\delta(s_0,Z,s_0)=\\{(s_0,AZ)\\}\\Rightarrow s_{0}Zs_{0}\\rightarrow{a(s_{0}As_{0})(s_{0}Zs_{0})}\\)<\/p>\n

\\(\\delta(s_0,Z,s_0)=\\{(s_0,AZ)\\}\\Rightarrow s_{0}Zs_{1}\\rightarrow{a(s_{0}As_{0})(s_{0}Zs_{1})}\\)<\/p>\n

\\(\\delta(s_0,Z,s_0)=\\{(s_0,AZ)\\}\\Rightarrow s_{0}Zq_{2}\\rightarrow{a(s_{0}As_{0})(s_{0}Zq_{2})}\\)<\/p>\n

\\(\\delta(s_0,Z,s_0)=\\{(s_0,AZ)\\}\\Rightarrow s_{0}Zs_{0}\\rightarrow{a(s_{0}As_{1})(s_{1}Zs_{0})}\\)<\/p>\n

\\(\\delta(s_0,Z,s_0)=\\{(s_0,AZ)\\}\\Rightarrow s_{0}Zs_{1}\\rightarrow{a(s_{0}As_{1})(s_{1}Zs_{1})}\\)<\/p>\n

\\(\\delta(s_0,Z,s_0)=\\{(s_0,AZ)\\}\\Rightarrow s_{0}Zq_{2}\\rightarrow{a(s_{0}As_{1})(s_{1}Zq_{2})}\\)<\/p>\n

\\(\\delta(s_0,Z,s_0)=\\{(s_0,AZ)\\}\\Rightarrow s_{0}Zs_{0}\\rightarrow{a(s_{0}Aq_{2})(q_{2}Zs_{0})}\\)<\/p>\n

\\(\\delta(s_0,Z,s_0)=\\{(s_0,AZ)\\}\\Rightarrow s_{0}Zs_{1}\\rightarrow{a(s_{0}Aq_{2})(q_{2}Zs_{1})}\\)<\/p>\n

\\(\\delta(s_0,Z,s_0)=\\{(s_0,AZ)\\}\\Rightarrow s_{0}Zq_{2}\\rightarrow{a(s_{0}Aq_{2})(q_{2}Zq_{2})}\\)<\/p>\n

3. Nun werden die Zustandskombinationen noch umbenannt in \\(A,B,C, …\\), unn\u00f6tiges gestrichen (man kann sich einen Abh\u00e4ngigkeitsgraphen malen um unn\u00f6tige Zust\u00e4nde besser zu identifizieren, wie z.B. in diesem Beitrag<\/a> gezeigt) und der Startzustand \\(S\\rightarrow s_0Zq2\\) hinzugef\u00fcgt. Am Ende haben wir dann die folgenden Regeln f\u00fcr unsere Grammatik:<\/p>\n

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

\\(C\\rightarrow b\\mid aCG\\)<\/p>\n

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

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

\u00a0Wir k\u00f6nnten hier sogar noch \\(G\\) oder \\(C\\) streichen und kommen auf<\/p>\n

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

\\(C\\rightarrow b\\mid aCC\\)<\/p>\n

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

Grammatik zu Kellerautomat mit nur einem Zustand<\/span><\/p>\n

Da wir nun unsere Grammatik haben, k\u00f6nnen wir nach dem Verfahren von oben (erstes Beispiel bei Lernziel 4) uns einen sch\u00f6nen Automaten mit nur einem Zustand basteln, der die Worte unserer Sprache mit leerem Keller akzeptiert. Das sind die Zustands\u00fcberg\u00e4nge, die wir aus der Grammatik ableiten k\u00f6nnen:<\/p>\n

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

\\(\\delta(s_0,\\epsilon,A)=\\{(s_0,aCA)\\}\\)<\/p>\n

\\(C\\rightarrow b\\mid aCC\\)<\/p>\n

\\(\\delta(s_0,\\epsilon,C)=\\{(s_0,b)\\}\\)<\/p>\n

\\(\\delta(s_0,\\epsilon,C)=\\{(s_0,aCC)\\}\\)<\/p>\n

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

\\(\\delta(s_0,\\epsilon,A)=\\{(s_0,\\epsilon)\\}\\)<\/p>\n

Fehlen uns noch die Regeln f\u00fcr die Terminale und die Ersetzung des Kellerzeichens durch erste Ableitung \\(S\\) wenn wir fertig sind:<\/p>\n

\\(\\delta(s_0,a,a)=\\{(s_0,\\epsilon)\\}\\)<\/p>\n

\\(\\delta(s_0,b,b)=\\{(s_0,\\epsilon)\\}\\)<\/p>\n

\\(\\delta(s_0,\\epsilon,Z)=\\{(s_0,S)\\}\\)<\/p>\n

Nachdem wir alles zusammengef\u00fcgt haben, kommt der folgende Automat heraus:<\/p>\n

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

Grammatik zu Sprache<\/span><\/p>\n

Letzter Schritt nochmal aus der Grammatik die ableitbare Sprache zu basteln:<\/p>\n

\\(LC_2=\\{a^n b^n\\mid n\\in\\mathbb{N}\\}\\)<\/p>\n

Damit ist der Kreis geschlossen und wir sind da, wo wir angefangen haben. Und ich hoffe, dass ich mich nirgendwo vertippt habe… \ud83d\ude09<\/p>\n

Antwort zum Lernziel:\u00a0<\/strong>zu jedem nichtdeterministischen Kellerautomat, der eine Sprache mittels Endzustand erkennt kann man einen nichtdeterministischen Kellerautomaten angeben, der dieselbe Sprache mittels leerem Keller (ohne Endzustand) erkennen kann. Und das sogar mit nur einem einzigen Zustand. Das liegt daran, dass die Ausdrucksst\u00e4rke nur vom Keller und nicht von den Zust\u00e4nden des Automaten kommt.<\/p>\n

Dieser Automat kann weiter normiert werden, so dass man beim Erreichen des Endzustands einen leeren Keller hat und die \u00dcberf\u00fchrungsfunktionen entweder etwas auf den Stack legen oder nur etwas wegnehmen. Dazu werden die \u00dcberf\u00fchrungsfunktionen, die diese Kriterien nicht erf\u00fcllen durch neue, tempor\u00e4re Zust\u00e4nde und neue Regeln ersetzt.<\/p>\n

Der normierte Automat l\u00e4sst sich dann einfacher in eine kontextfreie Grammatik umwandeln, das die gleiche Sprache erzeugt wie der normierte Automat. Dazu werden die \u00dcberf\u00fchrungsrelationen des Automaten in Ableitungsregeln f\u00fcr die Grammatik umgewandelt, ein Abh\u00e4ngigkeitsgraph gezeichnet und unn\u00f6tige Zust\u00e4nde und Relationen mit seiner Hilfe gestrichen, so dass sich die Menge der Ableitungen auf ein Minimum verk\u00fcrzt.<\/p>\n

Am Ende hat man eine minimale Grammatik, aus der man zum einen die Sprache ableiten, als auch wieder einen Automaten mit nur einem einzigen Zustand erzeugen kann, der die von der Grammatik erzeugte Sprache mittels leerem Keller akzeptiert.<\/p>\n","protected":false},"excerpt":{"rendered":"

Update 2: Einzel- und Mehrschrittrelationen, sowie \u00dcberf\u00fchrungsfunktion genauer erkl\u00e4rt. Gro\u00dfes Update: Fehlerbeseitigung und langes Beispiel zum Beweisverfahren Sprache zu Automat(en) zu Grammatik zu Sprache (Lernziel 4). Lernziel 3 Wie sind Kellerautomaten und die von ihnen akzeptierte Sprache definiert? Noch einmal zur Auffrischung: alle Sprachen, die ein endlicher Automat akzeptiert sind regul\u00e4r. Haben wir aber eine … <\/p>\n

\u201eTIB: Kontextfreie Sprachen und Kellerautomaten (Lernziele KE7 2\/3, Update 2)\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-1920","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\/1920","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=1920"}],"version-history":[{"count":52,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1920\/revisions"}],"predecessor-version":[{"id":3542,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1920\/revisions\/3542"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1920"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1920"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1920"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}