Jak mały może być NFA w porównaniu z minimalnym jednoznacznym automatem skończonym (UFA) tego samego języka regularnego?

Jednoznaczne automaty skończone (UFA) są specjalnym typem niedeterministycznych automatów skończonych (NFA).

NFA jest nazywany jednoznacznym, jeśli każde słowo ma co najwyżej jedną ścieżkę akceptującą.$w\in \Sigma^*$

Oznacza to, .$DFA\subset UFA\subset NFA$

Znane powiązane wyniki automatów:

1. Minimalizacja NFA jest kompletna z PSPACE.
2. Minimalizacja NFA w stosunku do języków skończonych to DP-Hard .
3. Minimalizacja UFA jest NP-Complete .
4. Istnieją NFA, które są wykładniczo mniejsze niż minimalne DFA . (Również - istnieją UFA, które są wykładniczo mniejsze niż minimalne DFA - RB).

Pytanie brzmi: czy możemy znaleźć zwykły język taki, że istnieje NFA akceptujący L, który jest wykładniczo mniejszy (pod względem stanu) niż minimalny UFA dla L ? Czy może się to zdarzyć w przypadku skończonego języka?$L$$L$$L$

Wierzę, że taki (skończony) istnieje, ale mój dowód opiera się obecnie na hipotezie wykładniczej czasu i zastanawiałem się, czy ktoś nie ma dowodu, który na nim nie polega.$L$

Czy ktoś może scharakteryzować zestaw języków, dla których istnieje taka różnica wielkości?

EDYCJA: @Shaull podał miły link do artykułu na temat nieskończonego języka. Czy ktoś zna podobny wynik dla skończonego języka?

Myślę, że artykuł IJFCS'05 autorstwa Leunga: opisowa złożoność nfa o różnej dwuznaczności stanowi przykład z rodziną NFA akceptującą skończone języki, które wiążą się z wykładniczym powiększeniem „disambiguation” (w dowodzie Twierdzenia 5).

Ponadto automaty te mają specjalną strukturę (DFA z wieloma stanami początkowymi).

Jest nawet silniejszy wynik niż twoja prośba:

Istnieją wykładniczo niejednoznaczne NFA, dla których minimalne wieloznacznie niejednoznaczne NFA są wykładniczo większe, w szczególności minimalne UFA.

Sprawdź ten artykuł autorstwa Hing Leung.