Wykładniczy podział między NFA i DFA w obecności związków

Ostatnio zadano interesujące pytanie, a następnie usunięto.

W przypadku zwykłego języka jego złożoność DFA jest wielkością minimalnej akceptacji DFA, a złożoność NFA jest wielkością minimalnej akceptacji NFA. Dobrze wiadomo, że istnieje wykładnicza separacja między tymi dwoma złożonościami, przynajmniej wtedy, gdy wielkość alfabetu jest nieograniczona. W istocie, pod język nad alfabetu składa się z wszystkich słów nie zawierających wszystkie symbole. Za pomocą twierdzenia Myhill-Nerode łatwo jest obliczyć złożoność DFA . Z drugiej strony złożoność NFA wynosi tylko (jeśli dozwolonych jest wiele stanów początkowych; w przeciwnym razie jest to ). $L$ $L_n$ $\{1,\ldots,n\}$ $2^n$ $n$ $n+1$

Zainteresowane usunięty pytanie DFA obejmujące złożoność języka, który jest minimalny takie, że może być zapisany jako (niekoniecznie rozłącznych) unii języków DFA złożoności co najwyżej . Złożoność DFA obejmująca wynosi tylko . $C$ $L$ $C$ $L_n$ $2$

Czy istnieje wykładniczy podział między złożonością NFA a złożonością DFA obejmującą złożoność?

regular-languages finite-automata

— Yuval Filmus
źródło

Rozważmy język , gdzie jest nowym symbolem. Złożoność NFA wynosi . Pokażemy, że jego złożoność obejmująca DFA wynosi . $M_n = \epsilon +(L_n \#)^*L_n$ $\#$ $M_n$ $n$ $2^n$

Niech być DFA przyjmując część języka z funkcją przejścia . Nazywamy stanem opłacalne jeśli istnieje jakiś wyraz taki sposób, że jest stanem akceptacji. Dla dowolnych dwóch stanów braku awarii , niech $A$ $L(A) \subseteq M_n$ $q_A$ $s$ $w$ $q_A(s,w)$ $s,t$ Nie jest trudno sprawdzić, czy każde słowo można zapisać jako gdzie dla niektórych realnych .

A_{s, t} = {w \in (1 + \dots + n)^{*} : q_{A} (s, w) = t} .

$A_{s,t} = \{ w \in (1+\cdots+n)^* : q_A(s,w) = t \}.$

w \in L (A)

$w \in L(A)$

w = w_{1} # \dots # w_{l}

$w = w_1\# \cdots \#w_l$

w_{i} \in A_{s_{i}, t_{i}}

$w_i \in A_{s_i,t_i}$

s_{i}, t_{i}

$s_i,t_i$

Załóżmy, że , gdzie każdy jest DFA. Niech będzie siecią generowaną przez wszystkie języki . Możemy postrzegać jako język nad , odstęp między dowolnymi dwoma symbolami odpowiadający . W tym punkcie widzenia $M_n = \bigcup_{i=1}^N L(A^i)$ $A^i$ $P$ $A^i_{s,t}$ $L(A^i)$ $L_P(A^i)$ $P^*$ $\#$ $M_n$ odpowiada . $P^*$

Zadzwoń do universal, jeśli dla niektórych jest tak, że dla wszystkich istnieje takie, że . Twierdzimy, że niektóre są uniwersalne. W przeciwnym razie każdy zawiera co najwyżej $L_P(A^i)$ $x \in P^*$ $y \in P$ $z \in P^*$ $xyz \in L_P(A^i)$ $L_P(A^i)$ $L_P(A^i)$ słów o długości . W sumie musi zawierać wszystkie słowa o długości , stąd , który jest wzbudzona przez wystarczająco dużą . $(|P|-1)^l$ $l$ $L_P(A^i)$ $|P|^l$ $l$ $|P|^l \leq N (|P|-1)^l$ $l$

Załóżmy, że jest uniwersalne, i napisz dla zwięzłości. Niech będzie odpowiednim prefiksem i niech będzie jakimś odpowiadającym mu słowem. Zatem dla każdego jest trochę takich, że . $L_P(A^i)$ $A = A^i$ $x' \in P^*$ $x \in M_n$ $y \in L_n$ $z_y \in M_n$ $x\#y\#z_y \in L(A_i)$

Dla podzbioru niech składa się z liter zapisanych w kolejności. Zastrzeżenia patentowe, że słowa jest inequivalent w stosunku Myhill-Nerode z . Istotnie, przypuśćmy i znaleźć jakiś (bez straty ogólności). Następnie $S \subseteq \{1,\ldots,n\}$ $y_S$ $S$ $x\#y_S$ $A$ $S \neq T$ $a \in S \setminus T$ natomiast . Dlatego musi mieć co najmniej stanów. $x\#y_T y_{\{1,\ldots,n\} - a} \# z_{y_T y_{\{1,\ldots,n\} - a}} \in L(A)$ $x\#y_S y_{\{1,\ldots,n\} - a} \# z_{y_T y_{\{1,\ldots,n\} - a}} \notin M_n$ $A$ $2^n$

— Yuval Filmus
źródło