Condiciones para la universalidad NFA

Considere un autómata finito no determinista y una función f (n) . Además definimos \ Sigma ^ {\ leq k} = \ bigcup_ {i \ leq k} \ Sigma ^ i .$A = (Q, \Sigma, \delta, q_0, F)$$f(n)$$\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i$

Ahora analicemos la siguiente declaración:

Si , entonces .$\Sigma^{\leq f(|Q|)} \subseteq L(A)$$L(A) = \Sigma^*$

Es fácil mostrar que para es cierto, por lo tanto, si el autómata produce cada palabra con una longitud de hasta , entonces produce .$f(n) = 2^n+1$$2^{|Q|}+1$$\Sigma^*$

¿Pero aún se mantiene si es un polinomio?$f$

Si no, ¿cómo podría ser una construcción de un NFA para un polinomio dado , st ?$A$$p$$\Sigma^{\leq p(|Q|)} \subseteq L(A) \subsetneq \Sigma^*$

Para que la declaración se mantenga, f debe crecer exponencialmente, incluso con el alfabeto unario.

[Editar: El análisis se mejora ligeramente en la revisión 2.]

Aquí hay un boceto de prueba. Suponga que la declaración se cumple y deja que f sea ​​una función tal que cada NFA con como máximo n estados que acepte todas las cadenas con longitud como máximo f ( n ) acepte todas las cadenas en absoluto. Demostraremos que por cada C > 0 y n suficientemente grande , tenemos f ( n )> 2 ^{C ⋅√ n} .

El teorema del número primo implica que para cada c <lg e y para k suficientemente grande , hay al menos c ⋅2 ^k / k primos en el rango [2 ^k , 2 ^{k +1} ]. Tomamos c = 1. Para tal k , deje N _k = ⌈2 ^k / k ⌉ y defina un NFA M _{k de la} siguiente manera. Sea p ₁ ,…, p _{N k} primos distintos en el rango [2 ^k , 2 ^{k +1}] El NFA M _k tiene S _k = 1 + p ₁ +… + p _{N k} estados. Además del estado inicial, los estados se dividen en N _k ciclos donde el i ésimo ciclo tiene una longitud p _i . En cada ciclo, todos menos un estado son estados aceptados. El estado inicial tiene N _k bordes salientes, cada uno de los cuales va al estado inmediatamente después del estado rechazado en cada ciclo. Finalmente, también se acepta el estado inicial.

Sea P _k el producto p ₁ ... p _{N k} . Es fácil ver que M _k acepta todas las cadenas de longitud menor que P _k pero rechaza la cadena de longitud P _k . Por lo tanto, f ( S _k ) ≥ P _k .

Tenga en cuenta que S _k ≤ 1 + N _k ⋅2 ^{k +1} = o (2 ^{2 k} ) y que P _k ≥ (2 ^k ) ^{N _k} ≥ 2 ^{2 k} . El resto es estándar.

EDITAR AL 10/12/06:

ok, esta es la mejor construcción que puedo obtener, mira si alguien tiene mejores ideas.

Teorema. Para cada Hay un estados NFA sobre alfabetos con modo que la cadena más corta que no está en es de longitud .$n$$(5n+12)$$M$$\Sigma$$|\Sigma|=5$$L(M)$$(2^n-1)(n+1)+1$

Esto nos dará .$f(n) = \Omega(2^{n/5})$

La construcción es más o menos la misma que la de Shallit , excepto que primero construimos un NFA directamente en lugar de representar el lenguaje mediante una expresión regular. Dejar

$\Sigma = \{{0 \brack 0},{0 \brack 1},{1 \brack 0},{1 \brack 1},\sharp\}$ .

Para cada , vamos a construir un lenguaje de reconocimiento NFA , donde es la siguiente secuencia (tome por ejemplo):$n$$\Sigma^*-\{s_n\}$$s_n$$n=3$

$s_3 = \sharp{0 \brack 0}{0 \brack 0}{0 \brack 1}\sharp{0 \brack 0}{0 \brack 1}{1 \brack 0}\sharp \ldots \sharp{1 \brack 1}{1 \brack 1}{0 \brack 1}\sharp$ .

La idea es que podemos construir un NFA consta de cinco partes;

• un iniciador , que asegura que la cadena comience con ;$\sharp{0 \brack 0}{0 \brack 0}{0 \brack 1}\sharp$
• un terminador , que garantiza que la cadena termine con ;$\sharp{1 \brack 1}{1 \brack 1}{0 \brack 1}\sharp$
• un contador , que mantiene el número de símbolos entre dos 's como ;$\sharp$$n$
• un verificador add-one , que garantiza que solo aparezcan símbolos con la forma ; finalmente,$\sharp{x \atop x+1}\sharp$
• un verificador consistente , que garantiza que solo los símbolos con la forma puedan aparecer simultáneamente.$\sharp{x \atop y}\sharp{y \atop z}\sharp$

Tenga en cuenta que queremos aceptar lugar de , por lo que una vez que descubramos que la secuencia de entrada está desobedeciendo uno de los comportamientos anteriores, aceptamos la secuencia de inmediato. De lo contrario, después depasos, el NFA estará en el único estado de rechazo posible. Y si la secuencia es más larga que, la NFA también acepta. Por lo tanto, cualquier NFA satisface las cinco condiciones anteriores solo rechazará .$\Sigma^*-\{s_n\}$$\{s_n\}$$|s_n|$$|s_n|$$s_n$

Puede ser fácil verificar la siguiente figura directamente en lugar de una prueba rigurosa:

Comenzamos en el estado superior izquierdo. La primera parte es el iniciador y el contador, luego el verificador consistente, el terminador, finalmente el verificador de agregar uno. Todo el arco sin nodos terminales apunta al estado inferior derecho, que es un aceptador de todos los tiempos. Algunos de los bordes no están etiquetados debido a la falta de espacios, pero se pueden recuperar fácilmente. Una línea de trazos representa una secuencia de estados con aristas.$n-1$$n-2$

Podemos (dolorosamente) verificar que la NFA rechaza solamente, ya que sigue las cinco reglas anteriores. Por lo tanto, se ha construido un NFA de estado con , que satisface el requisito del teorema.$s_n$$(5n+12)$$|\Sigma|=5$

Si hay alguna falta de claridad / problema con la construcción, deje un comentario e intentaré explicarlo / solucionarlo.

Esta pregunta ha sido estudiada por Jeffrey O. Shallit et al., Y de hecho el valor óptimo de todavía está abierto para . (En cuanto al lenguaje unario, vea los comentarios en la respuesta de Tsuyoshi )$f(n)$$|\Sigma|>1$

En la página 46-51 de su charla sobre universalidad , proporcionó una construcción tal que:

Teorema. Para para algunos suficientemente grandes, hay una NFA de estado sobre alfabetos binarios, de modo que la cadena más corta que no está en es de longitud para .$n\geq N$$N$$n$$M$$L(M)$$\Omega(2^{cn})$$c=1/75$

Por lo tanto, el valor óptimo para está entre y . No estoy seguro de si el resultado de Shallit ha mejorado en los últimos años.$f(n)$$2^{n/75}$$2^n$