0 Daumen
16 Aufrufe

Frage:

blob.png

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 :(

vor von
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

1 Antwort

0 Daumen
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\}^*\).

vor von 3,6 k

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?

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community