Сопоставление грамматики BNF

Question

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

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

и четыре строки, соответствующие им:

• дффд
• дддефдфе
• Дедф
• преданный

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

Answer 1

Хм...

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

---

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

Answer 2

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

Answer 3

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