¿Puede una máquina de Turing decidir si un NFA acepta una cadena de longitud principal?

14

Quiero saber si el siguiente problema es decidible:

Instancia: un NFA A con n estados

Pregunta: ¿Existe algún número primo p tal que A acepte alguna cadena de longitud p.

Creo que este problema es indecidible, pero no puedo probarlo. El decisor puede tener fácilmente un algoritmo para determinar si un número particular es primo, pero no veo cómo podría analizar el NFA con suficiente detalle para saber exactamente qué longitudes puede producir. Podría comenzar a probar cadenas con el NFA, pero para un lenguaje infinito, puede que nunca se detenga (y, por lo tanto, no sea un factor decisivo).

El NFA se puede cambiar fácilmente a un DFA o expresión regular si la solución lo necesita, por supuesto.

Esta pregunta es algo que he estado reflexionando como una pregunta de preparación hecha por mí mismo para una final que tengo en 2 semanas.

Frío
fuente
No estoy seguro de si esto es de nivel universitario, así que no te preocupes por eliminarlo. Puede resultar un problema difícil, ver, por ejemplo, terrytao.wordpress.com/2007/05/25/…
Bueno, lo inventé, así que puede ser difícil. No he encontrado ninguna prueba de problemas indecidibles relacionados con NFA / DFA, por lo que pensé que podría ser interesante probar uno.
Creo que lo que vinculaste es un problema diferente (más fácil). Puede responder "¿cuántas cadenas de longitud x acepta un NFA?". Usando la fórmula provista, tendríamos que verificar infinidad de instancias de para ver si existe una cadena que el NFA acepta que tenga una longitud máxima. No estoy preguntando sobre una prima particular, estoy preguntando sobre todos ellos. sL(n)

Respuestas:

17

Las longitudes de las cadenas aceptadas por un DFA forman un conjunto semilineal (como en el teorema de Parikh para lenguajes libres de contexto), la descripción de esos no es demasiado difícil de encontrar (esencialmente empalma todos los ciclos posibles del autómata), y por El teorema de Dirichlet cualquier progresión aritmética de la forma con mcd ( a , b ) = 1 contiene una infinidad de números primos.a+bkgcd(a,b)=1

Al unir lo anterior se obtiene un algoritmo para verificar si su lenguaje regular (o incluso sin contexto) contiene cadenas de longitud principal. Definitivamente no es una pregunta simple, en mi humilde opinión ...

vonbrand
fuente
Agradecería un poco de ayuda para entender el teorema de Parikh en este caso. Obviamente, podemos convertir un NFA en un PDA simplemente no usando la pila en el PDA. ¿Los subconjuntos lineales especifican los ciclos? Si es así, ¿cómo funciona eso?
Chill
1
kk
1
Creo que eso responde mi pregunta. Voy a tratar de leer más sobre el teorema de Parikh. Entiendo la idea y cómo puede especificar ciclos en este caso. Lo que quiero descubrir es una solución más "práctica" en la que haga un algoritmo real para resolver este problema.
Chill
@Chill, solo mira mi comentario anterior. No es tan difícil llegar a una descripción de las longitudes posibles simplemente borrando los símbolos en el DFA como un gráfico y verificando las caminatas entre el estado de inicio y los estados finales. Difícil de formalizar, fácil de entender a mano para cualquier ejemplo dado.
vonbrand
3
aaaa(aa)