Kontextfreie Grammatik entwerfen

31.03.2015, 00:09	Auf diesen Beitrag antworten »
Jannes	Kontextfreie Grammatik entwerfen Hallo, ich brauche bei folgender Aufgabe Hilfe, weil ich einfach nicht weiß, wie ich vorgehen soll. Ich hab auch überhaupt keinen Ansatz, wie ich da an die Lösung komme. Bin über jede Hilfe dankbar. Gruß, Jannes


31.03.2015, 13:34	Auf diesen Beitrag antworten »
Karlito	Hallo Jannes, ich habe auch eine Weile nachdenken müssen. Rein intuitiv ist ja schon einmal klar, dass es eine kontextfreie Grammatik geben muss, da man relativ leicht einen Kellerautomaten konstruieren kann, welcher die Sprache akzeptiert. D.h. es muss eine kontextfreie Grammatik geben. Nur wie man diese erstellt ist ein wenig kniffelig. Tragen wir unser wissen zusammen: Es ist das leere Wort in der Sprache, wenn k=0 und n=0 sind. Wenn n = 0, dann ist die Sprache $[latex]L = \{a^{2k}\}[/latex]$ Wenn n > 0, dann gibt es n mehr a am Anfang als am Ende. Man kann die Sprache also auch folgendermaßen auffassen: $[latex]<br /> L = \{ a^{(m+n)}b^na^{m} \} <br /> [/latex]$ Das macht uns die Erstellung der Grammatik ein wenig einfacher. $[latex]<br /> \begin{array}{rcll}<br /> S & \rightarrow & \varepsilon & \text{ Das leere Wort ist in der Sprache und Terminierung für } n = 0 \text{ und } m > 0<br /> S & \rightarrow & aSa & \text{ für } n = 0<br /> S & \rightarrow & aBb & \text{ für } n = 1<br /> B & \rightarrow & aBb & \text{ für } n > 1<br /> B & \rightarrow & \varepsilon & \text{ Terminierung für } n \neq 0<br /> \end{array}<br /> [/latex]$ Bis man selbst auf solche Lösungen kommt, braucht es etwas Übung und Kreativität. Es gibt sicher noch andere korrekte Lösungen. Die Begründung, warumdiese Grammatik korrekt ist, sollte dir jetzt nicht allzu schwer fallen. Falls noch etwas unklar ist, bitte nachfragen. Gruß, Karlito

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »