Considere el lenguaje , donde # es un nuevo símbolo. La complejidad NFA de M n es n . Mostraremos que su complejidad de cobertura de DFA es 2 n .Mn=ϵ+(Ln#)∗Ln#Mnn2n
Deje que sea un DFA aceptar algún lenguaje L ( A ) ⊆ M n , con función de transición q A . Llame a un estado s viable si hay alguna palabra w tal que q A ( s , w ) es un estado de aceptación. Para cualquiera de los dos estados sin falla s , t , sea A s , t = { w ∈ ( 1 + ⋯ + n ) ∗ : q AAL(A)⊆MnqAswqA(s,w)s,tNo es difícil comprobar que cada palabra w ∈ L ( A ) se puede escribir como w = w 1 # ⋯ # w l donde w i ∈ A s i , t i para algunos viables s i , t i .
As,t={w∈(1+⋯+n)∗:qA(s,w)=t}.
w∈L(A)w=w1#⋯#wlwi∈Asi,tisi,ti
Suponga que , donde cada A i es un DFA. Sea P el enrejado generado por todos los idiomas A i s , t . Podemos ver L ( A i ) como un lenguaje L P ( A i ) sobre P ∗ , el espacio entre dos símbolos correspondientes a # . Bajo este punto de vista, corresponde a PMn=⋃Ni=1L(Ai)AiPAis,tL(Ai)LP(Ai)P∗#MnP∗ .
Llame a universal si para algunos x ∈ P ∗ es el caso de que para todos y ∈ P haya z ∈ P ∗ tal que x y z ∈ L P ( A i ) . Afirmamos que algo de L P ( A i ) es universal. De lo contrario, cada L P ( A i ) contiene como máximo ( | PLP(Ai) x∈P∗y∈Pz∈P∗xyz∈LP(Ai)LP(Ai)LP(Ai) l . palabras de longitud l . En total, la L P ( A i ) debe contener todo | P | l palabras de longitud l , por lo tanto | P | l ≤ N ( | P | - 1 ) l , que se viola por lo suficientemente grande(|P|−1)llLP(Ai)|P|ll|P|l≤N(|P|−1)ll
Suponga que es universal, y escriba A = A i por brevedad. Sea x ′ ∈ P ∗ el prefijo correspondiente, y sea x ∈ M n una palabra que le corresponda. Por lo tanto, para cada y ∈ L n hay algo z y ∈ M n tal que x # y # z y ∈ L ( A iLP(Ai)A=Aix′∈P∗x∈Mny∈Lnzy∈Mn .x#y#zy∈L(Ai)
Para un subconjunto , que y S consista en las letras en S escritas en orden. Reivindicamos que las palabras x # Y S son no equivalentes para la relación Myhill-Nerode de A . De hecho, suponga S ≠ T y encuentre alguna a ∈ S ∖ T (sin pérdida de generalidad). Entonces x # y T y { 1 , ... , n } - aS⊆{1,…,n}ySSx#ySAS≠Ta∈S∖Tmientras quex#ySy { 1 , ... , n } - a #z y T y { 1 , ... , n } - a ∉Mn. Por lo tanto,Adebe tener al menos2nestados.x#yTy{1,…,n}−a#zyTy{1,…,n}−a∈L(A)x#ySy{1,…,n}−a#zyTy{1,…,n}−a∉MnA2n