---

Geschrieben von sk12345 am 17.04.2016 um 11:55:

  kontextfreie Grammatik

Meine Frage:
Gegeben ist folgende kontextfreie Grammatik G mit Startsymbol S:
S -> AB
A -> aAbb|c
B -> cB|dB|e (e ist in diesem Fall epsilon)

Ist

aacbbbbc

ableitbar?

Wenn es geht muss ich auch eine Ableitung angeben. Kann mir jemand helfen?


Meine Ideen:
Vielleicht wäre auch ein Ableitungsbaum hilfreich, weil verstehen tue ich es nicht.

---

Geschrieben von eulerscheZahl am 17.04.2016 um 13:09:

 

Sagt dir der CYK Algorithmus etwas?

---

Geschrieben von sk12345 am 17.04.2016 um 13:26:

 

Ne leider nicht.

---

Geschrieben von eulerscheZahl am 17.04.2016 um 13:31:

 

Egal, dann argumentiere ich anders:
Der erste Schritt ist klar: S -> AB
Das A kann jetzt entweder zu aAbb oder zu c werden. Da das herzuleitende Wort mit a anfängt, muss es aAbb sein.
AB -> aAbbB -> aaAbbbbB
jetzt brauchst du ein c, also: aaAbbbbB -> aacbbbbB
Fehlt noch ein c am Ende. Mit B -> cB geht das: aacbbbbcB. Das B kriegst du durch den Epsilonübergang weg, also ist aacbbbbc ableitbar.

---

Geschrieben von sk12345 am 17.04.2016 um 13:39:

 

Vielen Dank

---

Geschrieben von sk12345 am 17.04.2016 um 14:49:

 

ich habe jetzt cdc abgeleitet mit G und S, stimmt es so:

S-> AB -> cB -> cdB -> cdcB -> cdc

---

Geschrieben von eulerscheZahl am 17.04.2016 um 20:19:

 

Ja, das passt so.