El reverso, una serie $w^{R}$ $w = w_1w_2...w_n$, es la cadena $w_n...w_2w_1$. Supongamos que L es un lenguaje regular. ¿Debe regular el lenguaje $L_1 = {w : w^Rw \in L}$, o sea no regular? Explicar.
Respuestas
¿Demasiados anuncios?
uv_
Puntos
36
Es regular. Observe que $L^R=\{w^R\mid w\in L\}$ es regular, y la idea es hacer un "bidireccional" verificación de la NFA de $L$$L^R$, que en realidad son el mismo autómatas finitos con todos los bordes invertidos.
Para hacer que sea formal, supongamos que la NFA para $L$ $\mathcal{A}=(\Sigma, Q, s, \delta_1, \{f\})$ (Ver esta página de la wiki para la definición del modelo). Entonces podemos construir una invertida autómatas $\mathcal{A}^R=(\Sigma, Q, f, \delta_2, \{s\})$$L^R$, donde $$\delta_2(q,c)=\{q'\in Q\mid \delta_1(q',c)=q\}.$$ Suponemos que $\epsilon$-transiciones permitidas, y para asegurar las siguientes construcciones son razonables, no asumir que $q\in\delta_i(q,\epsilon)$ para todos los $q\in Q$, $i=1,2$.
A continuación definimos un producto directo de la NFA $(\Sigma, Q\times Q, (s,f),\delta, F)$ tal que $$\delta((q_1,q_2),c)=\delta_1(q_1,c)\times\delta(q_2,c),\ \forall c\in\Sigma\cup\{\epsilon\}$$ $$F=\{(q,q)\mid q\in Q\}$$ Y está claro que cuando una cadena de $w$ es alimentado en este autómatas, lo que hace es simular $\mathcal{A}$ $w$ de estado $s$ e invierte $\mathcal{A}^R$ $w$ de estado $f$. Si se encuentran en el mismo estado después de la $w$ termina, podemos concatenar sus transiciones para obtener un camino de$s$$f$, en el que la aceptó cadena es exactamente $ww^R$.
Llegamos a la conclusión de la anterior NFA acepta el lenguaje de $L'=\{w\mid ww^R\in L\}$. Aviso $$L_1=\{w^R\mid ww^R\in L\}=L'^R$$ y por lo tanto $L_1$ es regular.
MHS
Puntos
599
Aquí es una idea que demuestra que $L_1$ está a menos de contexto libre.
Supongamos que el (universal) alfabeto para todos los idiomas es $A$. Sabemos que el espejo de lenguaje $L_R=\{w^Rw\mid w\in A^*\}$ es de contexto libre el uso de una PDA. Ahora intersección $L_R$ regular con su lengua $L$ obtenemos $L_R\cap L$, que es definitivamente un lenguaje libre de contexto (general de cierre de la propiedad). Entonces, esto también demuestra que el lenguaje de $L_1$ está a menos de contexto libre de la siguiente manera: Ejecutar un no-determinista de la PDA, que no determinista genera una palabra al azar $v$ (que al final va a resultar ser $w^R$) en la pila y en paralelo se ejecuta el autómata de estado finito para $L$ en esta palabra $v$. Después de esto, el PDA se inicia la lectura de la entrada real,$w$. Símbolo por símbolo se compara esta entrada contra los símbolos sacados de la pila (si es que hay alguna anomalía o si la pila está vacía antes de $w$ está completamente de lectura, que se detiene y se rechaza) y también continúa ejecutando el autómata de estado finito para $L$. Una vez que la entrada es completamente leer la máquina comprueba si la pila está vacía (es decir, $v$ corresponde a $w^R$) y el autómata de estado finito para $L$ alcanzado una aceptación de la terminal de estado (es decir,$vw$$L$). Si se cumplen ambas condiciones a la entrada de la palabra $w$ es aceptado.
Ahora la pregunta más difícil es si su idioma $L_1$ puede ser, de hecho, estrictamente de contexto libre (es decir, no regulares). Lo he pensado un par de ejemplos, pero no encontramos ningún caso en el que $L_1$ no es regular, por lo que incluso el más fuerte, el resultado se mantiene.
