Quão pequeno pode ser um NFA, em comparação com o mínimo Automated Unite ambíguo (UFA) do mesmo idioma regular?

Os autômatos finitos inequívocos (UFA) são tipos especiais de autômatos finitos não determinísticos (NFA).

Um NFA é chamado inequívoco se cada palavra tiver no máximo um caminho de aceitação.$w\in \Sigma^*$

Isto significa .$DFA\subset UFA\subset NFA$

Resultados conhecidos de autômatos relacionados:

1. A minimização de NFA é PSPACE-Complete.
2. A minimização de NFA em idiomas finitos é DP-Hard .
3. A minimização do UFA é NP-Complete .
4. Existem NFAs que são exponencialmente menores que os DFAs mínimos . (Além disso, existem UFAs que são exponencialmente menores que os DFAs mínimos - RB).

A questão é: podemos encontrar uma linguagem regular tal forma que exista uma NFA que aceite L, que seja exponencialmente menor (em termos de estado) do que a UFA mínima para L ? Isso pode acontecer para um idioma finito?$L$$L$$L$

Acredito que esse (finito) exista, mas minha prova atualmente depende da hipótese do tempo exponencial para sustentar, e fiquei imaginando se alguém tem uma prova que não depende dela.$L$

Além disso, alguém pode caracterizar o conjunto de idiomas para os quais existe essa diferença de tamanho?

EDIT: @Shaull deu um bom link para um artigo sobre linguagem infinita. Alguém sabe um resultado semelhante para uma linguagem finita?

Penso que o artigo IJFCS'05 de Leung: A complexidade descritiva do nfa de ambiguidade diferente fornece um exemplo com uma família de NFA que aceita linguagens finitas que envolvem uma explosão exponencial de "desambiguação" (na prova do Teorema 5).

Além disso, esses autômatos têm uma estrutura especial (DFA com vários estados iniciais).

Há ainda um resultado mais forte que o seu pedido:

Existem NFAs exponencialmente ambíguos para os quais os NFAs polinomialmente ambíguos mínimos são exponencialmente maiores e, em particular, os UFAs mínimos.

Confira este artigo de Hing Leung.