Здравствуйте, Pzz, Вы писали:
Pzz>Синклер, наверное, рассчитывал, что эта задача проще задачи проверки эквиавалентности ДКА. А оказывается, сложнее.
Нет, не рассчитывал. У нас задача как раз такая, что нужно уметь сравнивать языки, и именно что на нестрогое неравенство.

Pzz>А что, если построить третий автомат, объединяющий первые два, и все три минимизировать? Тогда если третий, объединенный, автомат сведется к какому-то из двух исходных, то тот, к которому сведется, он то ли, как раз, искомый, то ли наоборот — это надо подумать. А если не сведется, то ответ точно отрицательный.
Ну, алгоритм, предложенный копилотом, выглядит на первый взгляд работоспособным.
Дальше надо смотреть — либо ваша идея изоморфна копилотовской с точностью до порядка действий, либо у одной из них будет более хорошая асимптотика/коэффициенты при О-оценках.