BNF-Grammatik Matching

Question

Mein Lehrer hat mir zwei bnf Grammatiken gegeben:

A ::= 'd' | A 'e' A | A 'f' A
B ::= 'd' | B B 'e' | B B 'f'

und vier Saiten mit ihnen übereinstimmen:

• DFFD
• dddefddfe
• dedf
• DEDED

Ich habe zwei von ihnen herausgefunden, aber die anderen beiden haben mich ratlos. Ich will nicht, dass jemand mir die Antworten sagen, aber wenn jemand ein paar Tips geben könnte mir, wo ich falsch werde es würde sehr geschätzt werden.

Answer 1

Hmmm ...

Durch Induktion, alle Spiele müssen eine ungerade Anzahl von Zeichen haben. So kann weder die 4 Zeichenkette ein Hit ...

---

Oh, Moment mal. Ich habe gerade bemerkt das ‚Y‘ in der ersten Regel. Wissen wir, was das ist? Es könnte mein Argument richtig aufbricht ...

Answer 2

Dies ist eine kontextfreie Grammatik, so sollten Sie einen Parse-Baum suchen zu ziehen. Sie können dann sehen, welche Nicht-Terminal-Symbol führt zu der Zeichenfolge ergab. Diese Grammatiken sind recht einfach, so zeichnen einen Parse-Baum sollte ziemlich einfach von Hand zu tun.

Answer 3

Mein Rat wäre, einen endlichen Automaten oder Zustandsdiagramm für sich selbst zu zeichnen, bevor Sie einen Code schreiben. Tun Sie es per Hand mit einem Bleistift und Papier zuerst.