Condición para la infinitud del lenguaje de un autómata de estado finito

9

Hay un teorema que dice que:

Dado un autómata de estado finito que tiene estados, si existe una cadena cuya longitud satisface entonces el lenguaje aceptado por el autómata es infinito.nortewnorte≤El |wEl |≤2norte-1

Entiendo la restricción El |wEl |≥norte , pero no entiendo por qué la restricción El |wEl |≤2norte-1 está ahí.

automata finite-automata rahul sharma
fuente

Respuestas:

5

En el peor de los casos, su NFA podría verse así:

La w más pequeña wpara la que se garantiza un bucle (lo que lo obliga a aceptar un idioma infinito) tiene un tamaño de 2norte-1 .

André Souza Lemos
fuente
Cuando empiezo desde q0 y luego cuando regresé a q0, eso significa que hay un ciclo en la máquina. ¿No es suficiente en el peor de los casos, por qué volvemos a la etapa final nuevamente en este caso? Por lo que entiendo de esta figura, bombearemos este ciclo una vez y luego volveremos a la etapa final, así que significa una vez que ingresamos en la etapa final, estamos asumiendo que esta no es mi cadena, ya que regresó a otro estado, pero una vez que vuelve a la etapa final nuevamente, entonces estamos seguros de que esta es nuestra cadena ya que hay algún bucle que tiene sido bombeado?
Rahul Sharma
Estamos tratando de demostrar algo sobre el autómata, a saber, que acepta un lenguaje infinito. En la forma en que se formula la prueba, se conjetura una cadena , cuyo tamaño se supone que está dentro de cierto intervalo. Obviamente, si el autómata tiene un bucle, entonces la cadena existe. Lo que sucede es que si es imposible de encontrar dentro de este intervalo, entonces la máquina no puede ser como la de la imagen. O no tiene bucles o no tiene estados finales. www
André Souza Lemos
Entiendo su punto. Solo estoy tratando de entender el límite superior en el intervalo, por qué es 2n-1 y por qué no 2n-x (x puede ser cualquier cosa menos 1). En la figura anterior podemos decir que loop es qo -q1 .... qn-q1 .... qn, ¿verdad (el ciclo máximo)? Pero cuando vuelvo a ser q0 (q0 ... aq, q0), ¿no significa que hay un ciclo, así que el máximo debería ser n, ¿por qué estamos agregando n-1 a n (o por qué vamos a volver al estado final)? Estoy teniendo dificultades para obtener esto :(. puede max. loop ser q0., q1, q2 ..qn, qn-1, qn-1..q0, algo así?
rahul sharma
El límite superior es porque no empeora más que eso. es más pequeño que , y acabo de mostrarle un autómata que necesita pasos. No hay uno que necesite más (y hace el trabajo), pero hay uno que necesita esta cantidad. 2n−12n−x2n−12n−1
André Souza Lemos
Lo tengo ahora. Solo una pequeña duda. Supongo que tengo 4 estados en mi máquina. Y leí la cadena ABC y llegué al estado final y luego leí d allí y volví al estado inicial, y luego vuelve al estado final, así que mi cadena se convertirá en abcdabc. ¿Cómo puedo dividir esto en lemma de bombeo y obtener y ^ i, donde i = 1, para mostrar que y ha sido bombeado una vez?
rahul sharma
5

La condición adicional le permite escribir un algoritmo directo - verifique todas las cadenas con longitudes en este intervalo - para decidir (in) finitud del lenguaje aceptado. Por lo tanto, obtienes una prueba de que esta propiedad es decidible (lo que no es para la mayoría de los modelos de autómatas con potencia súper regular).

Rafael
fuente
3

El teorema completo establece una equivalencia en lugar de una implicación :

El lenguaje aceptado por un NFA de estado es infinito si y solo si contiene una palabra cuyo tamaño satisface .nortewnorte≤El |wEl |≤2norte-1

La condición extra fortalece así el teorema .El |wEl |≤2norte-1

Yuval Filmus
fuente