Стоимость запроса эквивалентности для DFA

Вдохновленный этим вопросом , мне интересно следующее:

Какова сложность наихудшего случая проверки, принимает ли данный DFA тот же язык, что и данное регулярное выражение?

Это известно? Надежда будет заключаться в том, что эта проблема в P - что есть алгоритм полинома в размере обоих.

Согласно Garey and Johnson (стр. 174), НЕУНИВЕРСАЛЬНОСТЬ РЕГУЛЯРНОГО ВЫРАЖЕНИЯ является PSPACE-полной. Это проблема принятия решения , является ли регулярное выражение над вовсе не генерирует все строки. Так что ваша проблема также PSPACE-полная.$\{0,1\}$

Вот один из способов увидеть, что проблема ОП в PSPACE. Учитывая DFA и регулярное выражение , создайте NFA для и используйте конструкцию набора мощности, чтобы фактически построить DFA эквивалентный ; мы не будем хранить в памяти, но у нас есть оракулярный доступ к с использованием только полиномиального пространства. Теперь фактически построим DFA для симметричной разности и используя конструкцию продукта. Этот DFA не принимает строки (и поэтому$A$$r$$B$$r$$C$$B$$C$$C$$D$$A$$C$$L(A) = L(r)$) если нет пути из исходного состояния в принимающее состояние. Поскольку достижимость находится в NL, а имеет размер , мы можем проверить, есть ли в , последнее равенство по теореме Савича.$D$$2^{\mathrm{poly}(n)}$$L(D) = \emptyset$$\mathrm{NSPACE}(\mathrm{poly}(n)) = \mathrm{NPSPACE} = \mathrm{PSPACE}$