Construire un DFA basé sur ce langage
Laisser $L \subseteq \Sigma^*$ être une langue de n'importe quel alphabet $\Sigma$. Laisser$move(L)$ décrire la langue qui contient chaque chaîne de telle sorte qu'elle prenne la dernière lettre de $x \in L$ et le met au premier plan.
Comment pouvons-nous construire un DFA $A$ pour $move(L)$?
J'ai commencé par regarder à quoi ressemblerait DFA pour L:
- Dire $s = s_0 s_1 s_2 ... s_n$ où $s_i \in \Sigma$ est une chaîne acceptée par DFA
- il passera par un chemin d'états $q_0q_1...q_n$. J'ai fait la transition du dernier état au premier en$A$ mais quelque chose me dit que ce n'est pas bien, donc je ne sais pas comment passer à autre chose.
Réponses
Laisser $\ A=\big(Q,\Sigma, \delta, q_0, F\big)\ $ être un DFA qui accepte $\ L\ $. Soit \ 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'$\\ \ big (\ sigma, \ delta (q, s) \ big) & if $\ q'=(\sigma,q)\in\Sigma\times Q\ $.} \ end {align} Alors$\ S'=\big(Q',\Sigma, \delta', q_0', F'\big)\ $ est un DFA qui accepte $\ move(L)\ $.
Si $\ \xi\in\Sigma^*\ $, et $\ q_n\ $ est l'état de $ A\ $ après avoir traité la chaîne $\ \xi\ $, puis $\ \big(s_0,q_n\big)\ $ sera l'état de $\ A' $ après avoir traité la chaîne $\ s_0\xi\ $, et $\ \big(s_0,q_n\big)\in F'\ $ si et seulement si $\ \delta(q_n,s_0)\in F\ $-C'est, $\ A'\ $ accepte la chaîne $\ s_0\xi\ $ si et seulement si $\ A\ $ accepte la chaîne $\ \xi s_0\ $.
Répondre à la requête de l'OP dans les commentaires
En général, le DFA à état minimal pour la langue $\ L\ $ aura strictement moins d'états que le DFA à état minimal pour $\ move(L)\ $, donc si vous recevez un DFA pour $\ L\ $ il n'est pas toujours possible de créer un DFA pour $\ move(L)\ $qui a le même ensemble d'états. 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} par exemple, il est facile de construire un $5$-État DFA qui accepte $\ L\ $. cependant,\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} et il n'est pas difficile de montrer que tout DFA qui accepte $\ move(L)\ $ doit avoir au moins $7$états (en utilisant le théorème de Myhill-Nerode , par exemple).
Et qu'est-ce qui se passerait si $\ \epsilon\in L\ $?
La réponse de Dromniscience et le commentaire de LetmeKnow ci-dessous m'ont alerté sur le fait que la réponse ci-dessus fait implicitement (et par inadvertance de ma part) une hypothèse qui n'est pas nécessairement justifiée - à savoir que l' opération de déplacement éliminera la chaîne vide$\ \epsilon\ $ s'il se trouve que c'est dans $\ L\ $. Car$\ q_0'\not\in F'\ $ dans la définition ci-dessus de $\ A'\ $ la chaîne vide $\ \epsilon\ $ ne peut pas être dans la langue acceptée par $\ A'\ $.
Cependant, comme l'OP ne spécifie pas comment l' opération de déplacement traitera la chaîne vide, il ne me semble pas justifié de supposer que$\ \epsilon\not\in move(L)\ $ n'importe quand $\ \epsilon\in L\ $. Si, au contraire,$\ \epsilon\in L\ \implies\epsilon\in move(L)\ $ puis la définition de $\ A'\ $devrait être modifié comme suit: \ 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 \} & if$\ 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) & si $\ q'=q_0'$\\ \ big (\ sigma, \ delta (q, s) \ big) & if $\ q'=(\sigma,q)\in\Sigma\times Q\ $.} \ end {align}
Vous n'êtes pas obligé de déplacer la dernière transition vers l'avant. Au lieu de cela, pourquoi ne vous souvenez-vous pas simplement de la première lettre et ne vérifiez pas si elle conduira à un état final dans le DFA d'origine?
Veuillez y réfléchir avant de continuer à lire. Si nous désignons le DFA d'origine comme$L = \langle Q, \Sigma, \delta, q_0, F\rangle$, nous pouvons créer un nouveau DFA pour $move(L) = \langle Q', \Sigma, \delta', q_{init}, F'\rangle$, où \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} Depuis $\epsilon$ n'est jamais dedans $move(L)$, $F'$ suffit.