---

Geschrieben von unleashed656 am 12.03.2015 um 11:20:

  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.

---

Geschrieben von Karlito am 12.03.2015 um 11:53:

 

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 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.



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 alle möglichen Anzahlen b zwischen n und 2n abgedeckt.

Vollständig wären die Produktionsregeln also folgende:


Gruß,

Karlito

---

Geschrieben von unleashed656 am 12.03.2015 um 12:12:

 

Danke, perfekt erklärt