 Kontextfreie Grammatik entwerfen |
Jannes
unregistriert
 |
|
|
31.03.2015 00:09 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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]](http://www.matheboard.de/latex2png/latex2png.php?L = \{a^{2k}\})
- 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]](http://www.matheboard.de/latex2png/latex2png.php?<br />
L = \{ a^{(m+n)}b^na^{m} \} <br />
)
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]](http://www.matheboard.de/latex2png/latex2png.php?<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 />
)
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
|
|
|
31.03.2015 13:34 |
|
|
|
