{"id":2185,"date":"2009-01-13T23:00:48","date_gmt":"2009-01-13T22:00:48","guid":{"rendered":"https:\/\/www.herr-rau.de\/wordpress\/?p=2185"},"modified":"2023-05-10T09:34:27","modified_gmt":"2023-05-10T07:34:27","slug":"formale-sprachen-teil-3-kontextfreie-sprachen","status":"publish","type":"post","link":"https:\/\/www.herr-rau.de\/wordpress\/2009\/01\/formale-sprachen-teil-3-kontextfreie-sprachen.htm","title":{"rendered":"Formale Sprachen, Teil 3: Kontextfreie Sprachen"},"content":{"rendered":"<div style='text-align:right;'><small>(<a href='https:\/\/www.herr-rau.de\/wordpress\/2009\/01\/formale-sprachen-teil-3-kontextfreie-sprachen.htm#comments'>14 Kommentare.<\/a>)<\/small> <\/div>\n<p><em>Das ist die Fortsetzung <a href=\"https:\/\/www.herr-rau.de\/wordpress\/2009\/01\/formale-sprachen-teil-2-regulaere-sprachen.htm\">dieses Eintrags<\/a>. Aber danach gibt es erst mal wieder Blogeintr\u00e4ge, die vielleicht von allgemeinerem Interesse sind, bevor ich mich dann an die richtig schwierigen Sachen wage.<\/em><\/p>\n\n\n\n<p>Nehmen wir als Alphabet wieder nur {a, b}. Aus diesen zwei Zeichen kann man unendlich viele W\u00f6rter kombinieren. Greifen wir eine Teilmenge davon heraus, dann ist das eine Sprache. Die Sprache zum Beispiel, die aus allen W\u00f6rtern besteht, die genau so oft den einen wie den anderen Buchstaben enthalten, ist eine <strong>kontextfreie Sprache<\/strong>, vom Typ Chomsky 2. Sie kann durch eine kontextfreie Grammatik beschrieben werden; ihre W\u00f6rter werden von einem Kellerautomaten akzeptiert. (Mit der regul\u00e4ren Grammatik vom letzten Eintrag kann man diese Sprache nicht beschreiben.)<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">1. Kontextfreie Grammatik<\/h3>\n\n\n\n<p>1. S =&gt; aSB<br>2. S =&gt; bSA<br>3. S =&gt; \u03b5 (das hei\u00dft so viel wie nichts\/null)<br>4. A =&gt; aS<br>5. B =&gt; bS<\/p>\n\n\n\n<p>Diese Grammatik beschreibt die Sprache aller W\u00f6rter \u00fcber {a, b}, in denen beide Buchstaben gleich oft vorkommen, einschlie\u00dflich des leeren Worts.<br>Das Wort <em>ababba<\/em> kann man mit den Regeln so ableiten, fett gedruckt ist jeweils das Nichtterminal, das in der folgenden Zeile ersetzt wird:<\/p>\n\n\n\n<p>Regel 1: S =&gt; aS<strong>B<\/strong><br>Regel 5: =&gt; aSb<strong>S<\/strong><br>Regel 2: =&gt; aSbb<strong>S<\/strong>A<br>Regel 3: =&gt; aSbb<strong>A<\/strong><br>Regel 4: =&gt; aSbba<strong>S<\/strong><br>Regel 3: =&gt; a<strong>S<\/strong>bba<br>Regel 2: =&gt; abS<strong>A<\/strong>bba<br>Regel 4: =&gt; abSa<strong>S<\/strong>bba<br>Regel 3: =&gt; ab<strong>S<\/strong>abba<br>Regel 3: =&gt; ababba<\/p>\n\n\n\n<p>Und fertig. Gibt es eine k\u00fcrzere Ableitung des Wortes? Gibt es eine k\u00fcrzere Grammatik, die dieselbe Sprache beschreibt? Mir gef\u00e4llt dieses \u03b5 nicht, da geh\u00f6rt das leere Wort ja auch zur Sprache; kann ich die Grammatik auch ohne das schreiben? Legitime Fragen, auf die es Antworten gibt.<\/p>\n\n\n\n<p>F\u00fcr eine <em>kontextfreie<\/em> Grammatik gelten folgende Einschr\u00e4nkungen:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Links vom Pfeil steht immer nur genau ein Nichtterminalzeichen. (Im Beispiel: Gro\u00dfbuchstaben.)<\/li>\n\n\n\n<li>Rechts vom Pfeil d\u00fcrfen Terminale und Nichtterminale <em>in beliebiger Folge und Anzahl<\/em> stehen. Au\u00dferdem darf es eventuell noch die Regel S =&gt; \u03b5 geben.<\/li>\n<\/ul>\n\n\n\n<p>Gibt es \u00fcberhaupt Sprachen, bei denen es wichtig ist, dass genau so oft das eine Zeichen auftaucht wie das andere? Aber ja. Stellen wir uns nur die Zeichen &#8222;(&#8220; und &#8222;)&#8220; oder &#8222;{&#8220; &#8222;}&#8220; oder &#8222;if&#8220; und &#8222;endif&#8220; vor &#8211; bei jedem Computerprogramm, bei jedem deutschen Satz, bei dem eine Klammer aufgemacht wird, muss auch wieder eine zugemacht werden. Wenn das brav nacheinander geschieht &#8211; Klammer auf, Klammer zu, Klammer auf, Klammer zu &#8211; dann geht das zur Not auch mit einer regul\u00e4ren Sprache. Aber sobald man verschachteln kann, sobald es Klammern in Klammern gibt, dann braucht man eine kontextfreie Grammatik. Und verschachteln kann man eben auch in nat\u00fcrlicher Sprache, wo eine Nominalphrase als Genitivattribut wieder eine Nominalphrase enthalten kann, die als Pr\u00e4positionalattribut wieder eine Nominalphrase enthalten kann, und so weiter.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">2. Kellerautomat<\/h3>\n\n\n\n<p>&#8222;Keller&#8220; ist die deutsche \u00dcbersetzung des englischen &#8222;stack&#8220;. Man kann auch Stapel dazu sagen. Ein Stapel kann beliebig hoch werden (ein Keller beliebig tief), man kann immer noch etwas drauflegen. Abgebaut wird der Stapel in umgekehrter Reihenfolge. Man kann also nicht unmittelbar auf ein Element mitten im Stapel zugreifen, sondern muss erst das abarbeiten, was dar\u00fcber liegt.<br>Den Kellerautomaten will ich hier nicht beschreiben. Es sei nur gesagt, dass er eben \u00fcber einen Keller\/Stapel\/stack verf\u00fcgt, der beliebig gro\u00df werden kann. Das ist der Hauptunterschied zum endlichen Automaten. Es gibt auch beim Kellerautomaten einen Startzustand und mindestens einen akzeptierenden Zustand, wohl auch mehrere nicht akzeptierende Zust\u00e4nde. Wenn das Wort abgearbeitet ist, bleibt der Automat in einem Zustand stehen. Immer. Bleibt er in einem akzeptierenden Zustand stehen, geh\u00f6rt das Wort zur Sprache, sonst nicht.<\/p>\n\n\n\n<p>(&#8222;Stack&#8220; kennt man auch vom <a href=\"http:\/\/de.wikipedia.org\/wiki\/Puffer%C3%BCberlauf\">&#8222;stack overflow&#8220;<\/a>, einer typischen Sicherheitsl\u00fccke beim Programmieren.)<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">3. Beispiele<\/h3>\n\n\n\n<p><strong>1. Programmiersprachen<\/strong><\/p>\n\n\n\n<p>Alle Programmiersprachen k\u00f6nnen mit einer kontextfreien Grammatik beschrieben werden. Hier ist eine nicht ganz vollst\u00e4ndige Grammatik in der \u00fcbersichtlicheren Backus-Naur-Form, die die Programmiersprache von <a href=\"https:\/\/www.herr-rau.de\/wordpress\/2006\/05\/geheimnisvolle-ruinenstadt-mit-robot-karol.htm\">Robot Karol<\/a> beschreibt. Die Grammatik l\u00e4sst allerdings noch keine selbst definierten Anweisungen und Bedingungen zu, Abs\u00e4tze und Kommentare, die die \u00dcbersichtlichkeit erh\u00f6hen, habe ich ebenfalls weggelassen. Im Prinzip w\u00e4ren das aber jeweils nur wenige Zeilen mehr.<\/p>\n\n\n\n<p><code>&lt;Programm&gt; :: = &lt;Anweisung&gt;<br>\n&lt;Anweisung&gt; ::= &lt;vordefinierte Anweisung&gt; |&lt;Sequenz&gt; | &lt;Entscheidung&gt; | &lt;Wiederholung&gt;<br>\n&lt;vordefinierte Anweisung&gt; ::= \"linksDrehen\" | \"rechtsDrehen\" | \"Schritt\" | \"Hinlegen\" | \"Aufheben\" | \"MarkeSetzen\" | \"MarkeAufheben\"<br>\n&lt;Sequenz&gt; :: = &lt;Anweisung&gt;*<br>\n&lt;Entscheidung&gt; ::= \"wenn\" &lt;Bedingung&gt;  \"dann\" &lt;Anweisung&gt; \"sonst\" &lt;Anweisung&gt; \"*wenn\"<br>\n&lt;Bedingung&gt; ::= \"istWand\" | \"nichtIstWand\"| \"istZiegel\"| \"nichtIstZiegel\" |\"istMarke\" | \"nichtIstMarke\"<br>\n&lt;Wiederholung&gt; ::= &lt;Wiederholung mit Bedingung&gt; | &lt;Wiederholung mit fester Anzahl&gt;<br>\n&lt;Wiederholung mit Bedingung&gt; ::= \"wiederhole solange\" &lt;Bedingung&gt; &lt;Anweisung&gt; \"*wiederhole\"<br>\n&lt;Wiederholung mit fester Anzahl&gt; ::= \"wiederhole\" &lt;Zahl&gt; \"mal\" &lt;Anweisung&gt; \"*wiederhole\"<br>\n&lt;Zahl&gt; ::= &lt;Zahl&gt;<sup>+<\/sup><br>\n&lt;Zahl&gt; ::=  1|2|3|4|5|6|7|8|9|0<br>\n<\/code><\/p>\n\n\n\n<p>Alles in spitzen Klammern ist ein Nichtterminal, &lt;Programm&gt; ist der Startpunkt, alles in Anf\u00fchrungszeichen ist ein Terminal. Wer sich an diese Grammatiken h\u00e4lt, erzeugt immer ein &#8222;Wort&#8220; der Robot-Karol-Sprache &#8211; will hei\u00dfen, immer ein syntaktisch korrektes Robot-Karol-Programme. Ob das Programm auch das tut, was man m\u00f6chte, ist eine andere Frage, ebenso die, ob das Programm zur Laufzeit einen Fehler ergibt, also ob Robot Karol gegen eine Wand l\u00e4uft.<\/p>\n\n\n\n<p><strong>2. Eine Grammatik, angelehnt an die nat\u00fcrliche Sprache<\/strong><\/p>\n\n\n\n<p><code>&lt;Satz&gt; ::= &lt;Nominalphrase&gt; &lt;Verbalphrase&gt;<br>\n&lt;Nominalphrase&gt; ::= &lt;Determiner&gt; &lt;Nomen&gt;<br>\n&lt;Determiner&gt; ::= der | das | die | dieser | dieses | diese | jener | jenes | jene<br>\n&lt;Nomen&gt; ::= Hund | Katze | Maus | Mann | Frau | Kind | Knochen<br>\n&lt;Verbalphrase&gt; ::= &lt;VerbTransitiv&gt; &lt;Nominalphrase&gt;<br>\n&lt;VerbTransitiv&gt; ::= fra\u00df | k\u00fcsste | suchte | fand | warf<\/code><\/p>\n\n\n\n<p>Damit kann man solche &#8222;W\u00f6rter&#8220; (wir nennen sie sonst: S\u00e4tze) ableiten:<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\">                   Satz\n                 \/     \\\n               NP       VP   \n              \/ \\      \/   \\  \n             D   N    V    NP\n          Jene Katze fra\u00df  \/ \\\n                          D   N\n                         die Maus\n<\/pre>\n\n\n\n<p>Warum passt diese Art Grammatik eher zur englischen Sprache? Schon mal, weil &#8222;the&#8220; sich weder durch Numerus, Kasus noch Genus \u00e4ndert, anders als im Deutschen. Damit man also S\u00e4tze verhindert wie: &#8222;Der Katze fra\u00df den Maus&#8220;, muss man die Regeln noch weit verfeinern. Mehr dazu &#8211; aus der sprachwissenschaftlichen, nicht der informatischen Seite &#8211; bei: <a href=\"http:\/\/de.wikipedia.org\/wiki\/Generative_Grammatik\">generative Grammatik<\/a> (Wikipedia).<\/p>\n\n\n\n<p><strong>3. Logische Ausdr\u00fccke<\/strong><\/p>\n\n\n\n<p><code>&lt;wff&gt; ::= p | q | r |s<br>\n&lt;wff&gt; ::= N&lt;wff&gt;<br>\n&lt;wff&gt; ::= K&lt;wff&gt;&lt;wff&gt; | A&lt;wff&gt;&lt;wff&gt; | E&lt;wff&gt;&lt;wff&gt; | C&lt;wff&gt;&lt;wff&gt;<\/code><\/p>\n\n\n\n<p>Mit diesen Regeln kann man Ausdr\u00fccke erzeugen wie {p, q, r, s, Np, Nq, Nr, Ns, Kpp, Kpq, NKpq, KpANpEqq &#8230; } &#8211; und diese Ausdr\u00fccke <a href=\"https:\/\/www.herr-rau.de\/wordpress\/2005\/04\/wff-n-proof.htm\">bedeuten etwas (ich sag nur WFF &#8218;N PROOF)<\/a>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">4. Das Wortproblem f\u00fcr kontextfreie Sprachen<\/h3>\n\n\n\n<p>Das Wortproblem wird sp\u00e4ter noch einmal wichtig. Es lautet: Kann man einen Algorithmus bauen (also zum Beispiel einen solchen Automaten), der f\u00fcr jedes beliebige Wort zu einem gegebenen Alphabet in endlicher Zeit entscheidet, ob das Wort zu einer bestimmten Sprache geh\u00f6rt oder ob es nicht dazu geh\u00f6rt? Ja, man kann. F\u00fcr kontextfreie Sprachen ist das Wortproblem entscheidbar. Nach endlicher Zeit bleibt der Kellerautomat stehen, und zwar entweder in einem akzeptierenden Zustand oder nicht.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">5. Zusammenfassung<\/h3>\n\n\n\n<p>Kontextfreie Sprachen sind wichtig f\u00fcr die Entwicklung und Umsetzung von Programmiersprachen. Auch nat\u00fcrliche Sprachen k\u00f6nnen &#8211; falls \u00fcberhaupt &#8211; mit einer kontexfreien Grammatik beschrieben werden. <em>(Nachtrag. Stimmt so nicht, siehe Kommentar unten.)<\/em> Aber nicht alle Sprachen kann man mit einer kontextfreien Grammatik erzeugen. Das Standardbeispiele ist a<sup>i<\/sup>b<sup>i<\/sup>c<sup>i<\/sup>, also die Sprache aller W\u00f6rter, die aus einer Reihe von a&#8217;s bestehen, gefolgt von ebenso vielen b&#8217;s, gefolgt von ebenso vielen c&#8217;s.<\/p>\n\n\n\n<p><a href=\"https:\/\/www.herr-rau.de\/wordpress\/2009\/02\/formale-sprachen-teil-4-kontextsensitive-sprachen.htm\">Teil 4 folgt nach einer kleinen Pause.<\/a><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/ssl-vg03.met.vgwort.de\/na\/66c80e43b2704e1e8383e85c4d4139fe\" alt=\"\" width=\"1\" height=\"1\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>(14 Kommentare.) Das ist die Fortsetzung dieses Eintrags. Aber danach gibt es erst mal wieder Blogeintr\u00e4ge, die vielleicht von allgemeinerem Interesse sind, bevor ich mich dann an die richtig schwierigen Sachen wage. Nehmen wir als Alphabet wieder nur {a, b}. Aus diesen zwei Zeichen kann man unendlich viele W\u00f6rter kombinieren. Greifen wir eine Teilmenge davon [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[25],"tags":[227],"class_list":["post-2185","post","type-post","status-publish","format-standard","hentry","category-informatik","tag-informatik"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/2185","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/comments?post=2185"}],"version-history":[{"count":3,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/2185\/revisions"}],"predecessor-version":[{"id":56020,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/2185\/revisions\/56020"}],"wp:attachment":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/media?parent=2185"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/categories?post=2185"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/tags?post=2185"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}