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 .L C L $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ść?

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

Niech być DFA przyjmując część języka L ( A ) ⊆ M n z funkcją przejścia q A . Nazywamy stanem s opłacalne jeśli istnieje jakiś wyraz w taki sposób, że q ( s , w ) jest stanem akceptacji. Dla dowolnych dwóch stanów braku awarii s , t , niech A s , t = { w ∈ ( 1 + ⋯ + n ) ∗ : q A$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 w ∈ L ( A ) można zapisać jako w = w 1 # ⋯ # w l gdzie w i ∈ A s i , t i dla niektórych realnych s i , t i .

$$A_{s,t} = \{ w \in (1+\cdots+n)^* : q_A(s,w) = t \}.$$ $w \in L(A)$$w = w_1\# \cdots \#w_l$$w_i \in A_{s_i,t_i}$$s_i,t_i$

Załóżmy, że , gdzie każdy A i jest DFA. Niech P będzie siecią generowaną przez wszystkie języki A i s , t . Możemy postrzegać L ( A i ) jako język L P ( A i ) nad P ∗ , odstęp między dowolnymi dwoma symbolami odpowiadający # . W tym punkcie widzenia M $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 x ∈ P ∗ jest tak, że dla wszystkich y ∈ P istnieje z ∈ P ∗ takie, że x y z ∈ L P ( A i ) . Twierdzimy, że niektóre L P ( A i ) są uniwersalne. W przeciwnym razie każdy L P ( A i ) 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 l . W sumie L P ( A i ) musi zawierać wszystkie | P | l słowa o długości l , stąd | P | l ≤ N ( | p | - 1 ) L , który jest wzbudzona przez wystarczająco dużą l .$(|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 A = A i dla zwięzłości. Niech x ′ ∈ P ∗ będzie odpowiednim prefiksem i niech x ∈ M n będzie jakimś odpowiadającym mu słowem. Zatem dla każdego y ∈ L n jest trochę z y ∈ M n takich, że x # y # z y ∈ L ( A i ) .$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 y S składa się z liter S zapisanych w kolejności. Zastrzeżenia patentowe, że słowa x # y S jest inequivalent w stosunku Myhill-Nerode z A . Istotnie, przypuśćmy S ≠ T i znaleźć jakiś A ∈ S ∖ T (bez straty ogólności). Następnie x # y T y { 1 , … , n } - $S \subseteq \{1,\ldots,n\}$$y_S$$S$$x\#y_S$$A$$S \neq T$$a \in S \setminus T$ natomiast x # y S y { 1 , … , n } - a # z y T y { 1 , … , n } - a ∉ M n . Dlatego A musi mieć co najmniej 2 n 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$