Я сходу не нашёл решения, может кто навскидку знает, куда копать?
Вкратце, ситуация следующая.
Допустим, у нас есть некоторая грамматика (G1), заданная через НКА.
Теперь у нас есть некоторая другая грамматика (G2), тоже заданная через НКА.
Если бы нас интересовала эквивалентность, то мы бы её проверили за полиномиальное время через минимизацию ДКА и их эквивалентность.
Но нас интересует нестрогая эквивалентность: L1>=L2. Т.е. предполагаем, что G2 описывает подъязык языка G1. Быть может, полный, а может быть, и нет.
Есть ли алгоритм, который это проверяет?