prueba de lenguaje regular, un lenguaje parcial a uno regular

Question

He estado intentando resolver una duda que tengo y creo que estoy en lo cierto pero no estoy seguro. ¿Es el lenguaje {w| www pertenece a L' y L' es regular} regular? No pude encontrar ninguna manera de demostrar que no es regular, así que pensé que tal vez lo es, Lo que consideré es el siguiente escenario, supongamos que tenemos el autómata A(L') Nos fijamos en el Delta(q0,www) = qF para cada palabra de la forma www en L' , y podemos suponer que existe un estado qi que Delta(q0,w) = qi, y Delta(qi,ww) = qF, Así que como eso es cierto (por razones obvias) puedo construir un autómata que el estado qi es un estado de aceptación para cada palabra www en el autómata original y eliminar otros estados de aceptación del autómata y ahora tenemos un autómata que acepta la palabra w para cada palabra www que existía en L' lo que significa que L es regular (porque tiene un dfa/nfa). ten en cuenta que w es una palabra completa de longitud desconocida.

¿Esta idea básica es correcta o se me escapa algún agujero?

Answer 1

Supongamos que $M=\langle Q,\Sigma,\delta,q_0,F\rangle$ es un DFA que reconoce $L'$ podemos construir un DFA $M'=\langle Q',\Sigma,\delta',q_0',F'\rangle$ que reconoce $L$ como sigue.

$Q'$ es el conjunto de todas las funciones de $Q$ a $Q$ . Un estado $f\in Q'$ es un estado aceptor en $M'$ si $f^3(q_0)\in F$ donde $f^3(q)=f(f(f(q)))$ es decir, $F'=\{f\in Q':f^3(q_0)\in F\}$ . El estado inicial $q_0'$ es la función de identidad en $Q$ . Sólo queda definir la función de transición $\delta'$ .

Para cada $w\in\Sigma$ deje $f_w:Q\to Q:q\mapsto\delta(q,w)$ . Entonces para $f\in Q'$ y $a\in\Sigma$ definimos $$\delta'(f,a)=f\circ f_a\;;$$ esto tiene sentido, ya que $f\circ f_a$ es una función de $Q$ a $Q$ y, por tanto, es un elemento de $Q'$ es decir, un estado de $M$ .

Te dejo a ti demostrar que este DFA $M'$ reconoce $L$ . Querrás demostrar (por inducción sobre la longitud de $w$ ) que $\delta'(q_0',w)=f_w$ para cada $w\in\Sigma^*$ .

Por cierto, modificando convenientemente $F'$ puede utilizar esta construcción para demostrar que una variedad de idiomas relacionados de manera similar a $L'$ son regulares.

Answer 2

Pista. Supongamos que tiene una ADC para $L'$ cuyo conjunto de estados es $Q$ y regla de transición $\delta_1$ . Ahora construye un nuevo DFA cuyo conjunto de estados sea $\mathcal P(Q\times Q)$ y regla de transición $$ \delta_2(X,a) = \{ (q,\delta_1(q',a)) \mid (q,q') \in X\} $$

Ahora, una elección adecuada de los estados inicial y de aceptación resolverá su problema.

Answer 3

Una forma fácil de demostrar este resultado es utilizar el hecho de que un lenguaje es regular si y sólo si es reconocido por un monoide finito.

Definición . Un idioma $L$ de $A^*$ es reconocido por un monoide finito $M$ si existe un morfismo monoide suryectivo $f:A^* \to M$ y un subconjunto $P$ de $M$ tal que $f^{-1}(P) = L$ .

Ahora $K = \{u \in A^* \mid u^3 \in L\}$ y que $Q = \{m \in M \mid m^3 \in P \}$ . Entonces tenemos \begin{array} {}f^{-1}(Q) &= \{ u \in A^* \mid f(u)^3 \in P \} = \{ u \in A^* \mid f(u^3) \in P \} \\ &= \{ u \in A^* \mid u^3 \in f^{-1}(P) \} = \{ u \in A^* \mid u^3 \in L \} \\ &= K \end{array} Así $K$ es regular.