Насколько маленьким может быть NFA по сравнению с минимальным однозначным конечным автоматом (UFA) того же обычного языка?

Однозначные конечные автоматы (UFA) - это особый тип недетерминированных конечных автоматов (NFA).

NFA называется однозначным, если каждое слово имеет не более одного приемлемого пути.$w\in \Sigma^*$

Это означает , что .$DFA\subset UFA\subset NFA$

Известные связанные результаты автоматов:

1. Минимизация NFA - PSPACE-Complete.
2. Минимизация NFA над конечными языками - DP-Hard .
3. Минимизация УФА является NP-Complete .
4. Существуют NFA, которые экспоненциально меньше минимальных DFA . (Также - существуют UFA, которые экспоненциально меньше минимальных DFA - RB).

Вопрос в том, можем ли мы найти обычный язык такой, что существует NFA, принимающий L, который экспоненциально меньше (по состоянию), чем минимальный UFA для L ? Может ли это произойти для конечного языка?$L$$L$$L$

Я полагаю, что такая (конечная) существует, но мое доказательство в настоящее время опирается на гипотезу об экспоненциальном времени, и мне было интересно, есть ли у кого-то доказательство, которое не полагается на него.$L$

Кроме того, кто-то может охарактеризовать набор языков, для которых существует такая разница в размерах?

РЕДАКТИРОВАТЬ: @Shaull дал хорошую ссылку на документ, посвященный бесконечному языку. Кто-нибудь знает подобный результат для конечного языка?

Я думаю, что статья IJFCS'05 Люнга: Сложность описания nfa различной неоднозначности дает пример с семейством NFA, принимающим конечные языки, которые включают экспоненциальный разрыв для «устранения неоднозначности» (в доказательстве теоремы 5).

Более того, эти автоматы имеют специальную структуру (DFA с несколькими начальными состояниями).

Есть даже более сильный результат, чем ваш запрос:

Существуют экспоненциально неоднозначные NFA, для которых минимальные полиномиально неоднозначные NFA экспоненциально больше, и, в частности, минимальные UFA.

Проверьте эту статью Хинг Леунг.