grammar - BNF文法マッチング

Question

私の先生は私に2つのbnf文法を与えました：

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

そしてそれらと一致する4つの文字列：

• dffd
• dddefddfe
• dedf
• 献身

私はそれらのうちの2つを理解しましたが、他の2つは私を困惑させました。誰かに答えてもらいたくないのですが、どこが間違っているのか、誰かにヒントを教えていただければ幸いです。

Answer 1

これは文脈自由文法なので、構文木を描くことを検討する必要があります。次に、どの非終端記号がどの生成文字列につながるかを確認できます。これらの文法は非常に単純であるため、構文木を手動で描くのは非常に簡単です。

Answer 2

うーん...

帰納法により、すべての一致の文字数は奇数でなければなりません。ということで、4文字列のどちらもヒットにならない…

---

あっ、待って。最初のルールの「Y」に気付きました。それが何であるか知っていますか？それは私の議論を真っ向から破る可能性があります...

Answer 3

私のアドバイスは、コードを書く前に、自分で有限オートマトンまたは状態図を描くことです。最初に鉛筆と紙を使って手でそれを行います。