Мой учитель дал мне две грамматики BNF:
A ::= 'd' | A 'e' A | A 'f' A
B ::= 'd' | B B 'e' | B B 'f'
и четыре строки, соответствующие им:
Я вычислил двух из них, но два других поставили меня в тупик. Я не хочу, чтобы кто-нибудь говорил мне ответы, но если бы кто-нибудь мог мне подсказать, в чем я ошибаюсь, я был бы очень признателен.
Хм...
По индукции все совпадения должны содержать нечетное количество символов. Так что ни одна из 4-х символьных строк не может быть хитом ...
Ой, погоди. Я только что заметил букву «Y» в первом правиле. Мы знаем, что это такое? Это могло бы сломать мой аргумент ...
Это контекстно-свободная грамматика, поэтому вы должны попытаться нарисовать дерево синтаксического анализа. Затем вы можете увидеть, какой нетерминальный символ ведет к какой полученной строке. Эти грамматики довольно просты, поэтому рисование дерева синтаксического анализа должно быть довольно простым делом вручную.
Я бы посоветовал вам нарисовать для себя конечный автомат или диаграмму состояний, прежде чем писать какой-либо код. Сначала сделайте это вручную, используя карандаш и бумагу.
