Exponentielle Trennung zwischen NFAs und DFAs in Gegenwart von Gewerkschaften

Kürzlich wurde eine interessante Frage gestellt und anschließend gelöscht.

Für eine reguläre Sprache ist ihre DFA-Komplexität die Größe des minimalen DFA, der sie akzeptiert, und ihre NFA-Komplexität ist die Größe des minimalen NFA, der sie akzeptiert. Es ist bekannt, dass es eine exponentielle Trennung zwischen den beiden Komplexitäten gibt, zumindest wenn die Größe des Alphabets nicht begrenzt ist. Betrachten Sie in der Tat die Sprache über dem Alphabet die aus allen Wörtern besteht, die nicht alle Symbole enthalten. Mit dem Myhill-Nerode-Theorem ist es einfach, die DFA-Komplexität zu berechnen . Andererseits ist die NFA-Komplexität nur $L$ $L_n$ $\{1,\ldots,n\}$ $2^n$ $n$ (Wenn mehrere Anfangszustände zulässig sind, andernfalls ist es ). $n+1$

Die gestrichene Frage betraf den DFA, der die Komplexität einer Sprache abdeckt , wobei es sich um das minimale , sodass als (nicht notwendigerweise disjunkte) Vereinigung von Sprachen mit DFA-Komplexität höchstens . Die DFA, die die Komplexität von abdeckt, beträgt nur . $C$ $L$ $C$ $L_n$ $2$

Gibt es eine exponentielle Trennung zwischen NFA-Komplexität und DFA-Komplexität?

regular-languages finite-automata Yuval Filmus
quelle

Antworten:

Betrachten Sie die Sprache , wobei ein neues Symbol ist. Die NFA-Komplexität von ist . Wir werden zeigen, dass der DFA, der die Komplexität abdeckt, beträgt . $M_n = \epsilon +(L_n \#)^*L_n$ $\#$ $M_n$ $n$ $2^n$

Sei ein DFA, der eine Sprache mit der Übergangsfunktion akzeptiert . Rufe einen Zustand lebensfähig , wenn es einig Wort , so daß ist ein akzeptierende Zustand. Für zwei beliebige Nicht-Fehlerzustände sei $A$ $L(A) \subseteq M_n$ $q_A$ $s$ $w$ $q_A(s,w)$ $s,t$ Es ist nicht schwer zu überprüfendass jedes Wort kann geschrieben werden wo für einige lebensfähig .

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$

$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$ $P^*$

$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)$ $(|P|-1)^l$ $l$ $L_P(A^i)$ $|P|^l$ $l$ $|P|^l \leq N (|P|-1)^l$ $l$

$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)$

$S \subseteq \{1,\ldots,n\}$ $y_S$ $S$ $x\#y_S$ $A$ $S \neq T$ $a \in S \setminus T$ $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
quelle