Программирование задача. Теория вычислимости

Разработайте алгоритм, который, принимая на вход описание произвольной формальной грамматики (в форме Бэкуса-Наура или аналогичной) и произвольный конечный автомат (детерминированный или недетерминированный), определяет, существует ли бесконечное множество строк, генерируемых грамматикой, которые не принимаются автоматом, и если да, то генерирует пример такой строки. Алгоритм должен иметь полиномиальную временную сложность относительно суммарного размера описания грамматики и автомата. Дополнительно, если такое множество существует, алгоритм должен определить, является ли оно рекурсивно перечислимым. Обоснуйте корректность и полиномиальную сложность предложенного алгоритма.