Hilfe zu Grammatik

12.03.2015, 11:20	Auf diesen Beitrag antworten »
unleashed656	Hilfe zu Grammatik Hallo ich habe eine Sprache gegeben zu der ich nun eine kontextfreie Grammatik erstellen muss, nur leider komme ich nicht wirklich drauf. Die Sprache: L= {w {a, b}*\|w = a^n b^m mit 1 <= n <= m <= 2n} Ich habe schwierigkeiten mit der Bedingung 1<=n<=m<=2n. Wie kann ich die Grammatik bilden? Danke schonmal für eure Hilfe.


12.03.2015, 11:53	Auf diesen Beitrag antworten »
Karlito	Hallo unleashed656, schauen wir uns als erstes die zu erzeugende Sprache an: Die Sprache enthält mindestens das Wort ab Die Wörter sind immer eine Folge von a gefolgt von einer Folge von b Die Anzahl der b muss mindestens genauso groß sein wie die Anzahl der a Es dürfen maximal zwei mal so viele b sein wie a Entwerfen wir also eine Grammatik. Es soll eine kontextfreie Grammatik sein. D.h. auf der linken Seite der Produktionen dürfen nur einzelne Nichtterminale stehen, wohingegen auf der rechten Seite der Produktionen beliebige Abfolgen von Terminal- und Nichtterminalsymbolen sowie $[latex] \varepsilon [/latex]$ stehen dürfen. Wir wissen, dass die Anzahl der b von der Anzahl der a Abhängig ist, aber in gewisser Weise flexibel. Also erzeugen wir uns erst einmal mit n >=1, wobei B ein Nichtterminal ist und passen nachher B so an, dass die Bedinung, wie viele b es geben darf zutrifft. $[latex]<br /> S \rightarrow aSB ~\|~ aB<br /> [/latex]$ Wir wissen ja, dass die Anzahl b mindestens genau so groß sein darf wie die Anzahl a. Wenn wir also alle B durch b ersetzen würden, so hätten wir genau so viele b wie a. Wenn wir das B durch bb ersetzen, dann hätten wie genau doppelt so viele b wie a. somit hätten wir mit der Produktion $[latex] B \rightarrow b ~\|~ bb [/latex]$ alle möglichen Anzahlen b zwischen n und 2n abgedeckt. Vollständig wären die Produktionsregeln also folgende: $[latex]<br /> S & \rightarrow & aSB ~\|~ aB<br /> B & \rightarrow & b ~\|~ bb<br /> [/latex]$ Gruß, Karlito
12.03.2015, 12:12	Auf diesen Beitrag antworten »
unleashed656	Danke, perfekt erklärt

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »