Lengua con error.

Question

Que $L \subset {0, 1}^∗$ ser lengua regular. $$L_e = { w | w = uxv, x \in {0, 1}, u\overline{x}v \in L}$$, where $ \overline{x} = 1 − x$ prueba $L_e$ es a lengua regular. Por ejemplo: si $10 \in L$ y $11, 00 \in L_e$ $.

Estoy pensando en él muchas horas pero nada funciona. Trato de usar Teorema de Nyhill-Nerode pero no ayuda. Por favor me sugerencia.

Answer 1

SUGERENCIA: Deje $M$ ser un afd que reconoce a $L$. Haga dos copias de $M$, decir $M_1$$M_2$; vamos a modificar para hacer un NFA $N$ que reconoce $L_e$. $N$ comienza en el estado inicial de $M_1$. Cada estado de $M_1$ tiene todas las transiciones de $M$, y cada uno también tiene dos transiciones, una para $0$ y uno para $1$, que van en $M_2$. No hay transiciones de$M_2$$M_1$.

La idea es que con el fin de ser aceptado, la palabra debe conducir a la $N$ a $M_2$, y se puede hacer esto sólo por pretender – sólo una vez! – que una entrada de $i$ se $1-i$. Me he dejado más de los detalles en el spoiler bloque protegido a continuación, pero a ver si puede venir con $N$ sobre tu primer.

Específicamente, si $q\overset{i}\longrightarrow q'$$M$, $N$ $i$ transiciones a partir de la copia de $q$ $M_1$ a la copia de $q'$ $M_1$ y un $1-i$ transición de la copia de $q$ $M_1$ a la copia de $q'$ en $M_2$. $M_2$ sólo tiene las transiciones de $M$. Finalmente, el aceptor de los estados de $N$ son los de $M_2$, que son los mismos que en $M$; $M_1$ no tiene aceptor de los estados.

Answer 2

Asumir la existencia de un autómata $M=(\Sigma^*,Q,q_0,'.',\{q_f\})$ reconocimiento $L$, la observación muy importante aquí es :$w$ es un elemento de $L_e$ si existe algunas palabras $u$ $v$ $x=0,1$ tal que $u(1-x)v$$M_e$, la idea es memorizar el estado de todas las palabras de esta forma,considere el siguiente autómata $M'=(\Sigma^*,Q',q_0',T,Q_f)$ definido por:

• $Q'=Q\times2^Q$
• $Q_f=\{(q,S)\in Q'\big/ q_f\in S\}$
• $q'_0=\emptyset $

y la transición de la función está definida por: $T((q,S),x)=\left(q.x,\left(S.x\cup \{q.(1-x)\}\right)\right)$

Si $M'(w)=(q,S)$ esto significa que el $M(w)=q$ y el conjunto de $S$ contiene el conjunto de todos los estados finales de todas las palabras de la forma $u(1-x)v$ al $uxv=w$, por lo que si $S$ contiene el estado final $q_f$ $w$ $M'$ y esto es exactamente lo que significa $w\in L_e$