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?

  • $\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$ Commented Feb 10, 2016 at 23:32
  • $\begingroup$ A method to generate a DFA for any regular language with the same alphabet using M1. $\endgroup$
    – Adam
    Commented Feb 10, 2016 at 23:43
  • 5
    $\begingroup$ Related: cs.stackexchange.com/questions/49342/… $\endgroup$ Commented Feb 11, 2016 at 12:41
  • 2
    $\begingroup$ @AntonTrunov That seems more than related: it's a near-exact duplicate. $\endgroup$ Commented Feb 11, 2016 at 20:05

1 Answer 1


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) $.


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