# How would a DFA be designed to accept a language defined as the string comprised of every other character in each string in another language? [duplicate]

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?

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

• 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. – Renato Sanhueza Feb 10 '16 at 23:32
• A method to generate a DFA for any regular language with the same alphabet using M1. – Adam Feb 10 '16 at 23:43
• – Anton Trunov Feb 11 '16 at 12:41
• @AntonTrunov That seems more than related: it's a near-exact duplicate. – David Richerby Feb 11 '16 at 20:05

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