0
$\begingroup$

This question already has an answer here:

For example, you have a DFA that accepts the language comprised of strings aabbbaa and aaabbbbaaa, and you want to create a new DFA that accepts a language comprised of strings abba and aabba (strings made up of every other character in the strings in the original language). What would be the generalized construction technique for creating the new DFA that could be applied to any DFA to produce the same results?

I think there's something to it involving creating an NFA using lambda transitions from each state to the following state in the original DFA, then converting the NFA to a DFA, but that creates a DFA that accepts more strings than originally intended.

Any suggestions?

$\endgroup$

marked as duplicate by J.-E. Pin, David Richerby, Luke Mathieson, Juho, hengxin Feb 22 '16 at 6:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Are you interested in the construction of a DFA $M_2$ for the language $L_2=\{abba, aabba\}$ using the DFA $M_1$ that denotes $L_1=\{aabbbaa, aaabbbbaaa\}$ or do you want a method to generate a DFA for any regular language with the same alphabet, using $M_1$?. Im really confused about your question. $\endgroup$ – Renato Sanhueza Feb 10 '16 at 23:32
  • $\begingroup$ A method to generate a DFA for any regular language with the same alphabet using M1. $\endgroup$ – Adam Feb 10 '16 at 23:43
  • 5
    $\begingroup$ Related: cs.stackexchange.com/questions/49342/… $\endgroup$ – Anton Trunov Feb 11 '16 at 12:41
  • 2
    $\begingroup$ @AntonTrunov That seems more than related: it's a near-exact duplicate. $\endgroup$ – David Richerby Feb 11 '16 at 20:05
2
$\begingroup$

This is a closure property. For language $L\subseteq \Sigma^*$, define the language $even(L) = \{ x_2x_4\dots x_{2n} \mid x_1x_2x_3\dots x_{2n-1}x_{2n} \in L, x_i\in\Sigma\}$. Now for regular $L$ the language $even(L)$ is again regular. This is a special case of closure of the regular languages under finite state transductions.

In case of this specific property an automaton $M_1$ for $even(L)$ when $M$ for $L$ is given, can be found as follows. For every pair of consecutive transitions $(p,a,q)(q,b,r)$ for $M$ introduce the transition $(p,b,r)$ in $M_1$.

Additionally one needs a somewhat formal argument that this will in fact work.

Alternatively, this closure property can be deduced from known closure properties: (inverse) morphisms and intersection with regular languages. Make a copy of $\Sigma$: $\bar\Sigma=\{\bar a \mid a\in \Sigma\}$. Define the morphisms $g,h:(\Sigma\cup\bar\Sigma)^*\to \Sigma^*$ where $g$ removes the bar (but keeping the letters), and $h$ removes letters from $\bar\Sigma$. $R$ is the regular language $(\bar\Sigma\Sigma)^*$ Then $even(L)$ is the composition $h(g^{-1}(L) \cap R) $.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.