Informatik 12/13 (G9)

Die Sprache L über dem Alphabet A = {x, y, -} bestehe aus dem leeren Wort sowie aus allen Wörtern, die mit x oder y starten, mit x oder y enden und die immer abwechselnd einen Buchstaben und einen Bindestrich enthalten, also z.B. x, y, y-y, x-y-y-x-x-y-y Erstellen Sie eine Grammatik, die L beschreibt.

Die Grammatik G = (A, V, P, S) besteht aus

1. dem Alphabet A = { x, y }
2. der Menge der Nichtterminale V = { S, Buchstabe, BuchstabeStrich }
3. dem Startsymbol S = Wort
4. den folgenden Produktionsregeln:

Wort = Ɛ | { BuchstabeStrich } Buchstabe
Buchstabe = "x" | "y"
BuchstabeString = Buchstabe "-"