{"id":1667,"date":"2013-05-23T17:32:17","date_gmt":"2013-05-23T15:32:17","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=1667"},"modified":"2025-11-25T23:06:07","modified_gmt":"2025-11-25T22:06:07","slug":"tib-grammatiken-und-regulare-sprachen-lernziele-ke5","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=1667","title":{"rendered":"TIB: Grammatiken und regul\u00e4re Sprachen (Lernziele KE5, Update 6)"},"content":{"rendered":"<p><strong>Update 2<\/strong>: Markus hat\u00a0eine Ungenauigkeit im Lernziel 8 gefunden. Ist korrigiert,\u00a0Danke.<\/p>\n<p><strong>Update<\/strong>: Beispiel f\u00fcr die regul\u00e4ren Ausdr\u00fccke, sowie Gleichungen f\u00fcr die Funktion \\(L\\) aus Lernziel 5 hinzugef\u00fcgt. Ebenfalls Antworten zu allen Lernzielen verfasst.<\/p>\n<p>Noch drei Kurseinheiten, dann ist TIB auch schon vorbei. In dieser Kurseinheit geht es um Grammatiken. H\u00e4ufig wird in der Literatur zun\u00e4chst die Grammatik eingef\u00fchrt und anschlie\u00dfend die Komplexit\u00e4t, aber das soll uns hier nicht weiter st\u00f6ren.\u00a0Also wieder entlang der Lernziele.<\/p>\n<h2>Lernziel 1<\/h2>\n<p style=\"padding-left: 30px;\"><em>Was ist eine Grammatik \\(G\\), wie definiert man die Sprache \\(L(G)\\)?<\/em><\/p>\n<p>Eine Grammatik ist ein Modell zur Definition konkreter Sprachen. Die erste Definition im Skript ist die der formalen Sprache (letzter Punkt ist der aus dem Skript, alle anderen sind geklaut aus dem Buch von Dirk. W. Hoffmann).<\/p>\n<blockquote><p>Automat: Maschine zum Erkennen von Sprachen.<\/p>\n<p>Alphabet \\(\\Sigma\\), endliche Menge von Symbolen.<\/p>\n<p>Jedes Element \\(a\\) ist ein Zeichen des Alphabets.<\/p>\n<p>Jedes Element \\(\\omega\\) ist ein Wort \u00fcber \\(\\Sigma\\).<\/p>\n<p>Jede Teilmenge \\(L\\subseteq\\Sigma^{*}\\) ist eine <strong>formale Sprache<\/strong> \u00fcber \\(\\Sigma\\).<\/p><\/blockquote>\n<p>\\(\\Sigma^{*}\\) nennt man auch Kleen&#8217;sche H\u00fclle. Dort sind alle endlichen Symbolsequenzen drin, die wir mit den Symbolen aus\u00a0\\(\\Sigma\\) basteln k\u00f6nnen. Auch ist dort das leere Wort \\(\\epsilon\\) enthalten (im\u00a0\\(\\Sigma^{+}\\) jedoch nicht). Sagen wir z.B., dass \\(L\\) \u00fcber dem Alphabet \\(\\Sigma=\\{0,1,2,&#8230;,9\\}\\) die Menge der Ziffernfolgen ist, die einer Primzahl entsprechen, so w\u00e4re z.B. \\(2,3,5,7,&#8230;\\in L\\), w\u00e4hrend \\(1,4,6,8,&#8230;\\notin L\\) ist.<\/p>\n<p>Uns geht es aber nicht um die Bedeutung der Worte, sondern um die syntaktischen Anteile.<\/p>\n<p><strong>\u00dcberabz\u00e4hlbarkeit<\/strong><\/p>\n<p>Ein wichtiger Aspekt ist, dass die Menge der formalen Sprachen \u00fcber \\(\\Sigma\\) (also \\(L_{\\Sigma}\\))\u00a0\u00fcberabz\u00e4hlbar unendlich ist. F\u00fcr eine Abz\u00e4hlbarkeit brauchen wir eine Bijektion zwischen den nat\u00fcrlichen Zahlen \\(\\mathbb{N}\\) und der abzuz\u00e4hlenden Menge. Da jedoch die menge aller Sprachen \u00fcber einem Alphabet \\(L_{\\Sigma}\\) gleich der M\u00e4chtigkeit aller Teilmengen von \\(\\Sigma^{*}\\) ist, gilt\u00a0\\(L_{\\Sigma}=P(\\Sigma^{*})\\). Das \\(P\\) steht f\u00fcr <a href=\"http:\/\/de.wikipedia.org\/wiki\/%C3%9Cberabz%C3%A4hlbarkeit\">Potenzmenge<\/a>. Und da Potenzmengen einer beliebigen Menge eine gr\u00f6\u00dfere M\u00e4chtigkeit haben, als die menge selbst ist\u00a0\\(L_{\\Sigma}\\) \u00fcberabz\u00e4hlbar. Das Beweisverfahren vom <a title=\"TI: Entscheidbarkeit und charakteristische Funktion\" href=\"https:\/\/fernuni.digreb.net\/?p=909\">zweiten Cantor&#8217;schen Diagonalargument<\/a> findet hier Anwendung.<\/p>\n<p>Kommen wir aber nun zu dem Kerl, der das ganze verbrochen hat: <a href=\"http:\/\/de.wikipedia.org\/wiki\/Noam_Chomsky\">Noam Chomsky<\/a>. Von ihm stammen auch ein paar spannende B\u00fccher. Der Kerl lebt, wie Stephen A. Cook aus dem <a title=\"TIB: NP-Vollst\u00e4ndige Probleme (Lernziele KE4 2\/2)\" href=\"https:\/\/fernuni.digreb.net\/?p=1616\">vorherigen Beitrag zu KE4<\/a>, auch noch und lehr am <a href=\"http:\/\/web.mit.edu\/\">MIT<\/a>. Mit etwas Kleingeld f\u00fcr die Studiengeb\u00fchren oder gen\u00fcgend Gehirnschmalz f\u00fcr das Doc-Program des MIT kommt Ihr also noch in den Genuss seiner Lehren.<\/p>\n<p>Der Typ hat also ein einfaches, formales Modell einer Grammatik eingef\u00fchrt, mit dem man Grundstrukturen einer Sprache beschreiben kann. Im Skript ist die Grammatik als Virertupel definiert, wie in den meisten anderen B\u00fcchern auch. Hier l\u00e4sst es sich also sehr gut auch mit Zusatzliteratur arbeiten. Allgemein halte ich Teil B der theoretischen Informatik f\u00fcr &#8222;gelungener&#8220;. Ob das nun daran liegt, dass es wirklich besser ist oder ich mich mittlerweile von TIA habe abstumpfen lassen, m\u00f6chte ich an dieser Stelle nicht weiter analysieren.<\/p>\n<p>Definieren wir also die <strong>Grammatik<\/strong> als Vierertupel \\(G=(\\Pi,\\Sigma,R,S)\\):<\/p>\n<blockquote><p>\\(\\Pi\\) Nichtterminalalphabet, endliche Variablenmenge (Platzhalter, auch Nonterminalsymbole genannt. Lassen sich ersetzen)<\/p>\n<p>\\(\\Sigma\\) Terminalalphabet, \\(\\Pi\\cap\\Sigma=\\emptyset\\) (nicht weiter ersetzbare Sprachberstandteile, auch Terminale genannt).<\/p>\n<p>\\(R\\) Regelmenge\/Produktion mit \\(R\\subseteq((\\Sigma\\cup\\Pi)^{*}\\setminus{\\Sigma^*})\\times(\\Sigma\\cup\\Pi)^{*}\\) (nicht erschrecken, Erkl\u00e4rung kommt gleich)<\/p>\n<p>\\(S\\in\\Pi\\) Startsymbol (damit beginnt <strong>immer<\/strong> die Ableitung)<\/p><\/blockquote>\n<p>Das ist auch gleichzeitig die Definition der\u00a0<em>Typ-0-Grammatik<\/em>. Wahrscheinlich h\u00e4ngt Ihr gerade an der Definition der Regelmenge, oder? Wir definieren hier eine Ableitungsrelation. Es gilt zudem \\(x\\Rightarrow^{*}y\\) gdw. das Wort \\(y\\) aus dem Wort \\(x\\) in endlich vielen Schritten anhand der Regeln aus \\(R\\) abgeleitet werden kann.<\/p>\n<p><strong>Beispiel<\/strong>: \\(G=(\\Pi,\\Sigma,R,S)\\) mit \\(\\Pi=\\{S,L,R\\}\\), \\(\\Sigma=\\{\\#,a\\}\\) und Regeln \\(R\\) (KE5, S. 9)<\/p>\n<p style=\"padding-left: 30px;\">\\(S\\rightarrow\\#aL\\#\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(aL\\rightarrow La\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(\\#L\\rightarrow\\#R\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(Ra\\rightarrow aaR\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(R\\#\\rightarrow L\\#\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(R\\#\\rightarrow\\#\\)<\/p>\n<p>Aus diesen Regeln k\u00f6nnen wir nun Zeichenfolgen ableiten, die zur Sprache \\(L\\) mit der Grammatik \\(G\\) geh\u00f6ren, d.h. Fragen beantworten, wie z.B. \\(\\#aa\\#\\in L(G)\\)? Wir m\u00fcssen nur aus \\(\\#aL\\#\\) nach endlich vielen Schritten \\(\\#aa\\#\\) anhand dieser Regeln erzeugen k\u00f6nnen. Ist das der Fall, so haben wir\u00a0\\(\\#aa\\#\\in L(G)\\) bewiesen (und ja, es ist tats\u00e4chlich \\(\\#aa\\#\\in L(G)\\), probiert es mal selbst).<\/p>\n<p><strong>\u00dcbung<\/strong>:\u00a0\\(\\#aa\\#\\in L(G)\\)?<\/p>\n<p><a class=\"spoiler_link_show\" href=\"javascript:void(0)\" onclick=\"wpSpoilerToggle(document.getElementById('id1875151401'), this, 'L\u00f6sung zeigen', 'L\u00f6sung verstecken')\">L\u00f6sung zeigen<\/a>\n<div class=\"spoiler_div\" id=\"id1875151401\" style=\"display:none\">\\(\\#aL\\#\\rightarrow \\#La\\#\\rightarrow \\#Ra\\#\\rightarrow \\#aaR\\#\\rightarrow \\#aa\\#\\)<\/div>\n<\/p>\n<p>Eine weitere, spannende Definition ist, dass die<\/p>\n<blockquote><p>von Typ-0-Grammatiken erzeugten Sprachen genau die rekursiv aufz\u00e4hlbaren (<em>semi-entscheidbaren<\/em>) Wortmengen sind.<\/p><\/blockquote>\n<p><strong>Beweisidee<\/strong>: Hierzu wird f\u00fcr eine Bandmaschine eine Grammatik konstruiert, wobei die Regeln der Grammatik die Einzelschrittrelationen der Maschine sind. Die Sprache ist dann genau die Menge der von der Maschine erzeugten Worte. In umgekehrter Richtung wird eine \\(NTM\\) erstellt, die vom Startsymbol ausgeht die Regeln als Einzelschrittrelationen anwendet und anh\u00e4lt wenn das Eingabewort abgeleitet wurde.\u00a0Nehmen wir also an, dass unsere Maschine aus der Eingabe \\(aa\\) in einem Schritt eine Ausgabe \\(aaaa\\) erzeugt. Das entspr\u00e4che dann eine Regel in unserer Grammatik: \\(aa\\rightarrow{aaaa}\\).<\/p>\n<p><strong>Achtung<\/strong>:\u00a0Die Menge der rekursiv aufz\u00e4hlbaren (semi-entscheidbaren) Sprachen ist gegen\u00fcber<\/p>\n<ul style=\"list-style-type: disc;\">\n<li>Kleene&#8217;scher H\u00fcllenbildung,<\/li>\n<li>Konkatenation,<\/li>\n<li>Schnitt\u00a0und<\/li>\n<li>Vereinigung<\/li>\n<\/ul>\n<p>abgeschlossen,\u00a0nicht jedoch gegen\u00fcber dem\u00a0Komplement\u00a0(geklaut aus der Wikipedia).\u00a0Da das aber nicht so deutlich im Skript raus kam, wollte ich das hier etwas hervorheben.<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: eine Grammatik \\(G\\) ist ein Modell zur Definition konkreter Sprachen. Sie ist ein 4-Tupel mit Terminalen, Nonterminalen, dem Alphabet und dem, was eine Grammatik erst ausmacht: den Regeln. Mittels diesen Regeln, auch Produktionen genannt, wird eine Sprache \\(L(G)\\) erzeugt, d.h. eine Sprache \\(L\\) \u00fcber der Grammatik \\(G\\).<\/p>\n<h2>Lernziel 2 (Update)<\/h2>\n<p style=\"padding-left: 30px;\"><em>Welche Sprachklasse wird durch Grammatiken definiert?<\/em><\/p>\n<p><del>Hier schwimme ich gerade etwas, da ich nichts mit der Frage anzufangen wei\u00df. Grammatiken definieren unterschiedliche Sprachklassen. Je nach gew\u00e4hlter Grammatik werden unterschiedliche Sprachklassen (entscheidbare oder semi-entscheidbare Sprachen) definiert. Wer die Frage anders interpretiert und eine andere Antwort hat, bitte in die Kommentare damit.<\/del><\/p>\n<p>Wieder mal ein gro\u00dfer Dank an <a href=\"http:\/\/www.vom-lektorat-zum-buch.de\/\">Barbara<\/a>, mit der die Antwort zum Lernziel erarbeitet wurde.<\/p>\n<p>Zun\u00e4chst einmal noch zur Erinnerung: Die Sprachklassen sind unsere Sprachen, die durch Typ-X-Grammatiken definiert werden. Wir fangen ab Typ-0 an zu z\u00e4hlen, hierzu geh\u00f6rt jede <strong>Grammatik<\/strong>, d.h. die absolute Ober-Sprachklasse, die durch Grammatiken definiert wird ist die Typ-0-Sprachklasse. Erst durch Einschr\u00e4nkung unserer Grammatiken zu Typ-1-, -2-, und -3-Grammatiken werden weitere Sprachklassen, eben die Typ-1-, -2-, und -3-Sprachen, definiert, die aber alle eine echte Teilmenge der Typ-0-Sprachklasse sind (diese Inklusionsberziehung ist wichtig, daher merken!).<\/p>\n<p>Nicht falsch verstehen: es gibt auch Sprachen, die nicht von Grammatiken erzeugt werden k\u00f6nnen (\u00dcberabz\u00e4hlbarkeit der Potenzmenge, aber dazu kommen wir sp\u00e4ter noch). Die Typ-0-Sprachen sind eine echte Teilmenge dieser. In den folgenden Beitr\u00e4gen wird die Beziehung zwischen den einzelnen Sprachklassen noch deutlicher hervorgehoben, also noch etwas Geduld \ud83d\ude09<\/p>\n<p>Durch was ist die Oberklasse Typ-0, die von Grammatiken erzeugt werden kann, also definiert? Durch eine Turingmaschine, die h\u00e4lt wenn es ein Wort der Typ-0-Sprachklasse akzeptiert und nicht h\u00e4lt (oder sich in einem anderen Zustand befindet) wenn das Wort nicht aus der Typ-0-Sprachklasse ist. Das ist genau die Definition von semi entscheidbaren\/rekursiv aufz\u00e4hlbaren Wortmengen: die Typ-0-Sprachen sind genau die von Turingmaschinen akzeptierten Sprachen.<\/p>\n<p><strong>Beweisidee<\/strong><\/p>\n<p style=\"padding-left: 30px;\">\\(TM\\rightarrow Grammatik\\)<\/p>\n<p style=\"padding-left: 60px;\">Das ist die eine Richtung. Zu einer Turingmaschine \\(M\\) wird eine Grammatik \\(G\\) erzeugt, deren Regeln im wesentlichen die Einzelschrittrelationen sind. Die von der Grammatik \\(G\\) erzeugte Sprache \\(L(G)\\) ist dann genau die Menge der Worte, die \\(M\\) erzeugt.<\/p>\n<p style=\"padding-left: 60px;\"><span style=\"text-decoration: underline;\">Vorgehensweise<\/span>: die Grammatik simuliert mit ihren Ableitungsregeln die Einzelschrittrelationen (Konfigurations\u00fcberg\u00e4nge) der TM. Dabei werden alle m\u00f6glichen Eingabew\u00f6rter, Anfangskonfigurationen und die Konfigurations\u00fcberg\u00e4nge als Regeln konstruiert (Nonterminal als Zustand und Folgezustand, Terminal als Eingabezeichen). Dabei wird die Akzeptanz eines Wortes durch das L\u00f6schen von Nonterminalen (\\(C\\rightarrow\\epsilon\\)) simuliert und der Ableitungsvorgang so gestoppt.<\/p>\n<p style=\"padding-left: 60px;\">Damit erzeugt die Grammatik \\(G\\) genau die Worte, die von der TM \\(M\\) akzeptiert werden.<\/p>\n<p style=\"padding-left: 30px;\">\\(Grammatik\\rightarrow TM\\)<\/p>\n<p style=\"padding-left: 60px;\">F\u00fcr die umgekehrte Richtung wird eine NTM \\(T\\) zu einer Typ-0-Grammatik \\(G\\) erzeugt, welche vom Startsymbol der Grammatik ausgehend die Regeln der Grammatik anwendet und anh\u00e4lt wenn das Wort abgeleitet wurde. Anschlie\u00dfend wir die NTM durch eine TM simuliert.<\/p>\n<p style=\"padding-left: 60px;\"><span style=\"text-decoration: underline;\">Vorgehensweise<\/span>: Die TM simuliert die Ableitungsregeln. Dabei werden ableitbare Worte von der TM schrittweise auf das Hilfsband (man k\u00f6nnte auch ohne Hilfsband arbeiten) geschrieben und mit der Eingabe verglichen. Die Maschine akzeptiert das Wort, bzw. terminiert im Endzustand genau dann wenn \\(\\omega\\in L(G)\\).<\/p>\n<p style=\"padding-left: 60px;\">Damit akzeptiert die TM genau die Worte, die von der Grammatik erzeugt werden.<\/p>\n<p style=\"padding-left: 30px;\"><strong>Beispiel<\/strong>: kontextsensitive Grammatik\u00a0\\(G_0=(\\Pi,\\Sigma,R,S)\\) mit \\(\\Pi=\\{S,B,C\\}\\), \\(\\Sigma=\\{a,b\\}\\) und Regeln \\(R\\)<\/p>\n<p style=\"padding-left: 60px;\">\\(S\\rightarrow aSBC\\mid aBC\\)<\/p>\n<p style=\"padding-left: 60px;\">\\(aB\\rightarrow ab\\)<\/p>\n<p style=\"padding-left: 60px;\">\\(bB\\rightarrow bb\\)<\/p>\n<p style=\"padding-left: 60px;\">\\(bC\\rightarrow bc\\)<\/p>\n<p style=\"padding-left: 60px;\">\\(cC\\rightarrow cc\\)<\/p>\n<p style=\"padding-left: 60px;\">\\(CB\\rightarrow BC\\)<\/p>\n<p style=\"padding-left: 30px;\">Diese Grammatik \\(G_0\\) erzeugt die fiese, kontextsensitive Typ-0-Sprache\u00a0\\(L_0=\\{a^n b^n c^n\\mid n\\in\\mathbb{N}\\}\\Rightarrow(abc,aabbcc,&#8230;)\\). Nun m\u00fcssen wir zu der Grammatik eine Turingmaschine angeben, die \u00a0ein Wort aus dieser Sprache durch erreichen des Endzustands akzeptiert und ansonsten in einem anderen Zustand h\u00e4lt oder nicht terminiert.<\/p>\n<p style=\"padding-left: 30px;\"><span style=\"text-decoration: underline;\">Exkurs<\/span>:<\/p>\n<p style=\"padding-left: 60px;\">Es stellt sich die Frage, warum m\u00fcssen wir eine Turingmaschine angeben? Warum geht nichts anderes? Leider haben wir noch nicht die einzelnen Sprachklassen charakterisiert, evtl. w\u00e4re es dann bereits jetzt klar. Die Turingmaschine ist das m\u00e4chtigste Werkzeug das wir haben, sie ist genauso m\u00e4chtig wie Registermaschinen. Nur, dass Registermaschinen auf Zahlen operieren und Turingmaschinen auf Worten.<\/p>\n<p style=\"padding-left: 60px;\">Und selbst mit den Turingmaschinen k\u00f6nnen wir nicht alle Sprachen angeben, denn die Anzahl der Turingmaschinen ist, wie wir wissen, abz\u00e4hlbar\u00a0unendlich\u00a0(zweites Diagonalrgument von Cantor). Die Menge aller Sprachen \u00fcber \\(\\Sigma^{*}\\) ist es jedoch nicht (Potenzmenge, siehe oben). Damit k\u00f6nnen wir, wie erw\u00e4hnt, nicht alle Sprachen mit Turingmaschinen akzeptieren. Wenn wir die Turingmaschine einschr\u00e4nken, k\u00f6nnen wir eine immer kleinere Menge innerhalb dieser Obersprachklasse (Typ-0) abdecken, bis wir irgendwann bei den regul\u00e4ren Sprachen (Typ-3) angelangt sind, die von einem endlichen Automaten akzeptiert wird, was im Prinzip nichts weiter ist, als eine maximal eingeschr\u00e4nkte TM.<\/p>\n<p style=\"padding-left: 30px;\">Aber weiter im Text: Was wir nun tun m\u00fcssen, ist es die Ableitungssequenz umzukehren. Denn unsere TM nimmt ein Wort entgegen anstatt es zu produzieren. Dazu muss es das Wort in das Startsymbol zur\u00fcckf\u00fchren. Wenn es der TM gelungen ist, gilt das Wort als akzeptiert. K\u00f6nnen mehrere Regeln angewandt werden, so m\u00fcssen wir unsere TM als NTM konstruieren.<\/p>\n<p style=\"padding-left: 30px;\">Wir haben uns zwar darauf beschr\u00e4nkt Einband-TM zu betrachten, aber f\u00fcr die Grammatik \\(G_0\\) war ich etwas faul und habe auf ein Arbeitsband zur\u00fcckgegriffen. Mit etwas mehr Zust\u00e4nden schaffen wir das ganze Spiel auch auf einer Einband-TM. In der folgenden Grafik wird die TM aufgezeigt, die unsere Sprache akzeptiert (ich habe mein neues\u00a0<a href=\"https:\/\/fernuni.digreb.net\/?p=1932\">Spielzeug<\/a>\u00a0benutzt, kann ich nur empfehlen). Das JFLOP-File k\u00f6nnt Ihr\u00a0<a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/g0_2band_tm.rar\">hier<\/a>\u00a0downloaden.<\/p>\n<p style=\"padding-left: 30px;\"><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/g0tm.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/g0tm.png\" alt=\"g0tm\" width=\"490\" height=\"191\" \/><\/a><\/p>\n<p style=\"padding-left: 30px;\">Erkl\u00e4rung der Grafik: \\(a;a,R\\mid B;A.R\\) bedeutet z.B. Lese auf dem Eingabeband ein \\(a\\) und gehe auf diesem nach rechts. Lese gleichzeitig auf dem Hilfsband ein \\(B\\) (Blank), schreibe ein \\(A\\) und gehe auf dem Hilfsband nach rechts.<\/p>\n<p style=\"padding-left: 30px;\"><strong>Funktionsweise<\/strong>: wir laufen das Wort ab und schreiben so viele \\(A&#8217;s\\) auf das Hilfsband, wie wir \\(a&#8217;s\\) auf dem Eingabeband haben. Anschlie\u00dfend gehen wir die \\(b&#8217;s\\) durch und ersetzen die gleiche Anzahl an \\(A&#8217;s\\) auf dem Hilfsband, wie \\(b&#8217;s\\) auf dem Eingabeband vorhanden sind durch \\(C&#8217;s\\). Nun werden die \\(c&#8217;s\\) auf dem Eingabeband eingelesen und die gleiche Anzahl der \\(C&#8217;s\\) auf dem Hilfsband gel\u00f6scht.<\/p>\n<p style=\"padding-left: 30px;\">Jetzt wandern wir auf beiden B\u00e4ndern so weit zur\u00fcck, wie unser Eingabewort lang ist. Finden wir dann nur noch Blanks auf dem Hilfsband und sind wir am Anfang unseres Eingabewortes angelangt, wird das Wort akzeptiert.<\/p>\n<p style=\"padding-left: 30px;\">Ladet euch die Datei f\u00fcr das JFLOP herunter und probiert es selbst aus (Links zu JFLOP und der Datei oberhalb der Grafik).<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>:\u00a0die Typ-0-Grammatiken definieren die Typ-0-Sprachklasse. Diese Sprachen sind genau die von Turingmaschinen akzeptierten\/semi entscheidbaren\/rekursiv aufz\u00e4hlbaren Wortmengen.<\/p>\n<p>Sie bilden die Oberklasse aller Sprachen, jedoch kann es auch Sprachen geben, die nicht von Grammatiken erzeugt werden k\u00f6nnen. Dies wird mit dem gleichen Verfahren bewiesen, wie es auch im zweiten Diagonalargument von Cantor angewandt wurde: es gibt einfach mehr Sprachen (Produktmenge \u00fcber \\(\\Sigma\\)), als es Turingmaschinen geben kann (Stichwort: \u00dcberabz\u00e4hlbarkeit).<\/p>\n<h2>Lernziel 3<\/h2>\n<p style=\"padding-left: 30px;\"><em>Was sind Typ-1-, Typ-2-, Typ-3-Grammatiken?<\/em><\/p>\n<p>Neben den Typ-0-Grammatiken gibt es auch noch weitere. Das ist dann die Chomsky-Hierarchie. Der werte Herr &#8211; Sprachwissenschaftler &#8211; hat 1957 ein Regelwerk erstellt um die Grammatiken in vier Klassen einzuteilen. Diese sind wie folgt:<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li><strong>Typ-0-Grammatiken<\/strong>: Phrasenstrukturgrammatiken\n<p>Die haben wir eben kennengelernt. Jede Grammatik ist auch immer eine Typ-0-Grammatik. Es gibt keine weiteren Einschr\u00e4nkungen als die erste Definition zum Vierertupel\u00a0\\(G=(\\Pi,\\Sigma,R,S)\\) in diesem Beitrag.<\/p>\n<p><strong>Automat:<\/strong> Zu jeder Typ-0-Sprache existiert eine TM, die diese Sprache akzeptiert (eine TM ist unser st\u00e4rkstes Berechnungsinstrument). Da wir eine NTM durch eine TM simulieren k\u00f6nnen (die TM simuliert einfach alle Berechnungspfade der NTM, k\u00f6nnen wir hier uns auf eine TM beschr\u00e4nken).<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li><strong>Typ-1-Grammatiken<\/strong>: Kontextsensitive Grammatiken\u00a0(kontextsensitive Sprache)\n<p>F\u00fcr die Produktionsbeziehungen \\(l\\rightarrow r\\) gilt die Beziehung \\(\\mid r\\mid\\geq\\mid l\\mid\\). D.h. die Anwendung der Produktion f\u00fchrt <strong>nie<\/strong> zu einer Verk\u00fcrzung der Zeichenkette. Ganz einfach, oder?<\/p>\n<p><strong>Beispiel<\/strong>: \\(aA\\rightarrow aBb\\)<\/p>\n<p><strong>Automat:\u00a0<\/strong>Zu jeder Typ-1-Sprache existiert eine linearbeschr\u00e4nkte TM, die diese Sprache akzeptiert. Die lineare Beschr\u00e4nkung ist der Tatsache geschuldet, dass wir die Grammatik eingeschr\u00e4nkt haben. Die rechte Seite der Produktion wird nie kleiner. Weil wir in der TM die Berechnung umkehren (wir leiten in der Maschine ein gegebenes ein Wort zu seinem Ursprung, statt wie in der Grammatik den Ursprung zum Wort), k\u00f6nnen wir nie mehr Zeichen auf dem Band bekommen als die Eingabe initial lang war.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li><strong>Typ-2-Grammatiken<\/strong>: Kontextfreie Grammatiken (kontextfreie Sprache)\n<p>Die linke Seite der Produktionsregeln besteht immer nur aus einer einzigen Variable, es gilt also: \\(l\\rightarrow r\\Rightarrow l\\in\\Pi\\). Auch nicht viel schwerer als Typ-1.<\/p>\n<p><strong>Beispiel<\/strong>: \\(A\\rightarrow aBb\\).<\/p>\n<p><strong>Automat:\u00a0<\/strong>Zu jeder Typ-2-Sprache existiert ein nichtdeterministischer Kellerautomat, der diese akzeptiert. Der Kellerautomat ist weniger m\u00e4chtig als die TM (zumindest mit nur einem Speicher), wir k\u00f6nnen uns also auf ein weniger m\u00e4chtiges Konstrukt st\u00fctzen. Warum? Weil das wieder der noch mehr eingeschr\u00e4nkten Grammatik geschuldet ist. Aber normale Automaten reichen nicht aus, da hier beliebig viele Nonterminale auftreten k\u00f6nnen. Wir brauchen also noch einen Speicher. Da wir uns auf Linksableitungen beschr\u00e4nken (das am links stehende Nonterminal wird ersetzt) k\u00f6nnen und somit immer nur auf das erste Zeichen im Kellerspeicher zugreifen, k\u00f6nnen wir diese Linksableitungen einer kontextfreien Grammatik mit unserem Kellerautomaten (NTM mit einem Einweig-Eigabeband und einem Kellerspeicher) simulieren.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li><strong>Typ-3-Grammatiken<\/strong>: Regul\u00e4re Grammatiken (rechtslineare Sprache)\n<p>Sie sind zun\u00e4chst kontextfrei und die rechte Seite der Produktion besteht entweder aus einem leeren Wort \\(\\epsilon\\) oder einem Terminalsymbol, dem ein Nichtterminalsymbol folgt. Formal: \\(l\\rightarrow r\\) mit \\(l\\in\\Pi\\) und \\(r\\in\\{\\epsilon\\}\\cup\\Sigma\\cdot\\Pi\\) (Danke Gerald, vorher stand da \\(r\\in\\{\\epsilon\\}\\cup\\Sigma\\cup\\Pi\\), bl\u00f6des CopyPaste). Das war jetzt etwas schwieriger. Wenn man die Definition langsam liest, erschlie\u00dft sich einem der Satz etwas besser.<\/p>\n<p><strong>Beispiel<\/strong>: \\(A\\rightarrow aB\\)<\/p>\n<p><strong>Automat:\u00a0<\/strong>Zu jeder Typ-3-Sprache existiert ein endlicher Automat, der diese akzeptiert. Noch eine weitere Einschr\u00e4nkung. Hier brauchen wir nicht einmal einen Speicher, sondern kommen mit Zust\u00e4nden aus.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>Nochmal zur Erinnerung: ein <strong>Terminalsymbol<\/strong> ist ein Symbol, dass nicht weiter ersetzt werden kann. Ein <strong>Nichtterminalsymbol<\/strong>\u00a0jedoch ist ein Platzhalter, den man durchaus ersetzen kann.<\/p>\n<p>Zwischen den Sprachen gilt die folgende <strong>echte<\/strong> Inklusionsbeziehung: \\(L(Typ-0)\\supset L(Typ-1)\\supset L(Typ-2)\\supset L(Typ-3)\\). Grafisch dargestellt sieht der ganze Spa\u00df so aus:<\/p>\n<p style=\"text-align: center;\"><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/05\/sprachen2.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter  wp-image-1960\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/05\/sprachen2.png\" alt=\"sprachen2\" width=\"526\" height=\"222\" srcset=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/05\/sprachen2.png 1097w, https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/05\/sprachen2-300x126.png 300w, https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/05\/sprachen2-1024x433.png 1024w\" sizes=\"auto, (max-width: 526px) 100vw, 526px\" \/><\/a><\/p>\n<p>Im Skript wird ebenfalls eine Verbindung zwischen den Komplexit\u00e4tsklassen und den Sprachen in der Chomsky-Hierarchie konstruiert, so dass folgende Aussagen \u00e4quivalent sind:<\/p>\n<blockquote><p>\\(L\\) ist eine <em>Typ-1-Sprache (kontextsensitiv)<\/em>.<\/p>\n\\(L\\in NBAND(n)\\)<\/blockquote>\n<p>Das liegt an folgenden Dingen: keine Regel kann das Wort verk\u00fcrzen, au\u00dfer \\(S\\rightarrow\\epsilon\\). Damit haben wir \\(lg(x)\\leq lg(y)\\) (wir leiten von \\(x\\) auf \\(y\\) ab) wenn wir nicht auf ein leeres Wort ableiten. Haben wir zudem z.B. eine Eingabe \\(x\\) von der wir pr\u00fcfen wollen ob sie zu der Sprache \\(L(G)\\) geh\u00f6rt oder nicht, leiten wir ausgehend vom Startsymbol ab. Da die L\u00e4nge des abgeleiteten Wortes aufgrund der Einschr\u00e4nkung f\u00fcr <em>Typ-1-Sprachen<\/em> sich nie verk\u00fcrzen kann, k\u00f6nnen wir die Berechnung verwerfen wenn wir ein Wort ableiten, dass l\u00e4nger als unsere Eingabe ist.<\/p>\n<p>Noch eine Kleinigkeit: wegen dem <a title=\"TIB: NP-Vollst\u00e4ndige Probleme (Lernziele KE4 2\/2)\" href=\"https:\/\/fernuni.digreb.net\/?p=1616\">Satz von Savitch<\/a>\u00a0ist auch jede kontextsensitive Sprache in Exponentialzeit und \\(BAND(n^2)\\) entscheidbar.<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: die Grammatiken werden, ausgehend von Typ-0, immer\u00a0restriktiveren\u00a0Einschr\u00e4nkungen f\u00fcr die Produktionsregeln unterworfen. Dadurch wird es m\u00f6glich die Obermenge der Typ-0-Sprachen (semi-Entscheidbarkeit) immer weiter einzuschr\u00e4nken, bis man letztlich zu den Typ-3-Sprachen (regul\u00e4re Sprachen, vollst\u00e4ndig entscheidbar durch einen endlichen Automaten) kommt. Es ergibt sich so eine echte Inklusionsbeziehung zwischen den Sprachklassen und eine Hierarchiebeziehung, auch Chomsky Hierarchie genannt.<\/p>\n<p>Diese Sprachen spielen eine gro\u00dfe Rolle bei den Programmiersprachen: Typ-2-Sprachen (kontextfrei) erlauben z.B. eine Interpretation von Ausdr\u00fccken dieser Sprache, so dass entschieden werden kann ob ein Ausdruck den Regeln der Grammatik entspricht (Parser) oder nicht.<\/p>\n<h2>Lernziel 4<\/h2>\n<p style=\"padding-left: 30px;\"><em><em>Wie definiert man regul\u00e4re Mengen?<\/em><\/p>\n<p><\/em><\/p>\n<p>Im Skript steht, dass jeder Informatiker die regul\u00e4ren Sprachen und ihre Eigenschaften kennen muss. Dem wollen wir uns also nicht verschlie\u00dfen. Die Menge der regul\u00e4ren Sprachen ist die kleinste Sprachklasse in der <a href=\"http:\/\/de.wikipedia.org\/wiki\/Chomsky-Hierarchie\">Chomsky-Hierarchie<\/a>. Sie sind rechtslinear (der Syntaxbaum neigt sich nach unten rechts weg) und werden von determinierten und nichtdeterminierten Automaten erkannt. Automaten werden leider in der n\u00e4chsten Kurseinheit besprochen, was ich schade finde. Das w\u00fcrde zum Verst\u00e4ndnis dieser KE sicherlich beitragen. Aber sei es drum: wenn euch etwas noch nicht zu 100% klar ist, schaut in die n\u00e4chste KE.<\/p>\n<p>Aber weiter im Text: Die herausgehobene Position der regul\u00e4ren Sprachen in der Informatik basiert auf deren Verwendung, z.B. als regul\u00e4re Ausdr\u00fccke in Suchmustern.\u00a0Bevor wir darauf n\u00e4her eingehen,\u00a0definieren wir zun\u00e4chst die Operationen auf den Sprachen \u00fcber einem festen Alphabet, die auf Wortmengen zugeschnitten sind:<\/p>\n<blockquote><p>\\(X\\cdot Y := \\{xy\\mid x\\in X, y\\in Y\\}\\).\u00a0<a href=\"http:\/\/de.wikipedia.org\/wiki\/Komplexprodukt\">Komplexprodukt<\/a> von \\(X\\) und \\(Y\\).<\/p>\n<p>\\(X^n(n\\geq0)\\) als \\(X^0=\\{\\epsilon\\}\\) und \\(X^{n+1}=X^n\\cdot X\\)<\/p>\n<p>\\(X^{*}=\\bigcup_{n\\geq 0} X^n\\). Sternoperation.<\/p>\n<p>\\(X^{+}=\\bigcup_{n\\geq 0} X^n\\) (\\(X^*\\cdot X\\))<\/p>\n<p>\\(\\overline{X}=\\Sigma^{*}\\setminus X\\) (Komplement bzgl. \\(\\Sigma^{*}\\))<\/p>\n<p>\\(X^{R}=\\{x^R\\mid x\\in X\\}\\) (Spiegelung)<\/p><\/blockquote>\n<p>Definieren wir mal die regul\u00e4re Menge\/regul\u00e4re Sprache wie im Skript:<\/p>\n<blockquote><p>\\(\\emptyset\\) ist eine regul\u00e4re Menge \u00fcber \\(\\Sigma\\). Wenn \\(a\\) ein Element von \\(\\Sigma\\) ist, so ist die Wortmenge \\(\\{a\\}\\) eine regul\u00e4re Menge \u00fcber \\(\\Sigma\\).<\/p>\n<p>Sind \\(X\\) und \\(Y\\) regul\u00e4re Mengen, so ist es auch \\(X\\cup Y, X\\cdot Y\\) und \\(Y^{*}\\). Die regul\u00e4ren Mengen sind also bzgl. der genannten Operationen abgeschlossen.<\/p><\/blockquote>\n<p>Eine Menge nennt man regul\u00e4r wenn sie in endlich vielen Schritten mit den genannten Operationen in der letzten Definition erzeugt werden kann. Mit \\(REG_n\\) werden im Skript die regul\u00e4ren Mengen \u00fcber \\(\\Sigma\\) genannt, die man in \\(n\\) Schritten erzeugen kann. Da wir bereits die rekursiv aufz\u00e4hlbaren (semi-entscheidbaren) Sprachen hatten, haben die regul\u00e4ren Sprachen einen weiteren Vorteil:<\/p>\n<p>&nbsp;<\/p>\n<blockquote><p>Jede regul\u00e4re Menge\/Sprache ist rekursiv (entscheidbar)<\/p>\n<p>Jede endliche Menge \\(M\\subseteq\\Sigma^{*}\\) ist regul\u00e4r<\/p><\/blockquote>\n<p>&nbsp;<\/p>\n<p><strong>Achtung<\/strong>: Damit bilden sie eine echte Teilmenge in den Typ-0-Sprachen (die Menge der rekursiven (entscheidbaren) Sprachen ist eine Teilmenge der rekursiv aufz\u00e4hlbaren Sprachen).\u00a0Die regul\u00e4ren Sprachen erweisen sich als abgeschlossen unter<\/p>\n<ul style=\"list-style-type: disc;\">\n<li>Komplementbildung,<\/li>\n<li>Konkatenation,<\/li>\n<li>Schnitt,<\/li>\n<li>Vereinigung und<\/li>\n<li>Bildung des Kleeneschen Abschlusses.<\/li>\n<\/ul>\n<p>Bei Gelegenheit werde ich ein paar Beispiele zu den vorgestellten Operationen in diesen Beitrag einbauen.<\/p>\n<p>Noch ein Nachtrag aus der <a href=\"http:\/\/de.wikipedia.org\/wiki\/Regul%C3%A4re_Sprache\">Wikipedia<\/a> zum Thema: M\u00f6chte man zeigen, dass eine Sprache regul\u00e4r ist, so\u00a0muss man sie auf eine regul\u00e4re Grammatik, einen endlichen Automaten (z. B. einen Moore-Automaten) oder einen regul\u00e4ren Ausdruck oder auf bereits bekannte regul\u00e4re Sprachen zur\u00fcckf\u00fchren. F\u00fcr einen Nachweis, dass eine Sprache \u00a0nicht regul\u00e4r ist, kann man das <a href=\"http:\/\/de.wikipedia.org\/wiki\/Pumping-Lemma\">Pumping-Lemma<\/a> verwenden (dazu stand leider in dieser KE nichts, aber im Buch von Hoffmann schon. Wenn auch in KE6 und 7 nichts dazu steht, schreibe ich das hier ausf\u00fchrlich hin).<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: am Anfang stehen die einzelnen Zeichen \\(a\\) unseres Alphabets \\(\\Sigma\\). Diese nennen wir regul\u00e4r. Alles, was wir aus diesen Zeichen mittels Vereinigung, Verkettung und Sternoperation (Kleen&#8217;sche H\u00fclle) und der leeren Menge \\(\\emptyset\\) (welche der Definition nach ebenfalls regul\u00e4r ist) basteln k\u00f6nnen ist ebenfalls regul\u00e4r.<\/p>\n<p>Haben wir regul\u00e4re Mengen \\(X\\) und \\(Y\\), so ist die Menge, die durch die genannten Operationen auf diesen Mengen entsteht&#8230; ja, genau: auch regul\u00e4r.<\/p>\n<h2>Lernziel 5<\/h2>\n<p style=\"padding-left: 30px;\"><em><em>Welche Sprache wird durch einen regul\u00e4ren Ausdruck definiert?<\/em><\/p>\n<p><\/em><\/p>\n<p>Kommen wir nun zu den regul\u00e4ren Ausdr\u00fccken. Mit ihnen k\u00f6nnen wir regul\u00e4re Sprachen beschreiben. Damit kann jede Erzeugungsvorschrift durch einen regul\u00e4ren Ausdruck verschl\u00fcsselt werden, so dass wir durch die Syntax (regul\u00e4rer Ausdruck) die regul\u00e4re Sprache (Semantik) bekommen.<\/p>\n<p>Damit ist \\(L\\) unsere Semantikfunktion, die zu jedem regul\u00e4ren Ausdruck \\(\\alpha\\) eine Sprache aus \\(\\Sigma^{*}\\) zuordnet, sie fungieren als eine Art &#8222;Name&#8220; f\u00fcr die regul\u00e4ren Mengen (der Satz ist aus dem Skript. Ich finde ihn aber sehr anschaulich und habe ihn deswegen f\u00fcr den Beitrag geklaut).<\/p>\n<p>Definieren wir sie wieder zun\u00e4chst:<\/p>\n<blockquote><p>Sei \\(\\Sigma\\) ein beliebiges Alphabet, \\(Reg(\\Sigma)\\) die Menge der regul\u00e4ren Ausdr\u00fccke, die induktiv aus folgenden Regeln gebildet wird:<\/p>\n\\(\\emptyset,\\epsilon\\in Reg(\\Sigma)\\)\n\\(\\Sigma\\subset Reg(\\Sigma)\\)\n<p>Wenn \\(r\\in{Reg(\\Sigma)}\\) und \\(s\\in{Reg(\\Sigma)}\\), dann sind auch \\(rs\\) und \\((r\\mid s)\\in{Reg(\\Sigma)}\\)<\/p>\n<p>Wenn \\(r\\in{Reg(\\Sigma)}\\), dann sind auch \\((r)\\) und \\(r^*\\in{Reg(\\Sigma)}\\)<\/p><\/blockquote>\n<p>Es gelten die Rechenregeln:<\/p>\n<blockquote><p>Kommutativgesetz: \\(r\\mid s = s\\mid r\\)<\/p>\n<p>Idempotenzgesetz: \\(r\\mid r = r\\)<\/p>\n<p>Distributivgesetz: \\(r(s\\mid t) = rs\\mid rt\\) und \\((s\\mid t)r=sr\\mid tr\\)<\/p>\n<p>Neutrale Elemente: \\(r\\mid\\emptyset =\\emptyset\\mid r=r\\) und \\(r\\epsilon=\\epsilon r=r\\)<\/p><\/blockquote>\n<p>Wir k\u00f6nnen hiermit zu jeder Grammatik einen regul\u00e4ren Ausdruck finden, der die gleiche Sprache erzeugt: eine Sprache aus der Sprachklasse <em>Typ-3<\/em>. regul\u00e4re Ausdr\u00fccke und regul\u00e4re Grammatiken k\u00f6nnen auf endliche Automaten reduziert werden.<\/p>\n<p>Wie bereits erw\u00e4hnt, werden diese regul\u00e4ren Ausdr\u00fccke f\u00fcr Suchmuster verwendet. D.h. Werkzeuge wie <em>sed<\/em> oder <em>grep<\/em> unter UNIX greifen genau auf dieses Modell zu. Die Konkatenation (\\(ab\\)), Auswahl (\\(a\\mid b\\)) oder der Kleene-Stern (\\(*\\)) sind unver\u00e4ndert vorhanden. Alle anderen Erweiterungen dienen der Verk\u00fcrzung der Schreibweise und lassen sich auf diese Kernkonstrukte zur\u00fcckf\u00fchren.<\/p>\n<p>Die Funktion \\(L\\), die unserem regul\u00e4ren Ausdruck \\(\\alpha\\) eine Sprache zuordnet wird durch folgende Gleichungen definiert, die wir auch gleich in einem Beispiel anwenden werden:<\/p>\n<blockquote>\\(L(\\emptyset) = \\emptyset\\)\n<p><em>Die vom regul\u00e4ren Ausdruck \\(\\emptyset\\) erzeugte Sprache ist leer (es ist das leere Wort \\(\\epsilon\\)). Nicht vergessen: leere Mengen sind von Definition aus regul\u00e4r.<\/em><\/p>\n\\(L(a) = \\{a\\}\\)\n<p><em>Die vom regul\u00e4ren Ausdruck \\(a\\) erzeugte Sprache ist das Zeichen \\(a\\).<\/em><\/p>\n\\(L(\\alpha\\cup\\beta) = L(\\alpha)\\cup L(\\beta)\\)\n<p><em>Die Sprache, die aus der Vereinigung von zwei regul\u00e4ren Ausdr\u00fccken \\(\\alpha\\) und \\(\\beta\\) beschrieben wird, kann man auch auch durch die Vereinigung der Sprachen, die nur durch \\(\\alpha\\) und \\(\\beta\\) beschrieben werden, erzeugen.<\/em><\/p>\n\\(L(\\alpha\\beta) = L(\\alpha)\\cdot L(\\beta)\\)\n<p><em>Die Sprache, die aus der Konkatenation von zwei regul\u00e4ren Ausdr\u00fccken \\(\\alpha\\) und \\(\\beta\\) beschrieben wird, kann man auch auch durch die Konkatenation der Sprachen, die nur durch \\(\\alpha\\) und \\(\\beta\\) beschrieben werden erzeugen.<\/em><\/p>\n\\(L(\\alpha^{*}) = (L(\\alpha))^{*}\\)\n<p><em>Die Sprache, die durch den Sternoperator, angewandt auf den regul\u00e4ren Ausdruck \\(\\alpha\\) erzeugt wird, kann auch durch Anwendung des Sternoperators auf die nur durch \\(\\alpha\\) beschriebene Sprache erzeugt werden.<\/em><\/p><\/blockquote>\n<p>Am einfachsten zeigt man die Anwendung sicher an einem kleinen Beispiel (aus dem Skript).<\/p>\n<p><strong>Beispiel<\/strong>: regul\u00e4rer Ausdruck \\(\\beta=(\\emptyset^{*}\\cup(a^{*}b))\\)<\/p>\n<p style=\"padding-left: 30px;\">Wir suchen also die durch den Ausdruck beschriebene Sprache \\(L(\\beta)\\). Das geht ganz simpel durch Aufl\u00f6sen:<\/p>\n<p style=\"padding-left: 30px;\">\\(\\begin{align}L(\\beta)&amp;=L((\\emptyset^{*}\\cup(a^{*}b)))\\\\&amp;=L(\\emptyset^{*})\\cup L(a^{*}b)\\\\&amp;=L(\\emptyset^{*})\\cup(L(a^{*})\\cdot\\{b\\})\\\\&amp;=\\{\\epsilon\\}\\cup(\\{a\\}^{*}\\cdot\\{b\\})\\\\&amp;=\\{\\epsilon\\}\\cup\\{a\\}^{*}\\cdot\\{b\\}\\end{align}\\)<\/p>\n<p style=\"padding-left: 30px;\">Damit ist die zum regul\u00e4ren Ausdruck \\(\\beta\\) gesuchte Sprache \\(L(\\beta)=\\{\\epsilon\\}\\cup\\{a\\}^{*}\\cdot\\{b\\}\\).<\/p>\n<p style=\"padding-left: 30px;\">Was haben wir gemacht?<\/p>\n<p style=\"padding-left: 60px;\">\\((1)\\) Aufl\u00f6sung von \\(\\beta\\)<\/p>\n<p style=\"padding-left: 60px;\">\\((2)\\) wir k\u00f6nnen nicht nur Elemente, sondern auch Mengen mit den oben genannten Operationen verbinden, was wir hier der \u00dcbersichtlichkeit halber getan haben.<\/p>\n<p style=\"padding-left: 60px;\">\\((3)\\) \\(\\{b\\}\\) ist nur ein einzelnes Zeichen, dass k\u00f6nnen wir ebenfalls f\u00fcr die \u00dcbersichtlichkeit rausnehmen und mit der Konkatenation wieder verbinden<\/p>\n<p style=\"padding-left: 60px;\">\\((4)\\) welche Sprache beschreibt \\(L(\\emptyset)\\)? Keine gro\u00dfe, es besteht nur aus dem leeren Wort \\(\\epsilon\\). Gesagt, getan! Was beschreibt \\(L(a^*)\\)? Nur einen beliebig langen String aus \\(a&#8217;s\\). Also aufl\u00f6sen.<\/p>\n<p style=\"padding-left: 60px;\">\\((5)\\) und nun das Verbliebene nur noch mit den Operatoren verbinden und wir haben unsere Sprache gefunden.<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: mit regul\u00e4ren Ausdr\u00fccken (d.h. die Verwendung von Zeichen aus dem Alphabet mit den auf regul\u00e4ren Mengen definierten Operationen Vereinigung, Konkatenation und Kleene Stern) beschreiben wir Erzeugungsvorschriften f\u00fcr regul\u00e4re Sprachen. Sie fungierten so als eine Art &#8222;Name&#8220; f\u00fcr eine regul\u00e4re Menge.<\/p>\n<h2>Lernziel 6<\/h2>\n<p style=\"padding-left: 30px;\"><em><em>Was ist eine rechtslineare Grammatik?<\/em><\/p>\n<p><\/em><\/p>\n<p>Wie wir oben bereits geschrieben haben ist jede regul\u00e4re Grammatik auch eine rechtslineare Grammatik. Aufgrund der Struktur der Produktion neigt sich der Syntaxbaum nach rechts unten weg. Die Regeln haben folgende Form:<\/p>\n<blockquote><p>\\(A\\rightarrow\\omega B\\) oder<\/p>\n\\(A\\rightarrow\\omega\\)<\/blockquote>\n<p>Das hei\u00dft soviel, dass die\u00a0rechte Seite der Produktion aus einem Wort (mehrere Zeichen) \u00fcber \\(\\Sigma\\) und einem Nonterminal oder nur einem Wort \u00fcber \\(\\Sigma\\) besteht. Merkt euch die Definition, der Unterschied zur rechtslinearen Normalformgrammatik ist nur ganz klein, aber wichtig. Mit dem leeren Wort \\(\\epsilon\\) k\u00f6nnen wir ein Nonterminal verschwinden lassen und so den Ableitungsprozess stoppen.<\/p>\n<p>Ein <strong>Beispiel<\/strong> aus dem Buch von Dirk. W. Hoffmann (auf die Definition Skript gem\u00fcnzt):\u00a0\\(G_1=(\\Pi,\\Sigma,R,S)\\) mit \\(\\Pi=\\{S,B,C\\}\\), \\(\\Sigma=\\{a,b\\}\\), Startsymbol \\(S\\) und den Regeln \\(R\\):<\/p>\n<p style=\"padding-left: 30px;\">\\(S\\rightarrow aB\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(B\\rightarrow bC\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(C\\rightarrow\\epsilon\\mid aB\\)<\/p>\n<p>Wollen wir z.B. \\(abab\\) ableiten, also schauen ob \\(abab\\in L(G_1)\\) ist, so haben wir folgende Sequenz: \\(S\\rightarrow aB\\rightarrow abC\\rightarrow abaB\\rightarrow ababC\\rightarrow abab\\). Der Syntaxbaum hierzu sieht wie folgt aus:<\/p>\n<p style=\"text-align: center;\"><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/05\/abab_ableitung.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter  wp-image-1700\" style=\"margin-left: 150px; margin-right: 200px;\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/05\/abab_ableitung.png\" alt=\"abab_ableitung\" width=\"160\" height=\"190\" \/><\/a><\/p>\n<p>Schaut nochmal zur Definition der Typ-3-Sprachen (erzeugt von regul\u00e4ren Grammatiken, damit ist jede regul\u00e4re Sprache auch rechtslinear) hoch. Unsere Grammatik \\(G_1\\) erf\u00fcllt genau die dort gemachten Einschr\u00e4nkungen und erzeugt unsere Sprache. Sie ist au\u00dferdem auch noch in einer (rechtslinearen) Normalform, aber dazu gleich mehr.<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: eine rechtslineare Grammatik hat eine bestimmte Form der Produktionsregeln (auf der rechten Seite der Produktion steht entweder ein Wort oder ein Wort, gefolgt von einem Nonterminal). Da nur am \u00e4u\u00dfersten, rechten Rand ein Nonterminal steht, dass ersetzt werden kann, neigt sich der Ableitungsbaum nach rechts.<\/p>\n<p>Diese Regeln entsprechen denen f\u00fcr die Typ-3 Grammatiken, so dass jede regul\u00e4re Sprache auch rechtslinear ist.<\/p>\n<h2>Lernziel 7<\/h2>\n<p style=\"padding-left: 30px;\"><em>Wie zeigt man, dass die regul\u00e4re Sprache von rechtslinearen Grammatiken erzeugt wird?<\/em><\/p>\n<p>Eine von einer regul\u00e4ren Grammatik erzeugte Sprache nennt man regul\u00e4re Sprache. F\u00fcr jede regul\u00e4re Sprache existiert auch immer mindestens eine regul\u00e4re Grammatik. Wir m\u00fcssen also zeigen, dass wir aus einer rechtslinearen Grammatik mit den bei Typ-3-Definition gemachten Einschr\u00e4nkungen eine regul\u00e4re Sprache erzeugen k\u00f6nnen.<\/p>\n<p>Die Beweisidee im Skript folgt der Induktion \u00fcber den Aufbau regul\u00e4rer Mengen mittels der Operationen Vereinigung, Produkt und Stern aus den Mengen \\(\\emptyset\\) und \\(\\{a\\}\\) \u00fcber einem Alphabet \\(\\Sigma\\). Es wird gezeigt, dass es zu diesen Mengen rechtslineare Grammatiken gibt. Wenn das der Fall ist, so gibt es auch (aufgrund der Abgeschlossenheit) auch rechtslineare Grammatiken zu den Ergebnissen wenn man Vereinigung, Produkt und Stern auf\u00a0\\(\\emptyset\\) und \\(\\{a\\}\\) anwendet.<\/p>\n<p>Ohne auf Details einzugehen:<\/p>\n<p style=\"padding-left: 30px;\">1. Wir zeigen, dass wir die Sprachen \\(L_1=\\emptyset\\) und \\(L_2=\\{a\\}\\) durch entsprechende Grammatiken \\(G_1\\) und \\(G_2\\) erzeugen k\u00f6nnen<\/p>\n<p style=\"padding-left: 30px;\">2. Anschlie\u00dfend zeigen wir, dass wir durch die Vereinigung \\(L_1\\cup{L_2}\\) eine neue Sprache \\(L\\) bekommen, die wir wiederum durch eine entsprechende Grammatik \\(G\\) erzeugen k\u00f6nnen<\/p>\n<p style=\"padding-left: 30px;\">3. Nun k\u00fcmmern wir uns um das Produkt\u00a0\\(L_1\\cdot{L_2}\\) und zeigen ebenfalls, dass wir zu der erzeugten Sprache \\(L\\) eine Grammatik \\(G\\) angeben k\u00f6nnen, die \\(G\\) erzeugt<\/p>\n<p style=\"padding-left: 30px;\">4. Und als letztes das Gleiche mit dem Sternoperator: \\(L={L_1}^{*}\\)<\/p>\n<p>Damit erzeugen rechtslineare Grammatiken mindestens alle regul\u00e4ren Sprachen.<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: mittels der Operationen Kleene Stern, Vereinigung und Konkatenation k\u00f6nnen wir aus den Mengen \\(\\emptyset\\) und \\(\\{a\\}\\) weitere regul\u00e4re Mengen erzeugen. Diese werden anschlie\u00dfend mittels passender Grammatik, die den &#8222;rechtslinearen Einschr\u00e4nkungen&#8220; unterliegt erzeugt.<\/p>\n<p>Da wir mit den drei Operationen alle regul\u00e4ren Mengen abbilden k\u00f6nnen und f\u00fcr alle dadurch erzeugten, neuen Mengen rechtslineare Grammatiken angegeben haben, k\u00f6nnen wir so sagen, dass alle regul\u00e4ren Sprachen von rechtslinearen Grammatiken erzeugt werden.<\/p>\n<h2>Lernziel 8<\/h2>\n<p style=\"padding-left: 30px;\"><em>Wie transformiert man eine rechtslineare Grammatik in eine rechtslineare Normalform?<\/em><\/p>\n<p>Zun\u00e4chst: was ist eine Normalform? Im Prinzip ist es eine Vereinfachung durch Umformung. In einer rechtslinearen Normalformgrammatik haben alle Regeln die Form:<\/p>\n<blockquote><p>\\(A\\rightarrow aB\\) oder<\/p>\n\\(A\\rightarrow\\epsilon\\)<\/blockquote>\n<p>D.h. dass einem Terminalsymbol (kann nicht weiter ersetzt werden, hier \\(a\\)) immer ein Nonterminalsymbol (kann weiter ersetzt werden, hier \\(A\\) und \\(B\\))\u00a0folgt. Die Nonterminale k\u00f6nnen also nur ersetzt werden durch ein leeres Wort \\(\\epsilon\\) oder durch die Kombination eines Terminalsymbols mit einem Nonterminalsymbol.<\/p>\n<p>Und jetzt schaut einmal kurz hoch zur Definition der rechtslinearen Grammatik: ist euch der Unterschied aufgefallen? Anstatt, dass die rechte Seite der Produktion auch Wort \\(\\omega\\) erlaubt, erlaubt uns die Normalform nur ein einziges Terminalzeichen, d.h. nur noch ein Symbol \\(a\\) auf rechten Seite.\u00a0Damit werden alle W\u00f6rter in regul\u00e4ren Grammatiken in Normalform immer nach dem selben Prinzip erzeugt: ausgehend vom Startsymbol wird jede Produktion immer ein Zeichen anf\u00fcgen und ein Nichtterminal ersetzen.\u00a0Wir verl\u00e4ngern die Zeichenkette in einem Ableitungsschritt immer nur um ein Zeichen und begrenzen es durch ein immer wechselndes Nonterminal.<\/p>\n<p>Um also eine rechtslineare Grammatik in eine rechtslineare Normalform zu transformieren werden die Terminalregeln so angepasst, dass die Grammatik terminiert, die Regeln verk\u00fcrzt und so alle Regeln eliminiert, die nicht der Normalform entsprechen (d.h. es kommt keine Regel der Forml \\(A\\rightarrow B\\) (Nonterminal zu Nonterminal, Platzhalter zu Platzhalter) vor).<\/p>\n<p>Und jetzt kommt der Grund, warum ich die Kurseinheit 5 so gerne mag: ein sehr ausf\u00fchrliches Beispiel dieser einer Transformation, dass ich hier auch gerne ausf\u00fchren w\u00fcrde:<\/p>\n<p><strong>Beispiel<\/strong>: \\(G=(\\Pi,\\Sigma,R,S)\\) mit<\/p>\n<p style=\"padding-left: 30px;\">\\(\\Pi=\\{S,A,B,C\\}\\) (unsere Nonterminale)<\/p>\n<p style=\"padding-left: 30px;\">\\(\\Sigma=\\{a,b\\}\\) (unsere Terminale)<\/p>\n<p>und folgenden Regeln \\(R\\):<\/p>\n<p style=\"padding-left: 30px;\">\\(S\\rightarrow A\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(S\\rightarrow B\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(A\\rightarrow C\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(A\\rightarrow aB\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(A\\rightarrow baaB\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(B\\rightarrow A\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(B\\rightarrow bbC\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(C\\rightarrow a\\)<\/p>\n<p>Man sieht gleich, dass das wir hier einige Regeln haben, die nicht der Normalform entsprechen. Die m\u00fcssen wir nun loswerden.<\/p>\n<p>1. Der \u00dcbersicht halber wird mit \\(\\mid\\) <strong>abgek\u00fcrzt<\/strong>:<\/p>\n<p style=\"padding-left: 30px;\">\\(S\\rightarrow A\\mid B\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(A\\rightarrow C\\mid aB\\mid baaB\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(B\\rightarrow A\\mid bbC\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(C\\rightarrow a\\)<\/p>\n<p>2. Nun k\u00fcmmern wir uns um die <strong>korrekte Terminierung<\/strong>, d.h. \\(G\\) muss die M\u00f6glichkeit bieten ein Nichtterminal durch ein leeres Wort \u00a0\\(\\epsilon\\)\u00a0zu ersetzen. Wie man sieht, ist das bei unseren Regeln nicht der Fall. Wir f\u00fcgen also eine neue Regel ein und passen die letzte Regel an damit die Terminierung auch erreichbar ist:<\/p>\n<p style=\"padding-left: 30px;\">\\(S\\rightarrow A\\mid B\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(A\\rightarrow C\\mid aB\\mid baaB\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(B\\rightarrow A\\mid bbC\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(C\\rightarrow aE\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(E\\rightarrow\\epsilon\\)<\/p>\n<p>3. Nun werden die <strong>Regell\u00e4ngen verk\u00fcrzt<\/strong>. Wir haben einige Regeln, die bestehen aus mehr Terminalen als f\u00fcr die Normalform notwendig. Wir verk\u00fcrzen also die Regeln \\(A\\rightarrow baaB\\) und \\(B\\rightarrow bbC\\) in jedem Schritt um ein Terminalsymbol indem wir ein neues Nonterminal einf\u00fchren. Das wird solange fortgef\u00fchrt bis wir in unserer Normalform landen:<\/p>\n<p style=\"padding-left: 30px;\">\\(A\\rightarrow baaB\\) wird zu<\/p>\n<p style=\"padding-left: 30px;\">\\(A\\rightarrow bX\\) und<\/p>\n<p style=\"padding-left: 30px;\">\\(X\\rightarrow aaB\\)<\/p>\n<p>Letzteres wird dann weiter transformiert zu<\/p>\n<p style=\"padding-left: 30px;\">\\(X\\rightarrow aY\\) und<\/p>\n<p style=\"padding-left: 30px;\">\\(Y\\rightarrow aB\\)<\/p>\n<p>L\u00e4nge erreicht. Das Gleiche wird mit\u00a0\\(B\\rightarrow bbC\\) durchgef\u00fchrt und wir kommen insg. zu:<\/p>\n<p style=\"padding-left: 30px;\">\\(S\\rightarrow A\\mid B\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(A\\rightarrow C\\mid aB\\mid bX\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(X\\rightarrow aY\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(Y\\rightarrow aB\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(B\\rightarrow A\\mid bZ\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(Z\\rightarrow bC\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(C\\rightarrow aE\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(E\\rightarrow\\epsilon\\)<\/p>\n<p>4. Jetzt werden nur noch die <strong>Regeln eliminiert<\/strong>, die auf Nonterminale zeigen (d.h. in der Form \\(S\\rightarrow A\\)). Dazu ersetzen wir einfach das zu eliminierende Nonterminal durch seine &#8222;Ersatzzeichenkette&#8220;. Auf der rechten Seite der Produktionen haben wir die Nonterminale \\(A,B\\) und \\(C\\), die wir ersetzen m\u00fcssen. Wir fangen zun\u00e4chst mit \\(A\\) an und ersetzen es durch seine &#8222;Ersatzzeichenkette&#8220; \\(C\\mid aB\\mid bX\\) in den Regeln \\(S\\) und \\(B\\).<\/p>\n<p style=\"padding-left: 30px;\">\\(S\\rightarrow C\\mid aB\\mid bX\\mid B\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(A\\rightarrow C\\mid aB\\mid bX\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(X\\rightarrow aY\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(Y\\rightarrow aB\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(B\\rightarrow C\\mid aB\\mid bX\\mid bZ\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(Z\\rightarrow bC\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(C\\rightarrow aE\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(E\\rightarrow\\epsilon\\)<\/p>\n<p>Nun k\u00fcmmern wir uns um \\(B\\) und ersetzen es durch seine &#8222;Ersatzzeichenkette&#8220; \\(C\\mid aB\\mid bX\\mid bZ\\)\u00a0in seinem einzigen Vorkommen in \\(S\\):<\/p>\n<p style=\"padding-left: 30px;\">\\(S\\rightarrow{C\\mid aB\\mid bX\\mid C\\mid bZ}\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(A\\rightarrow C\\mid aB\\mid bX\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(X\\rightarrow aY\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(Y\\rightarrow aB\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(B\\rightarrow{C\\mid aB\\mid bX\\mid bZ}\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(Z\\rightarrow bC\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(C\\rightarrow aE\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(E\\rightarrow\\epsilon\\)<\/p>\n<p>Fehlt nur noch \\(C\\), dass \u00fcberall auf der rechten Seite der Produktionen durch \\(aE\\) ersetzt wird und wir haben am Ende eine rechtslineare Normalform:<\/p>\n<p style=\"padding-left: 30px;\">\\(S\\rightarrow aE\\mid aB\\mid bX\\mid bZ\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(A\\rightarrow aE\\mid aB\\mid bX\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(X\\rightarrow aY\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(Y\\rightarrow aB\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(B\\rightarrow aE\\mid aB\\mid bX\\mid bZ\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(Z\\rightarrow bC\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(C\\rightarrow aE\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(E\\rightarrow\\epsilon\\)<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: bei einer rechtslinearen Grammatik gilt nur die Einschr\u00e4nkungen \\(A\\rightarrow\\omega B\\) oder \\(A\\rightarrow\\omega\\). D.h. die rechte Seite der Produktion muss aus einem Wort, welches mit einem Nonterminal abschlie\u00dft oder nur durch ein Wort bestehen. Bei der zugeh\u00f6rigen Normalform ist das nicht mehr erlaubt. Dort gelten nur noch die Regeln \\(A\\rightarrow aB\\) sowie die Abschlussregel \\(B\\rightarrow\\epsilon\\).<\/p>\n<p>Durch Verk\u00fcrzung der Produktionen, eine korrekte Terminierung mit \\(\\epsilon\\), Eliminierung der Regeln, die nicht dem genannten Schema f\u00fcr die Normalform entsprechen k\u00f6nnen wir so eine rechtslineare Grammatik in eine Normalform \u00fcberf\u00fchren.<\/p>\n<p>Und das war auch schon KE5. Wie immer gilt: Wer Fehler oder Ungenauigkeiten findet, ab in die Kommentare oder per Mail.<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Update 2: Markus hat\u00a0eine Ungenauigkeit im Lernziel 8 gefunden. Ist korrigiert,\u00a0Danke. Update: Beispiel f\u00fcr die regul\u00e4ren Ausdr\u00fccke, sowie Gleichungen f\u00fcr die Funktion aus Lernziel 5 hinzugef\u00fcgt. Ebenfalls Antworten zu allen Lernzielen verfasst. Noch drei Kurseinheiten, dann ist TIB auch schon vorbei. In dieser Kurseinheit geht es um Grammatiken. H\u00e4ufig wird in der Literatur zun\u00e4chst die &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/fernuni.digreb.net\/?p=1667\" class=\"more-link\"><span class=\"screen-reader-text\">\u201eTIB: Grammatiken und regul\u00e4re Sprachen (Lernziele KE5, Update 6)\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-1667","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\/1667","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=1667"}],"version-history":[{"count":63,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1667\/revisions"}],"predecessor-version":[{"id":3530,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1667\/revisions\/3530"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1667"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1667"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1667"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}