Hallo,
konstruieren Sie eine kontextfreie Grammatik, mit der folgenden Sprache L.
L= {0^nx1^m | m, n ∈ N0}
Beispiele für Wörter dieser Grammatik: 0000000x111 oder 00x1111 oder auch nur x. Zwischen den Nullen und den Einsen steht also immer ein x. Die Anzahl der Nullen und Einsen stammt aus den natürlichen Zahlen, inkl. der 0.
Ich habe das wie folgt gelöst:
A -> CBD
B -> x
C -> ϵ | CC | 0
D -> ϵ | DD | 1
Kann mir jemand sagen, ob das so richtig ist?
Hallo,
deine Grammatik ist kontextfrei und erzeugt die gegebene (im übrigen reguläre) Sprache. Also sollte das richtig sein. Ich meine, mich erinnern zu können, dass kontextfreie Grammatiken keine verkürzenden Produktionen enthalten dürfen (also keine Epsilon-Ableitungen). Schau da noch mal in deinem Skript nach.
Ansonsten kann man das ganze auch etwas kompakter schreiben, wenn man will. Denke bitte daran, dass die Grammatik aus einem Tupel besteht (Terminalsymbole, Nichtterminalsymbole, Startsymbol, Regeln). Die Regeln allein beschreiben die Grammatik nur ungenügend.
Eine äquivalente, aber kürzere Grammatik wäre demzufolge:
G = ({0, 1, x}, {S, A, B}, S, {
S -\> AxB
A -\> A0 | ε
B -\> B1 | ε
})
Nico
Ah super, leuchtet ein. Herzlichen Dank für die Antwort! 