{"id":1720,"date":"2013-05-27T11:12:19","date_gmt":"2013-05-27T09:12:19","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=1720"},"modified":"2025-11-25T23:15:40","modified_gmt":"2025-11-25T22:15:40","slug":"tib-endliche-automaten-und-kontextfreie-grammatiken-lernziele-ke6-13","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=1720","title":{"rendered":"TIB: Endliche Automaten und kontextfreie Grammatiken (Lernziele KE6 1\/3)"},"content":{"rendered":"

Vorletzte Kurseinheit. Und dazu noch ein eig. sehr sch\u00f6nes Thema. Die letzte KE und diese hier geh\u00f6ren ganz eng zusammen; ich k\u00e4mpfe noch mit mir nicht einen einzigen Eintrag aus beiden Kurseinheiten zu gie\u00dfen. Ich empfehle euch beide in einem Tab\/Fenster aufzumachen damit Ihr beide Eintr\u00e4ge vor der Nase habt und zwischen ihnen bl\u00e4ttern k\u00f6nnt wenn in diesem Eintrag auf S\u00e4tze aus KE5 Bezug genommen wird.<\/p>\n

Leider sind die letzten Kurseinheiten etwas dicker \ud83d\ude09 K\u00e4mpfen wir uns also wieder direkt durch die Lernziele.<\/p>\n

Lernziel 1<\/h2>\n

Wie definiert man die von einem endlichen Automaten erkannte Sprache?<\/em><\/p>\n

In dieser Kurseinheit sind Turingmaschinen mit einem Einweg-Ausgabeband ohne Arbeitsb\u00e4nder im Fokus. Auch wenn man sie als Turingmaschinen notieren kann, wird eine andere Notation verwendet. Die der endlichen Automaten. Starten wir mit der Definition und einem Beispiel:<\/p>\n

Endlicher (nichtdeterministischer) Automat<\/p>\n

Quintupel \\(A=(\\Sigma,Q,q_0,F,\\delta)\\) mit<\/p>\n

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

\\(Q\\) als endliche Menge der Zust\u00e4nde<\/p>\n

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

\\(F\\subseteq Q\\) als Menge der Endzust\u00e4nde<\/p>\n

\\(\\delta\\subseteq Q\\times\\Sigma\\times Q\\) als \u00dcberf\u00fchrungsrelation<\/p><\/blockquote>\n

Dieser Teil der Definition macht euch sicher kaum Probleme, haben wir doch bereits Turingmaschinen in \u00e4hnlicher Weise definiert. Die \u00dcberf\u00fchrungsrelation f\u00fchrt einfach nur von einem Zustand aus \\(Q\\)\u00a0zu einem anderen Zustand aus \\(Q\\)\u00a0bei der Eingabe von einem Element aus dem Eingabealphabet \\(\\Sigma\\).<\/p>\n

Nun definieren wir noch \\(\\delta\\):<\/p>\n

\\(\\delta^0=\\{(q,\\epsilon,q)\\mid q\\in{Q}\\}\\)\n\\(\\delta^{n+1}=\\{(p,xa,q)\\mid x\\in{\\Sigma}^{*},a\\in{\\Sigma},\\exists r\\in{Q}.(p,x,r)\\in\\delta^{n}\\wedge(r,a,q)\\in\\delta\\}\\)\n

\\(\\delta^{*} = \\bigcup_{n\\geq 0}\\delta^n\\) ist die transitive H\u00fclle<\/a> von \\(\\delta\\)<\/p><\/blockquote>\n

Oha. Die induktive Definition der \u00dcberf\u00fchrungsrelation ist nicht so einfach. Aber warten wir das folgende Beispiel gleich ab, dann wird es klarer. In der transitiven H\u00fclle sind auch indirekte Relationen drin, d.h. erreichen wir z.B. den Zustand \\(q_2\\) bei der Eingabe von \\(a\\) nur \u00fcber \\(q_1\\) ausgehend vom Startzustand \\(q_0\\), so h\u00e4tten wir eig. nur die Relationen \\((q_0,a,q_1)\\) und \\((q_1,a,q_2)\\). In der transitiven H\u00fclle \\(\\delta^{*}\\) haben wir jedoch auch noch das indirekte Tripel \\((q_0,a,q_2)\\) drin.<\/p>\n

Diese Tripel in \\(\\delta^{*}\\) k\u00f6nnen nicht nur einzelne Zeichen aus \\(\\Sigma\\) beinhalten, sondern k\u00f6nnen der Definition nach auch Worte sein. F\u00fchrt uns z.B. die Eingabe \\(aaabbb\\) zu einem Endzustand, so ist in der transitiven H\u00fclle\u00a0\\(\\delta^{*}\\) auch \\((q_0,aaabbb,q)\\) drin (wobei \\(q_0\\) ein Anfangs- und \\(q\\) ein Endzustand ist). Wird gleich im folgenden beispiel etwas verst\u00e4ndlicher, versprochen.<\/p>\n

Kommen wir nun zur akzeptierten Sprache \\(L(A)\\):<\/p>\n

\\(L(A):=\\{x\\in\\Sigma^{*}\\mid\\exists q\\in F.(q_0,x,q)\\in\\delta^{*}\\}\\)\n\\(L(A):=\\{x\\in\\Sigma^{*}\\mid\\delta^{*}\\cap(\\{q_0\\}\\times\\{x\\}\\times F)\\neq\\emptyset\\}\\)<\/blockquote>\n

Es gilt also \\(x\\in L(A)\\) genau dann wenn \\(x\\) den Anfangszustand in einen Endzustand \u00fcberf\u00fchrt. Damit ist genau das die von dem endlichen Automaten \\(A\\) erkannte Sprache \\(L(A)\\). Nun k\u00fcmmern wir uns um die Worte determiniert<\/em> und vollst\u00e4ndig<\/em>.<\/p>\n

determiniert<\/strong>, gdw. \\(\\#\\{q\\in Q\\mid(p,a,q)\\in\\delta\\}\\leq 1\\) f\u00fcr alle \\(p\\in Q,a\\in\\Sigma\\)<\/p>\n

vollst\u00e4ndig<\/strong>, gdw. \\(\\#\\{q\\in Q\\mid(p,a,q)\\in\\delta\\}\\geq 1\\) f\u00fcr alle \\(p\\in Q,a\\in\\Sigma\\)<\/p><\/blockquote>\n

Gar nicht so schwer: determiniert bedeutet, dass wir ausgehend vom Startzustand \\(q_0\\) das Wort \\(x\\) von links nach rechts ableiten und immer einen<\/strong> Folgezustand haben. Wenn es mal keinen Folgezustand gibt, so ist der Automat nicht vollst\u00e4ndig und es gilt \\(x\\notin L(A)\\). Gibt es einen Zustand \\(p_n\\) f\u00fcr die Eingabe \\(x\\), wobei \\(n=lg(x)\\) (L\u00e4nge von \\(x\\)), so gilt: \\(x\\in L(A)\\Leftrightarrow p_n\\in F\\). D.h. soviel wie wenn die L\u00e4nge von \\(x\\) \\(n\\) ist, so muss nach \\(n\\) Schritten der Endzustand \\(p_n\\) erreicht worden sein. Damit ist dann auch \\(x\\in L(A)\\). Landet man nach \\(n\\) Berechnungsschritten nicht im Endzustand, so ist \\(x\\notin L(A)\\).<\/p>\n

Nichtdeterminierte Automaten sind – genauso wie \\(NTM\\) – reine Gedankenmodelle. Hierzu gibt es ein Beispiel im Skript, dass ich auch gerne anf\u00fchren w\u00fcrde:<\/p>\n

Beispiel<\/strong>: \\(A=(\\Sigma,Q,q_0,F,\\delta)\\) mit<\/p>\n

\\(\\Sigma=\\{a,b\\}\\) (Eingabealphabet)<\/p>\n

\\(Q=\\{0,1,2\\}\\) (Zust\u00e4nde)<\/p>\n

\\(q_0=0\\) (Startzustand)<\/p>\n

\\(F=\\{2\\}\\) (Endzustand)<\/p>\n

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

Wir zeichnen die Zust\u00e4nde als Kreise, weisen Start- und Endzustand entsprechend aus und jeder \u00dcbergang von einem Zustand zum anderen wird eine gerichtete und gekennzeichnete Kante zwischen diesen. Gibt es bereits einen \u00dcbergang, so m\u00fcssen wir die Kante mit dem zus\u00e4tzlichen Zeichen nur noch kennzeichnen.<\/p>\n

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

Dieser ist nicht determiniert<\/strong>. Warum? Weil es f\u00fcr f\u00fcr eine Eingabe und einen Zustand zwei Folgezust\u00e4nde gibt: \\((0,a,1)\\) und \\((0,a,0)\\).<\/p>\n

Auch ist er nicht vollst\u00e4ndig<\/strong>: Warum? Weil wir im Zustand \\(1\\) f\u00fcr die Eingabe \\(a\\) keinen Folgezustand haben.<\/p>\n

Wie sieht unsere transitive H\u00fclle \\(\\delta^{*}\\) aus? Sie hat z.B. auch noch zus\u00e4tzlich das indirekten Tripel \\((0,b,2)\\) drin. Und was ist mit dem \\(\\delta^n\\)? Dazu kommen wir auch gleich. Ersteinmal stellen wir uns die Frage:\u00a0Welche Sprache entscheidet der Automat?<\/p>\n

Zun\u00e4chst einmal k\u00f6nnen wir eine absolut beliebige Kombination aus \\(a\\) und \\(b\\) haben und verweilen im Zustand \\(0\\): \\({\\{a,b\\}}^{*}\\). Erst wenn wir zum Zustand \\(2\\) wollen, ben\u00f6tigen wir als Abschluss des ersten Teils der Zeichenkette ein \\(\\{ab\\}\\). Und dort angekommen sind wir entweder fertig oder k\u00f6nnen im Zustand \\(2\\) so verweilen, wie wir auch in Zustand \\(0\\) verweilt haben: mit einer beliebigen Kombination aus \\(1\\) und \\(b\\): \\({\\{a,b\\}}^{*}\\).<\/p>\n

Damit ist die von \\(A\\) erkannte Sprache \\(L\\), d.h. \\(L(A)={\\{a,b\\}}^{*}\\{ab\\}{\\{a,b\\}}^{*}\\)<\/p>\n

Und nun k\u00fcmmern wir uns um \\(\\delta^n\\) am versprochenen Beispiel (ebenfalls aus dem Skript geklaut).<\/p>\n

Beispiel<\/strong>\u00a0\\(a^4b^2\\in L(A)\\)?<\/p>\n

Wir m\u00fcssen also schauen ob die Eingabe \\(x=aaaabb\\) uns zu einem Endzustand (ein Zustand aus \\(F\\)) bringt oder nicht. In jedem Schritt bringt uns ein Zeichen aus dem Wort zu einem Folgezustand. Und wenn es mal keinen gibt oder wir nach \\(lg(x)=6\\) Schritten noch keinen Endzustand erreicht haben, so ist das Wort nicht Teil unserer Sprache \\(L(A)\\). Versuchen wir es also:<\/p>\n

\u00a0\\((0,\\epsilon,0)\\in\\delta^0\\)<\/p>\n

\u00a0\\((0,a,0)\\in\\delta^1\\)\u00a0da\u00a0\\((0,a,0)\\in\\delta\\)<\/p>\n

\\((0,aa,0)\\in\\delta^2\\) da\u00a0\\((0,a,0)\\in\\delta\\)<\/p>\n

\\((0,aaaa,0)\\in\\delta^3\\)\u00a0da\u00a0\\((0,a,0)\\in\\delta\\)<\/p>\n

\\((0,aaaaa,1)\\in\\delta^4\\)\u00a0da\u00a0\\((0,a,1)\\in\\delta\\)<\/p>\n

\\((0,aaaab,2)\\in\\delta^5\\)\u00a0da\u00a0\\((1,b,2)\\in\\delta\\)<\/p>\n

\\((0,aaaabb,2)\\in\\delta^6\\)\u00a0da\u00a0\\((2,b,2)\\in\\delta\\)<\/p>\n

Wir sehen also, dass wir Ausgehend vom Startzustand \\(0\\) zum Zustand \\(2\\) gelangen, welcher ein Endzustand ist. Es liegt daher \\((0,aaaabb,2)\\in\\delta^{*}\\), woraus folgt, dass\u00a0\\(a^4b^2\\in L(A)\\)! Um zu zeigen, dass ein Wort zur Sprache geh\u00f6rt, m\u00fcssen wir also einfach nur eine Zustandsfolge angeben, die die zu pr\u00fcfende Eingabe in den Endzustand \u00fcberf\u00fchrt. Braucht Ihr noch ein Beispiel um zu zeigen, dass eine Zeichenfolge nicht in \\(L(A)\\) ist? Gerne.<\/p>\n

Beispiel<\/strong>:\u00a0\\(a^4\\in L(A)\\)?<\/p>\n

Spielen wir den Graphen mit der Eingabe \\(aaaa\\) durch, so sehen wir, dass wir nie in im Endzustand \\(2\\) landen. Wir bleiben immer nur in \\(0\\) oder \\(1\\). Damit ist\u00a0\\(a^4\\notin L(A)\\)? Probiert die n\u00e4chsten beiden mal selbst.<\/p>\n

\u00dcbung<\/strong>:\u00a0\\(a^2 b^2\\in L(A)\\) \\((aabb)\\)?<\/p>\n

L\u00f6sung zeigen<\/a>\n

Zustandsfolge: \\(0\\xrightarrow{\\text{a}}0\\xrightarrow{\\text{a}}1\\xrightarrow{\\text{b}}2\\xrightarrow{\\text{b}}2\\), es gilt:\u00a0\\(a^2 b^2\\in L(A)\\)<\/div>\n<\/p>\n

\u00dcbung<\/strong>:\u00a0\\((ba)^3\\in L(A)\\) \\((bababa)\\)?<\/p>\n

L\u00f6sung zeigen<\/a>\n

Zustandsfolge: \\(0\\xrightarrow{\\text{b}}0\\xrightarrow{\\text{a}}0\\xrightarrow{\\text{b}}0\\xrightarrow{\\text{a}}1\\xrightarrow{\\text{b}}2\\xrightarrow{\\text{a}}2\\), es gilt:\u00a0\\((ba)^3\\in L(A)\\)<\/div>\n<\/p>\n

\u00dcbung<\/strong>:\u00a0\\((ba)\\in L(A)\\) \\((ba)\\)?<\/p>\n

L\u00f6sung zeigen<\/a>\n

Zustandsfolgen:<\/p>\n

\\(0\\xrightarrow{\\text{b}}0\\xrightarrow{\\text{a}}0\\) oder<\/p>\n

\\(0\\xrightarrow{\\text{b}}0\\xrightarrow{\\text{a}}1\\).<\/p>\n

Wir kommen also nie in einen Endzustand \\(2\\), damit gilt:\u00a0\\((ba)\\notin L(A)\\)<\/div>\n<\/p>\n

Antwort zum Lernziel<\/strong>: Damit ist die von einem endlichen Automaten \\(A\\) erkannte Sprache \\(L\\) die Menge der Worte \u00fcber dem Alphabet \\(\\Sigma\\), die ausgehend von einem Startzustand \\(q_0\\) den Automaten in einen Endzustand \\(q\\) \u00fcberf\u00fchrt und dabei nicht mehr Berechnungsschritte braucht als die Eingabe lang ist.<\/p>\n

Lernziel 2<\/h2>\n

Wie kann man zu einem nichtdeterminierten endlichen Automaten einen determinierten konstruieren, der dieselbe Sprache erkennt?<\/em><\/p>\n

Im Beitrag zu KE5 haben wir es bereits angedeutet: die Regeln aus den Grammatiken sind nichts weiter als \u00dcberf\u00fchrungsrelationen in Maschinen von einem Zustand zum anderen. Aus diesem Grund k\u00f6nnen wir rechtslineare Normalformgrammatiken in Automaten \u00fcberf\u00fchren. Dazu brauchen wir folgendes:<\/p>\n

Transformation \\(T\\) mit \\(T((\\Pi,\\Sigma,R,S)):=(\\Sigma,\\Pi,S,F,\\delta)\\) mit<\/p>\n

\\(F=\\{A\\in\\Pi\\mid (A\\rightarrow\\epsilon)\\in R\\}\\) und<\/p>\n\\(\\delta=\\{(A,a,B)\\in\\Pi\\times\\Sigma\\times\\Pi\\mid (A\\rightarrow aB)\\in R\\}\\)<\/blockquote>\n

Wir transformieren damit eine rechtslineare Normalformgrammatik in einen Automaten, so dass \\(L(G)=L(T(G))\\) gilt. Die Definition von \\(F\\) (unseren Endzust\u00e4nden im Automaten) besagt lediglich, dass in die Menge der Endzust\u00e4nde unseres Automaten das Nonterminal reingeh\u00f6rt. was auch als Regel f\u00fcr ein Nonterminal in den Regeln der Grammatik vorhanden ist und auf \\(\\epsilon\\) zeigt.<\/p>\n

Mit \\(\\delta\\) ist es \u00e4hnlich. In die \u00dcberf\u00fchrungsrelationen geh\u00f6ren alle Regeln rein, die auf ein Terminal (unsere Eingabe im Automaten) und ein Nonterminal (unser Zustand im Automaten) zeigen. Das ist dann unser Zustands\u00fcbergang.\u00a0Am besten ein Beispiel, oder? Nehmen wir dazu doch einfach die Grammatik, die wir im vorherigen Beitrag verwendet haben.<\/p>\n

Beispiel<\/strong>:\u00a0\\(G_1=(\\Pi,\\Sigma,R,S)\\) mit \\(\\Pi=\\{S,B,C\\}\\), \\(\\Sigma=\\{a,b\\}\\), Startsymbol \\(S\\) und den Regeln \\(R\\):<\/p>\n

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

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

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

Wir m\u00fcssen also aus der rechtslinearen Normalformgrammatik \\(G_1\\) einen endlichen Automaten basteln. Weder am Alphabet \\(\\Sigma\\), noch an den Zust\u00e4nden (Nonterminalen) \\(\\Pi\\) oder am Startzustand \\(S\\) haben wir was zu kamellen. Wir brauchen die Menge der Endzust\u00e4nde \\(F\\) und unsere \u00dcberf\u00fchrungsrelationen \\(\\delta\\).<\/p>\n

Fangen wir mit dem Endzustand<\/strong> \\(F\\) an. Schaut noch einmal die Definition von \\(F\\) oben an. Wir suchen also in den Regeln \\(R\\) unserer Grammatik \\(G_1\\) nach der Regel von der Form \\((A\\rightarrow\\epsilon)\\). Die einzige Regel, die so aussieht ist die Regel f\u00fcr\u00a0\\(C\\rightarrow\\epsilon\\mid aB\\). Damit haben wir den Endzustand der Grammatik \\(C\\) nun in unserer Automaten-Menge \\(F\\). H\u00e4tten wir mehr Regeln, die auf ein \\(\\epsilon\\) zeigen, so h\u00e4tten wir auch mehr Endzust\u00e4nde.<\/p>\n

Jetzt die \u00dcberf\u00fchrungsrelationen<\/strong> \\(\\delta\\): wir transformieren alle Regeln der Grammatik mit der Form \\((A\\rightarrow aB)\\) in die \u00dcberf\u00fchrungsrelation f\u00fcr dem Automaten mit der Form \\((A,a,B)\\):<\/p>\n

\\(S\\rightarrow aB\\Rightarrow(S,a,B)\\)<\/p>\n

\\(B\\rightarrow bC\\Rightarrow(B,b,C)\\)<\/p>\n

\\(C\\rightarrow aB\\Rightarrow(C,a,B)\\)<\/p>\n

That’s it. Wie sieht der Automat nun aus? So:<\/p>\n

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

Fertig! Wir sehen auch hier, dass er nicht vollst\u00e4ndig<\/strong> ist: es fehlt im Zustand \\(S\\) der Folgezustand f\u00fcr die Eingabe eines \\(b\\). Aber er ist determiniert<\/strong>, da wir nicht mehrere Folgezust\u00e4nde f\u00fcr eine Eingabe haben.<\/p>\n

Nachdem das nun gekl\u00e4rt ist, k\u00fcmmern wir uns um die \u00dcberf\u00fchrung von nichtdeterminierten Automaten in determinierte. Der Vorteil von letzteren liegt darin, dass diese sich mittels Boole’schen Schaltwerken realisieren lassen. W\u00e4re doch sch\u00f6n wenn wir dazu die nichtdeterminierten Automaten in determinierte \u00fcberf\u00fchren k\u00f6nnten…<\/p>\n

Beispiel<\/strong>: der Automat aus dem ersten Beispiel mit\u00a0\\(A=(\\Sigma,Q,q_0,F,\\delta)\\) mit<\/p>\n

\\(\\Sigma=\\{a,b\\}\\) (Eingabealphabet)<\/p>\n

\\(Q=\\{0,1,2\\}\\) (Zust\u00e4nde)<\/p>\n

\\(q_0=0\\) (Startzustand)<\/p>\n

\\(F=\\{2\\}\\) (Endzustand)<\/p>\n

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

und dem zugeh\u00f6rogen Graphen<\/p>\n

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

Die Menge der neuen Zust\u00e4nde ist maximal \\(2^Q = 2^3 = 8\\). Wobei wir nicht alle ben\u00f6tigen werden. Dazu stellen wir eine Tabelle auf, die uns am Ende zeigt welche \u00dcberg\u00e4nge und welche Zust\u00e4nde wir haben.\u00a0Wir fangen einfach mal an, die Inhalte der Spalten erschlie\u00dfen sich dann direkt:<\/p>\n\n\n\n\n\n<\/colgroup>\n\n\n\n\n
V<\/b><\/td>\nW<\/b><\/td>\nW\\V<\/b><\/td>\n<\/tr>\n
P<\/td>\na<\/td>\nb<\/td>\n<\/td>\n<\/tr>\n
{0}<\/td>\n{0,1}<\/td>\n{0}<\/td>\n{0,1}<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

In der ersten Zeile, in Spalte \\(P\\) steht der Startzustand. In Spalte \\(a\\) und \\(b\\) stehen die jeweils erreichbaren Zust\u00e4nde bei der jeweiligen Eingabe, ausgehend vom Zustand in Spalte \\(P\\). D.h. ausgehend von Startzustand \\(0\\) erreichen wir bei der Eingabe von \\(a\\) Folgezustand \\(0\\) und \\(1\\) und bei der Eingabe von \\(b\\) nur Zustand \\(0\\).\u00a0In der Spalte \\(W\\setminus{V}\\) befindet sich die Elemente der Menge \\(W=\\{\\{0,1\\},\\{0\\}\\}\\) ohne die Elemente der Menge \\(V=\\{\\{0\\}\\}\\), also nur\u00a0\\(W\\setminus{V}=\\{\\{0,1\\}\\}\\). Damit haben wir die erste Zeile aufgebaut.<\/p>\n

F\u00fcr die Spalte \\(P\\) in der zweite Zeile nehmen wir ein Element aus der Menge\u00a0\\(W\\setminus{V}=\\{\\{0,1\\}\\}\\). Viel Auswahl haben wir hier nicht (h\u00e4tten wir eine, so w\u00e4re die Auswahl willk\u00fcrlich, sie w\u00fcrde nur die Reihenfolge der Zeilen beeinflussen). Nun werden wieder die erreichbaren Folgezust\u00e4nde, ausgehend von Startzustand \\(0\\) und \\(1\\) bei der Eingabe von \\(a\\) und \\(b\\) in den folgenden Spalten notiert und in der letzten Spalte wieder\u00a0\\(W\\setminus{V}\\) eingetragen. Das machen wir solange, bis die Menge\u00a0\\(W\\setminus{V}\\) leer (\\(W\\setminus{V}=\\emptyset\\)) ist. Am Ende haben wir die folgende Tabelle:<\/p>\n\n\n\n\n\n<\/colgroup>\n\n\n\n\n\n\n\n
V<\/b><\/td>\nW<\/b><\/td>\nW\\V<\/b><\/td>\n<\/tr>\n
P<\/td>\na<\/td>\nb<\/td>\n<\/td>\n<\/tr>\n
{0}<\/td>\n{0,1}<\/td>\n{0}<\/td>\n{0,1}<\/td>\n<\/tr>\n
{0,1}<\/td>\n{0,1}<\/td>\n{0,2}<\/td>\n{0,2}<\/td>\n<\/tr>\n
{0,2}<\/td>\n{0,1,2}<\/td>\n{0,2}<\/td>\n{0,1,2}<\/td>\n<\/tr>\n
{0,1,2}<\/td>\n{0,1,2}<\/td>\n{0,2}<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Aus dieser k\u00f6nnen wir nun alle notwendigen Zust\u00e4nde (Spalte \\(P\\)) und die Folgezust\u00e4nde (Spalten \\(a\\) und \\(b\\)) ableiten. Alle Zust\u00e4nde aus Spalte \\(P\\), die die Zahl eines Endzustandes (\\(2\\)) des urspr\u00fcnglichen Automaten beinhalten, werden ebenfalls zu Endzust\u00e4nden.\u00a0Am Ende kommt daher folgender Graph raus:<\/p>\n

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

Wenn wir die Wertetabelle dazu aufstellen sehen wir auch, dass wir einen Zustand wegk\u00fcrzen k\u00f6nnen (wie in Computersysteme 1 und 2).<\/p>\n

 <\/p>\n\n\n\n\n<\/colgroup>\n\n\n\n\n\n\n
Zustand<\/b><\/td>\nFolgezustand bei Eingabe von \u201ea\u201c<\/b><\/td>\nFolgezustand bei Eingabe von \u201eb\u201c<\/b><\/td>\n<\/tr>\n
0<\/td>\n01<\/td>\n0<\/td>\n<\/tr>\n
01<\/td>\n01<\/td>\n02<\/td>\n<\/tr>\n
02<\/td>\n012<\/td>\n02<\/td>\n<\/tr>\n
012<\/td>\n012<\/td>\n02<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Zustand \\(02\\) und \\(012\\) sind \u00e4quivalent und damit k\u00fcrzbar (wenn man zur \\(b\\)-Kante von \\(02\\) noch \\(a\\) hinzuf\u00fcgt).<\/p>\n

Antwort zum Lernziel<\/strong>: zu einem nichtdeterminierten Automaten kann man einen determinierten Automaten konstruieren, der dieselbe Sprache erkennt, indem man eine neue Zustandsmenge definiert, die maximal aus der Potenzmenge \\(2^Q\\) der urspr\u00fcnglichen Zust\u00e4nde \\(Q\\) f\u00fchrt. Die Menge der ben\u00f6tigten Zust\u00e4nde ergibt sich aus allen erreichbaren Zust\u00e4nden.<\/p>\n

Diese neuen Automaten werden\u00a0Potenzautomaten<\/strong>\u00a0genannt. Damit l\u00e4sst sich festhalten, dass man zu jedem endlichen, nicht-deterministischen Automaten einen deterministischen Automaten angeben kann, der die selbe Sprache erkennt.<\/p>\n

Da die Namen der neuen Zust\u00e4nde aus den Namen der Ursprungszust\u00e4nde bestehen, k\u00f6nnen die gerichteten Kanten auch zu den neuen Zust\u00e4nden problemlos gezogen und so die Zustands\u00fcberg\u00e4nge im neuen Graphen modelliert werden. Durch die Benennung lassen sich auch die Endzust\u00e4nde im neuen, deterministischen Graphen identifizieren: jeder neue Zustand, der in seinem neuen Namen den Namen eines urspr\u00fcnglichen Endzustands beinhaltet, wird ebenfalls ein Endzustand.<\/p>\n

Das war der erste Teil von KE6. Wer Fehler findet: ab in die Kommentare.<\/p>\n","protected":false},"excerpt":{"rendered":"

Vorletzte Kurseinheit. Und dazu noch ein eig. sehr sch\u00f6nes Thema. Die letzte KE und diese hier geh\u00f6ren ganz eng zusammen; ich k\u00e4mpfe noch mit mir nicht einen einzigen Eintrag aus beiden Kurseinheiten zu gie\u00dfen. Ich empfehle euch beide in einem Tab\/Fenster aufzumachen damit Ihr beide Eintr\u00e4ge vor der Nase habt und zwischen ihnen bl\u00e4ttern k\u00f6nnt … <\/p>\n

\u201eTIB: Endliche Automaten und kontextfreie Grammatiken (Lernziele KE6 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-1720","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\/1720","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=1720"}],"version-history":[{"count":38,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1720\/revisions"}],"predecessor-version":[{"id":3545,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1720\/revisions\/3545"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1720"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1720"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1720"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}