Wie kann ich diese kontextfreie Grammatik erzeugen?
Die Kontextfreie Grammatik, die erzeugt werden soll ist: "zwischen zwei a´s liegt immer eine gerade Anzahl von b´s"
Jetzt weiß ich aber nicht, wie das funktionieren soll, denn auch ab oder abbabbaaaa wäre in der Sprache enthalten, wie kann ich a´s spammen aber so, dass zwischen zwei a´s nur gerade Mengen von b. enthalten sind. Ebenso für ba, bbba uns.?
2 Antworten
Schreibe das Ganze zuerst als regulären Ausdruck: „b*(a(bb)*)*b?“. Daraus kannst Du die Grammatik fast wörtlich ablesen.
Du erlaubst eine Kombination aus a's und dem Nichtterminal X, sodass die beiden Enden des Wortes a's sind (oder alternativ eine beliebige anzahl von a's oder b's, je nachdem wie man die Aufgabe versteht). Und evtl., auch je nachdem wie man die Aufgabe versteht, zwischen zwei a's immer ein X liegt.
Das Terminal X ersetzt du dann durch eine gerade Anzahl an b's. Beispielsweise so:
X -> bXb | bb;