Dado un DFA $A$ encontrar un algoritmo de tiempo polinómico para determinar si una palabra de la forma $ww$ está en $L(A)$

Question

Dado un DFA $A$ con $|\Sigma|\ge 2$ encontrar un algoritmo de tiempo polinómico para determinar si existe una palabra de la forma $ww$ en $L(A)$ .

Answer 1

Dejemos que $I_t$ sea el autómata obtenido a partir de $A$ haciendo $t$ el único estado final. Dejemos que $F_t$ sea el autómata obtenido a partir de $A$ haciendo $t$ el estado inicial.

El número de la $I_t$ y $F_t$ autómatas es lineal en el número de estados de $A$ . Para cada par de autómatas, $(I_t, F_t)$ , comprueba si la intersección de sus lenguajes es no vacía.

Si la lengua de la pareja $(I_t, F_t)$ no está vacío, contiene una palabra $w$ tal que $ww \in L(A)$ . (La carrera de $ww$ en $A$ pasa por $t$ .) El algoritmo se ejecuta claramente en tiempo polinómico.