0 Daumen
727 Aufrufe

Stimmen meine Lösungen zum finden einer Sprache zu einer Grammatik ?

Aufgabe:

$$ \text{Gib die Sprachen } L({ G }_{ 1 }) und L({ G }_{ 2 }) \text{an, ohne auf eine Grammatik zu 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.

Avatar von

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.

1 Antwort

0 Daumen

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.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community