требования:
- парсер
- удаление e-нетерминалов (причем, грамматика пустых слов может быть корректно обработана)
- удаление непораждающих и недостижимых
- приведение к нормальной форме хомского (для пересечения с регулярным)
- построение пересечения с регулярным языком
- выявление циклических зависимостей между нетерминалами, выявление терминалов, переписывающихся только в строки (короче, граф зависимостей построить)
- перечечение с другой кфг (для задачи 4)
требования:
- нормализация
- построение автомата брзозовски (детерменированного!!!)
- нахождение всех подрегулярных языков
- проверка на вложение одного языка в другой -> проверка на эквивалентность
- проверка принадлежности слова языку
- Парсится грамматика
- Удаляются e-правила (нетерминалы, раскрывающиеся только в пустые строки)
- Удаляются непорождающие и недостижимые нетерминалы
- Строится множество взаимно-нерекурсивных нетерминалов.
Здесь языки линейные (т.е. ровно с 1 нетерминалом в правой части), но может быть несколько вложенных подвыводов (с чёткой границей саморекурсивного фрагмента слева и справа). Т.е. левая и правая части будут четко разделены