Kontextfreie Grammatik finden

Question

Frage:

Text erkannt:

b) \( L_{2}=\left\{w \in\{a, b\}^{*} \mid\right. \) für jedes Präfix \( p \) von \( w \) gilt: \( \left.N_{a}(p) \geq N_{b}(w)\right\} \)

Gesucht ist eine kontextfreie Grammatik, die diese Sprache erzeugt.

Meine Idee

G = ( {S} , {a,b} , S , {S --> aSb | aSa | aa | ab | e} )

So ist das Präfix p ∈ {a}* und nicht p ∈ { a , b }*

Könnte mir bitte jemand behilflich sein :(

Comments

Steht N für "Nachfolger"?

Wie ist das Ungleichheitzeichen zu lesen?

Sprache über dem Alphabet {a,b} , w sind die Wörter? So zu lesen?

---

So wie ich das verstehe, bezeichnet N_{a}(p) die Anzahl der Vorkommen von a in p , Nb(w) die Anzahl der Vorkommen von b in w (w ∈ { a , b }*) .

---

Für ein Wort v ∈ A* gilt : p*v = w

Answer 1

für jedes Präfix \( p \) von \( w \) gilt: \( N_{a}(p) \geq N_{b}(w) \)

Sei \(w\in L_2\) und \(p = \varepsilon\).

Dann ist \(p\) Präfix von \(w\).

Wegen \( N_{a}(p) = 0\) und \(N_{a}(p) \geq N_{b}(w) \) ist \(N_{b}(w) = 0\).

Also ist \(L_2 = \{a\}^*\).

Comments

Gesucht ist eine kontextfreie Grammatik, die diese Sprache L2 erzeugt. L2 ist schon in der Aufgabe definiert :(

---

Soll das heißen du kannst auch für die Sprache \(\{a\}^*\) keine kontextfreie Gramatik angeben?