Dureza de encontrar una palabra de longitud como máximo

Planteamiento del problema :

Deje que sea un autómata pushdown (potencialmente no determinista) y deje que sea su alfabeto de entrada. ¿Hay una palabra st que es aceptado por ? $M$ $\cal A$ $w \in \cal A^*$ $|w| \leq k$ $M$

¿Es este problema NP-completo? ¿Ha sido estudiado? ¿Hay algún algoritmo que permita encontrar una palabra así?

cc.complexity-theory np-hardness fl.formal-languages automata-theory Lamina
fuente

¿No debería funcionar el algoritmo de Djikstra? (¡Probablemente estoy malinterpretando algo aquí!)

alpoge

"longitud como máximo "?

k

$k$

alpoge

De nada, Kaveh. Sí, olvidé "a lo sumo", volví a editar.

Lamine

La respuesta es fácil: ¿es una pregunta de tarea?

Sariel Har-Peled

¿Tenemos acceso a la descripción de los autómatas o solo la tenemos como recuadro negro?

Raphael

Respuestas:

Calcule la intersección de su lenguaje CFG con el lenguaje regular (esto equivale a multiplicar el número de estados por y agregar un estado "sin salida"). Ahora compruebe si el resultado está vacío: conviértalo en una gramática (creo que el resultado tendrá un tamaño polinómico) y "retroceda" de las producciones de epsilon. $\sum_{i=0}^k A^k$ $k$

Editar: Kaveh mencionó que esto es polinomial en , por lo que si se da como entrada, el algoritmo es exponencial en . Sin embargo, Kaveh encontró una manera de arreglarlo. Convierta el autómata original en un CFG y reemplace todos los terminales por un terminal fijo. Ahora use un algoritmo iterativo para encontrar el tamaño mínimo de una palabra generada por cada no terminal, de la siguiente manera. $k$ $k$ $|k|$

$\infty$ $A \rightarrow a^t \prod B_i$ $f(A) = \min(f(A),t+\sum f(B_i))$ $O(n)$ $n$

Yuval Filmus
fuente

También creo que la transformación PDA CFG es polinomial. ¡Gracias! Así que el problema está en .

\to

$\rightarrow$

P

$P$

Lamine

Ok, ya que hay una manera de calcular directamente la longitud más baja,

No es una entrada. Pero no entiendo por qué reemplazar todos los terminales por uno fijo. El algoritmo debe funcionar correctamente con terminales originales.

| k |

$|k|$

Lamine

Tienes razón, en realidad no importa.

Yuval Filmus

Cambie todos los caracteres del alfabeto a un solo carácter específico. Ahora, tiene un PDA definido sobre un solo carácter. Su lenguaje es una gramática libre de contexto. Sin embargo, la gramática libre de contexto sobre un solo carácter es regular. Por lo tanto, convierta el CFG a un idioma normal y luego verifique si contiene una palabra de longitud k.

Ahora, todas estas conversiones tienden a requerir un tiempo exponencial, pero me parece poco probable que el problema sea NP completo. Especialmente si permite el tiempo polinomial en . $k$

Podría estar equivocado, y me disculpo por mi respuesta inicial ...

Por cierto, el hecho de que un CFG sobre una sola letra sea regular se deduce del teorema de Parikh. Aunque una prueba directa no es demasiado difícil. Consulte el enlace para obtener más detalles sobre el teorema de Parikh: es un resultado hermoso ... http://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf

Sariel Har-Peled
fuente

No, no soy estudiante. El problema que mencioné es inicialmente un problema de red que se modeló como un autómata. Solo sabría si vale la pena buscar una solución polinómica o no.

Lamine

¿No debería esta respuesta ser un comentario?

Oleksandr Bondarenko

Si deberia. Sariel, ¿podrías mover esto a un comentario o dar una respuesta?

Suresh Venkat

@Suresh: Usted puede ser consciente de ello, pero ahora moderadores puede activar una respuesta en un comentario .

Tsuyoshi Ito

Moví la respuesta original a un comentario. Esta es una nueva respuesta.

Suresh Venkat

~~Un método probablemente subóptimo: ejecutar el algoritmo de Djikstra. Luego, para cada estado final, compare las distancias con . Si alguno es , acepte. Rechazar. $k$ $\leq k$~~

EDITAR: ¡Lo anterior solo funciona para los NFA! Lo siento por eso.

alpoge
fuente

(¡pero definitivamente poli-time!)

alpoge

No estoy seguro de que el algoritmo de Dijkstra pueda resolver el problema. Puede encontrar el camino más corto entre el estado inicial y el final. Por supuesto, se puede generar una palabra que pueda aceptarse a través de estos caminos. Pero estos caminos son elementales, y las palabras pueden aceptarse a través de caminos no elementales; de lo contrario, el problema de determinar si una gramática libre de contexto puede generar alguna palabra sería decidible, pero no lo es.

Lamine

La prueba de vacío para CFL es decidible, ¿no?

alpoge

(¡Perdóname de nuevo si estoy malentendido!)

alpoge

Bueno, uno puede usar un algoritmo de 'marcado' para hacer esto (dado el CFG): marcar terminales, luego marcar cosas que derivan terminales, luego marcar cosas que derivaron cosas que están marcadas, etc. hasta que el proceso finalice y luego verificar si la variable de inicio está marcada. Además, ignore mi respuesta: eso es lo que debe hacer para un NFA (¡ciertamente no para un PDA!).

alpoge