Geben Sie für die Sprache eine Grammatik an

Question

Frage:

Sei Sigma = {a,b,c}. Geben Sie für die folgenden Sprachen über Sigma jeweils eine Grammatik an, welche die Sprache erzeugt:

L = { w ∈ Sigma* | für alle i ∈ ℕ mit w(i) = a gibt es j ∈ ℕ sodass w(j) = b }

Meine Idee:

S -> ABCc | Cc

A -> aB | a

B -> bAb | b

Cc -> ε

ab -> ba

Könnte jemand sagen, ob das richtig ist?

Answer 1

L = { w ∈ Sigma* | für alle i ∈ ℕ mit w(i) = a gibt es j ∈ ℕ sodass w(j) = b }

Oder einfacher ausgedrückt, L ist die Sprache aller Wörter w, für die gilt:

         Wenn w ein a enthält, dann enthält es auch ein b.

Grammatik dazu:

        \(\begin{aligned} S & \to bS|cS|aP|\varepsilon\\ P & \to QbQ\\ Q & \to aQ|bQ|cQ|\varepsilon \end{aligned}\)

S -> ABCc | Cc
A -> aB | a

Dadurch fangen alle erzeugten Wörter mit a an. Das ist aber in L nicht notwendig.

ab -> ba

Das ist keine gültige Produktionsregel, weil das Wort auf der linken Seite eine Nicht-Terminalsymbol enthalten muss.

Comments

Ich komme hier nicht weiter und es wäre sehr nett, wenn sie mir weiterhelfen könnten.

L = {w ∈ {a,b}* | w enthält das Wort abba nicht}.

Es soll eine Typ 3 Grammatik sein, dennoch funktioniert meine für die Wörter ababababa und babababa nicht.

S -> ε | aA | bA | bB | aB

A -> aA | a | b | bB | aB

B -> bB | b

---

L = {w ∈ {a,b}* | w enthält das Wort abba nicht}.

L = {w ∈ {a,b}* | wenn abb gelesen wurde, dann folgt ein b oder das Wort ist zuende}.

Erstelle einen deterministischen endlichen Autmaten, der die Sprache akzeptiert. Erstelle aus dem Automaten eine Grammatik.

---

Die Aufgabe ist ja, dass ich einen NFA angeben soll. Dennoch bekomme ich probleme, wie ich längere Wörter erzeugen kann oder Wörter wie ababab oder bababa

Text erkannt:

\( \left.\begin{array}{l}151 \\ 1\end{array}\right] \)

---

Folgende Zustände:

1. Das soeben gelesene Zeichen ist ein \(a\).
2. Die zwei soeben gelesenen Zeichen sind \(ab\).
3. Die drei soeben gelesenen Zeichen sind \(abb\).
   
4. Damit das Wort verworfen wird, muss die komplette Folge \(abba\) erst noch gelesen werden.
   

---

Vielen Dank!