Construya un DFA basado en este lenguaje
Dejar $L \subseteq \Sigma^*$ ser un idioma de cualquier alfabeto $\Sigma$. Dejar$move(L)$ describir el idioma que contiene cada cadena de tal manera que toma la última letra en $x \in L$ y lo pone al frente.
¿Cómo podemos construir un DFA? $A$ para $move(L)$?
Comencé mirando cómo sería el DFA para L:
- Decir $s = s_0 s_1 s_2 ... s_n$ dónde $s_i \in \Sigma$ es una cadena que acepta DFA
- pasará por algún camino de estados $q_0q_1...q_n$. Hice la última transición de estado al primero en$A$ pero algo me dice que esto no está bien, así que no estoy seguro de cómo seguir adelante.
Respuestas
Dejar $\ A=\big(Q,\Sigma, \delta, q_0, F\big)\ $ ser un DFA que acepta $\ L\ $. Sea \ begin {align} Q '& = \ big (\ Sigma \ times Q \ big) \, \ cup \ big \ {q_0' \ big \} \\ F '& = \ big \ {(s, q) \ in \ Sigma \ times Q \, \ big | \, \ delta (q, s) \ in F \ big \} \\ \ delta '(q', s) & = \ cases {(s, q_0) & if$\ q'=q_0'$\\ \ grande (\ sigma, \ delta (q, s) \ grande) y si $\ q'=(\sigma,q)\in\Sigma\times Q\ $.} \ end {align} Entonces$\ S'=\big(Q',\Sigma, \delta', q_0', F'\big)\ $ es un DFA que acepta $\ move(L)\ $.
Si $\ \xi\in\Sigma^*\ $y $\ q_n\ $ es el estado de $ A\ $ después de que haya procesado la cadena $\ \xi\ $, luego $\ \big(s_0,q_n\big)\ $ será el estado de $\ A' $ después de que haya procesado la cadena $\ s_0\xi\ $y $\ \big(s_0,q_n\big)\in F'\ $ si y solo si $\ \delta(q_n,s_0)\in F\ $-es decir, $\ A'\ $ acepta la cuerda $\ s_0\xi\ $ si y solo si $\ A\ $ acepta la cuerda $\ \xi s_0\ $.
Responder a la consulta de OP en comentarios
En general, el DFA de estado mínimo para el idioma $\ L\ $ tendrá estrictamente menos estados que el DFA de estado mínimo para $\ move(L)\ $, por lo que si se le otorga un DFA para $\ L\ $ no siempre será posible construir un DFA para $\ move(L)\ $que tiene el mismo conjunto de estados. Si\begin{align} L=\ &\big\{a^{n_1}b^{n_2}c^{n_3}\,\big|\,n_1\ge0, n_2\ge0, n_3\ge1\,\big\}\\ \cup &\big\{a^{n_1}b^{n_2}d^{n_3}\,\big|\,n_1\ge0, n_2\ge0, n_3\ge1\,\big\}\\ \cup &\big\{a^{n_1}b^{n_2}e^{n_3}\,\big|\,n_1\ge0, n_2\ge0, n_3\ge1\,\big\}\ , \end{align} por ejemplo, es fácil construir un $5$-estado DFA que acepta $\ L\ $. Sin embargo,\begin{align} move(L)=\ &\big\{ca^{n_1}b^{n_2}c^{n_3}\,\big|\,n_1\ge0, n_2\ge0, n_3\ge0\,\big\}\\ \cup &\big\{da^{n_1}b^{n_2}d^{n_3}\,\big|\,n_1\ge0, n_2\ge0, n_3\ge0\,\big\}\\ \cup &\big\{ea^{n_1}b^{n_2}e^{n_3}\,\big|\,n_1\ge0, n_2\ge0, n_3\ge0\,\big\}\ , \end{align} y no es difícil demostrar que cualquier DFA que acepte $\ move(L)\ $ debe tener al menos $7$estados (utilizando el teorema de Myhill-Nerode , por ejemplo).
Y si $\ \epsilon\in L\ $?
La respuesta de Dromniscience y el comentario de LetmeKnow a continuación me alertaron sobre el hecho de que la respuesta anterior implícitamente (e inadvertidamente de mi parte) hace una suposición que no está necesariamente justificada, es decir, que la operación de movimiento eliminará la cadena vacía$\ \epsilon\ $ si pasa a estar en $\ L\ $. Porque$\ q_0'\not\in F'\ $ en la definición anterior de $\ A'\ $ la cuerda vacía $\ \epsilon\ $ no puede estar en el idioma aceptado por $\ A'\ $.
Sin embargo, dado que el OP no especifica cómo la operación de movimiento se ocupará de la cadena vacía, no me parece justificado asumir que$\ \epsilon\not\in move(L)\ $ cuando $\ \epsilon\in L\ $. Si, en cambio,$\ \epsilon\in L\ \implies\epsilon\in move(L)\ $ entonces la definición de $\ A'\ $tendría que modificarse de la siguiente manera: \ begin {align} Q '& = \ big (\ Sigma \ times Q \ big) \, \ cup \ big \ {q_0' \ big \} \\ F '& = \ cases {\ big \ {(s, q) \ in \ Sigma \ times Q \, \ big | \, \ delta (q, s) \ in F \ big \} y si$\ q_0\not\in F$\\ \ big \ {(s, q) \ in \ Sigma \ times Q \, \ big | \, \ delta (q, s) \ in F \ big \} \ cup \ big \ {q_0 '\ big \ }&Si $\ q_0\in F$} \\ \ delta '(q', s) & = \ cases {(s, q_0) & if $\ q'=q_0'$\\ \ grande (\ sigma, \ delta (q, s) \ grande) y si $\ q'=(\sigma,q)\in\Sigma\times Q\ $.} \ end {align}
No es necesario que mueva la última transición al frente. En su lugar, ¿por qué no recuerda simplemente la primera letra y comprueba si conducirá a un estado final en el DFA original?
Por favor, piénselo bien antes de continuar leyendo. Si denotamos el DFA original como$L = \langle Q, \Sigma, \delta, q_0, F\rangle$, podemos construir un nuevo DFA para $move(L) = \langle Q', \Sigma, \delta', q_{init}, F'\rangle$, dónde \begin{align} Q' &= \{q_{init}\} \cup \Sigma \times Q \\ F' &= \{(a, q)\mid \delta(a, q)\in F\} \\ \delta'((a, q), b) &= (a, \delta(q,b)) \\ \delta'(q_{init}, b) &= (b, q_0) \\ \end{align} Ya que $\epsilon$ nunca está en $move(L)$, $F'$ es suficiente.