kontextfreie Grammatik |
| 17.04.2016, 11:55 | Auf diesen Beitrag antworten » |
| sk12345 | 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. |
|
|
|
| 17.04.2016, 13:09 | Auf diesen Beitrag antworten » |
| eulerscheZahl | Sagt dir der CYK Algorithmus etwas? |
| 17.04.2016, 13:26 | Auf diesen Beitrag antworten » |
| sk12345 | Ne leider nicht. 
|
| 17.04.2016, 13:31 | Auf diesen Beitrag antworten » |
| eulerscheZahl | 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. |
| Anzeige | |
|
|
|
| 17.04.2016, 13:39 | Auf diesen Beitrag antworten » |
| sk12345 | Vielen Dank |
| 17.04.2016, 14:49 | Auf diesen Beitrag antworten » |
| sk12345 | ich habe jetzt cdc abgeleitet mit G und S, stimmt es so: S-> AB -> cB -> cdB -> cdcB -> cdc |
| 17.04.2016, 20:19 | Auf diesen Beitrag antworten » |
| eulerscheZahl | Ja, das passt so. |
|
|
