0 Daumen
654 Aufrufe

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?

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort
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.

Avatar von 5,6 k

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] \)

SmartSelect_20210505-150137_Samsung Notes.jpg

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!

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community