0 Daumen
72 Aufrufe

$$Aufgabe:\quad \\ Gib\quad die\quad Sprachen\quad L({ G }_{ 1 })\quad und\quad L({ G }_{ 2 })\quad an,\quad ohne\quad auf\quad eine\quad Grammatik\quad zu\quad verweisen:\\ Gegeben\quad sei\quad das\quad Alphabet\quad \sum { =\quad \left\{ a,b,c \right\}  } ,\quad die\quad Grammatiken\quad \\ { G }_{ 1 }=(\left\{ S,T,U,V \right\} ,\sum {  } ,{ P }_{ 1 },S)\quad und\quad { G }_{ 2 }=(\left\{ S,T \right\} ,\sum {  } ,{ P }_{ 2 },S)\quad mit\\ { P }_{ 1 }:\quad S\quad \rightarrow \quad a\quad |\quad cT\quad |\quad bV\quad \quad \quad \quad \quad \quad \\ \qquad T\quad \rightarrow \quad bbU\\ \qquad U\quad \rightarrow \quad cS\\ \qquad V\quad \rightarrow a\quad |\quad acV\\ \\ { P }_{ 1 }:\quad S\quad \rightarrow \quad b\quad |\quad ccS\quad |\quad aST\quad \quad \quad \quad \quad \quad \\ \qquad bT\quad \rightarrow \quad bbU\\ \\ Meine\quad Lösung:\\ L({ G }_{ 1 })=\left\{ { \left\{ a,(cbbc)^{ n }a,(cbbc)^{ m }(ca)^{ o }a \right\} |n,m,o∈N } \right\} \\ L({ G }_{ 2 })=\left\{ { (cc)^{ n }a^{ m }(cc)^{ o }x|n,m,o∈N\quad und\quad x∈{ \left\{ b,bb \right\}  } } \right\} \\ \qquad$$


Es wäre sehr nett, wenn mir Jemand bei der Lösung helfen würde, ich glaube sie ist komplett falsch.

LG

Gabba

von

keiner eine Idee?

Wie kommst du auf deine Lösung?

Was hat es mit P_(2) auf sich?

Du hast zwei P_(1) aufgeführt. Ist das Absicht?

Woher kommt (cc)^(o) ? Anscheinend meinst du nicht Null mit o.

Dadurch, dass die Sprache L(G1), obwohl nicht offensichtlich, eine Chomsky Typ-3 Sprache ist (Reguläre Sprache). Du hast bereits die Zustandsübergangsfunktion P gegeben, am besten du zeichnest ein DEA, da siehst du die Wörter schneller als in der Produktionsschreibweise.

Die Sprache L(G2) ist kontextsensitiv, also Typ-1 Sprache, da müsstest du eine Turing-Maschine zeichnen, wobei hier das Ablesen in der Produktionsschreibweise recht einfach ist. Eine Sache ist aber falsch. Die Produktion bT -> bbU bei G2 verweist auf ein nicht beschriebenes Nonterminal U.

Bitte logge dich ein oder registriere dich, um die Frage zu beantworten.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...