{"id":1759,"date":"2013-06-01T17:58:37","date_gmt":"2013-06-01T15:58:37","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=1759"},"modified":"2025-11-25T23:15:03","modified_gmt":"2025-11-25T22:15:03","slug":"tib-endliche-automaten-und-kontextfreie-grammatiken-lernziele-ke6-23","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=1759","title":{"rendered":"TIB: Endliche Automaten und kontextfreie Grammatiken (Lernziele KE6 2\/3), Update 3"},"content":{"rendered":"

Update 3<\/strong>: Korrektur der Beweisidee f\u00fcr Durchschnitt, nicht Vereinigung. Danke Phil.<\/p>\n

Update 2<\/strong>: Korrektur Aufgabe aus Lernziel 3. Danke Mike.<\/p>\n

Update<\/strong>: Aufgabe mit L\u00f6sung hinzugef\u00fcgt um aus einem Automaten eine Regelmenge abzuleiten.<\/p>\n

Ohne viele Worte: weiter in KE6.<\/p>\n

Lernziel 3<\/h2>\n

Wie konstruiert man zu einem endlichen Automaten \\(A\\) einen regul\u00e4ren Ausdruck \\(\\alpha\\) mit \\(L(A)=L(\\alpha)\\)?<\/em><\/p>\n

Hier kommt einiges an Schreibarbeit auf uns zu. Wie wir aus dem Beitrag zu KE5 wissen, k\u00f6nnen wir regul\u00e4re Sprachen mit einem regul\u00e4ren Ausdruck beschreiben. Um zu beweisen, dass eine Sprache regul\u00e4r ist,\u00a0muss man sie auf eine regul\u00e4re Grammatik, einen endlichen Automaten, einen regul\u00e4ren Ausdruck oder auf bereits bekannte regul\u00e4re Sprachen zur\u00fcckf\u00fchren.<\/p>\n

Hier haben wir einen Automaten \\(A\\) zu einer Sprache \\(L\\) bereits gegeben (die Sprache ist also als regul\u00e4r bewiesen) und suchen nun auch noch einen regul\u00e4ren Ausdruck, der uns dieselbe Sprache beschreibt. Wir verwenden als beispiel wieder den Automaten \\(A\\) aus dem vorherigen Beitrag:<\/p>\n

Beispiel<\/strong>:\u00a0\\(A=(\\{a,b\\},\\{0,1,2\\},0,2,\\delta)\\) mit<\/p>\n

\\(\\delta=\\{(1,a,1),(1,b,1),(1,a,2),(2,b,3),(3,a,3),(3,b,3)\\}\\)<\/p>\n

Hier nochmal der Graph damit Ihr nicht zwischen den Beitr\u00e4gen wechseln m\u00fcsst:<\/p>\n

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

Der Ansatz im Beweis ist ein geringf\u00fcgig anderer, ich will sagen etwas formaler aus die Vorgehensweise, die ich gleich vorstelle. Das Ergebnis ist aber dasselbe. Wenn jemand eine sch\u00f6ne Erkl\u00e4rung f\u00fcr den formalen Beweis im Skript hat, der die folgenden zwei Formeln verwendet, immer her damit.<\/p>\n

\\({L_{ij}}^{0}=\\{a\\in\\Sigma\\mid (i,a,j)\\in\\delta\\}\\)\n\\({L_{ij}}^{k}={L_{ij}}^{k-1}\\cup{L_{ik}}^{k-1}\\cdot({L_{kk}}^{k-1})^*\\cdot{L_{kj}}^{k-1}\\)<\/blockquote>\n

Wir machen das etwas weniger formal. Die Schritte sind wie folgt:<\/p>\n

Wir f\u00fchren einen neuen Startzustand \\(S\\) ein, der mit einem leeren Wort\u00a0\\(\\epsilon\\)\u00a0bereits in unseren ehemaligen Startzustand \u00fcbergeht. Ebenfalls wird ein neuer Endzustand \\(E\\) eingesetzt, zu dem ein Pfeil von jedem ehemaligen Endzustand gezogen wird. Auch hier wird das leere Wort als \u00dcbergang verwendet. Unser neuer Graph sieht wie folgt aus:<\/p>\n

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

Wenn wir uns den \u00dcbergang von Zustand \\(0\\) zu Zustand \\(1\\) anschauen, f\u00e4llt auf, dass wir in jedem Fall ein \\(a\\) als Abschluss der Zeichenkette brauchen um zu Zustand \\(1\\) zu kommen. Beliebig lange Worte, die aus \\(a\\) oder \\(b\\) zusammengesetzt sind, spielen f\u00fcr den \u00dcbergang aufgrund der Schleife im Zustand \\(0\\) keine Rolle solange das \\(a\\) als Suffix im Wort vorhanden ist. Das f\u00fchrt uns auch zu den beiden \u00dcberf\u00fchrungsregeln, die wir brauchen. Ein Bild sagt mehr als tausend Worte:<\/p>\n

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

Klammern wir die Ausdr\u00fccke bei Regel 1, wird es evtl. deutlicher: \\(\\{x\\}\\cdot\\{y\\}^*\\cdot\\{z\\}\\) ist dann der gesuchte, regul\u00e4re Ausdruck um von Zustand \\(A\\) zu Zustand \\(C\\) zu kommen nachdem man Zustand \\(B\\) entfernt hat. Ein Wort, dass den regul\u00e4ren Ausdruck erf\u00fcllen w\u00fcrde, w\u00e4re z.B. \\(xyyyyyyyz\\) oder \\(xz\\). Eines, dass ihn nicht erf\u00fcllt ist \\(xy\\).<\/p>\n

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

Regel 2 ist noch einfacher: Von Zustand \\(A\\) zu Zustand \\(C\\) kommt man durch die Konkatenation von \\(x\\) und \\(z\\). That’s it.<\/p>\n

Das alles angewendet auf unseren Graphen f\u00fchrt uns zu folgendem:<\/p>\n

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

Die leeren Worte \\(\\epsilon\\) brauchen wir nun nicht mehr und k\u00f6nnen sie streichen. Korrekt geklammert haben wir den gesuchten, regul\u00e4ren Ausdruck \\(\\alpha=\\{a,b\\}^{*}\\cdot\\{ab\\}\\cdot\\{a,b\\}^{*}\\) und damit gilt: \\(L(A) = L(\\alpha)\\). Wir k\u00f6nnen auch problemlos eine regul\u00e4re Grammatik \\(G\\) zum Automaten \\(A\\) angeben um \\(L(A) = L(\\alpha) = L(G)\\) zu bekommen. K\u00f6nnt Ihr mal selbst probieren.<\/p>\n

Aufgabe<\/strong>: findet zum Automaten \\(A\\) die Regelmenge der passenden Grammatik<\/p>\n

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

L\u00f6sung zeigen<\/a>\n

<\/strong>Das Vorgehen ist hier ziemlich simpel. Wir k\u00f6nnen die Regeln praktisch direkt ableiten.<\/p>\n

Von Zustand \\(0\\) kommen wir bei der Eingabe von \\(a\\) oder \\(b\\) wieder zu Zustand \\(0\\) und bei der Eingabe von \\(a\\) zu Zustand \\(1\\). Daraus entsteht die folgende Regelmenge:<\/p>\n

\\(0\\rightarrow a0\\mid b0\\mid a1\\)<\/p>\n

Von Zustand \\(1\\) kommen wir durch Eingabe von \\(b\\) zu Zustand \\(2\\):<\/p>\n

\\(1\\rightarrow b2\\)<\/p>\n

Im Zustand \\(2\\) verharren wir dann bei Eingabe von \\(a\\) oder \\(b\\), was uns zur letzten Regel bringt. Hier m\u00fcssen wir aber auch noch aufpassen: da es unser finaler Zustand ist, geh\u00f6rt hier unsere \\(\\epsilon\\)-Regel rein.<\/p>\n

\\(2\\rightarrow a2\\mid b2\\mid\\epsilon\\)<\/p>\n

Jetzt nur noch passend umbennen (Startzustand mit \\(S\\) ausweisen, der Rest bekommt Gro\u00dfbuchstaben):<\/p>\n

\\(S\\rightarrow aS\\mid bS\\mid bA\\)<\/p>\n

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

\\(B\\rightarrow aB\\mid bB\\mid\\epsilon\\)<\/p>\n

Und fertig ist die Laube.<\/p>\n

<\/div>\n<\/p>\n

Lernziel 4<\/h2>\n

Wie zeigt man, dass die regul\u00e4ren Sprache unter den in Satz 8.4.1 genannten Operationen abgeschlossen sind (Beweisidee)?<\/em><\/p>\n

Was waren nochmal die Operationen in Satz 8.4.1? Ach ja:<\/p>\n