BNF грамматика соответствия

Question

Мой учитель дал мне две БНФ грамматики:

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

и четыре строки для сопоставления с ними:

• dffd
• dddefddfe
• DEDF
• deded

Я разобрался с двумя из них, но два других поставили меня в тупик. Я не хочу, чтобы кто-нибудь говорил мне ответы, но если бы кто-то мог дать мне несколько советов относительно того, где я иду не так, это было бы очень ценно.

Answer 1

Это не зависящая от контекста грамматика, поэтому вы должны нарисовать дерево разбора. Затем вы можете увидеть, какой нетерминальный символ ведет к какой полученной строке. Эти грамматики довольно просты, поэтому рисование дерева разбора должно быть довольно простым делом вручную.

Answer 2

Хммм ...

По индукции все совпадения должны иметь нечетное количество символов. Так что ни одна из 4-х строк символов не может быть хитом ...

---

Ой, подожди. Я просто заметил «Y» в первом правиле. Мы знаем, что это? Это может сломать мой аргумент прямо ...

Answer 3

Мой совет - нарисовать для себя конечный автомат или диаграмму состояний, прежде чем писать какой-либо код. Сначала сделайте это вручную с помощью карандаша и бумаги.