How can I prove that this language is regular?

Question

Given a language $L$, define the language $K$ as the language $L$ where every second character is replaced with a $\#$. (Note: $\#$ is not part of the alphabet of $L$.) For example, if $L = \{ab, aabb, abbab \}$, then $K = \{a\#, a\#b\#, a\#b\#b \}$.

How can I prove that if $L$ is regular, then $K$ is also regular?

I think that I should transform the regular expression that defines $L$ to a series of sub-NDFA's and change the sub-NDFA's according to what operation is used ($*$, $|$ or $\cup$).

But that gives me the problem that I don't know if the previous sub-NDFA will have produced a string of odd or even length when arriving at the current sub-NDFA.

Example: If you have '$aa^{\ast} a$' you would have 3 sub-NDFA's ($a$, $a^{\ast}$ and $a$), but how can I know if I would have to change the last NDFA to $\#$ instead of leaving it at "$a$"?

All help is welcome!

Answer 1

I like Gadi’s answer, but you may want one with a different flavor.

Start with a DFA $M$ that recognizes $L$. Replace each state $s$ of $M$ by a pair of states, $s^0$ and $s^1$, and replace every transition $s \stackrel{x}\longrightarrow t$ by the transitions $s^0 \stackrel{x}\longrightarrow t^1$ and $s^1 \stackrel{x}\longrightarrow t^0$. The idea is that after reading $n$ letters, the new machine will be in a state with superscript $n\text{ mod }2$. Thus, if $s_0$ is the initial state of $M$, $s_0^0$ should be the initial state of the new machine, $M'$. Now you should be able to collapse $M'$ to a DFA that recognizes $K$.

Answer 2

A simple solution using the well-known closure properties: Mark every second character using an inverse homomorphism, then use another homomorphism in order to transform marked characters to #.

Details: Define a homomorphism: $h:\Sigma\cup\Sigma^\prime\to\Sigma ^*$ such that $h(\sigma)=h(\sigma^\prime)=\sigma$. Now we have that $h^{-1}(L)\cap (\Sigma\Sigma^\prime)^*$ is that set of all words of L of even length with every second character marked. Similarly you can mark all the odd-length words and take the union.

Now define another homomorphism $g:\Sigma\cup\Sigma^\prime\to\Sigma\cup\{\#\}$ such that $g(\sigma)=\sigma$ and $g(\sigma^\prime)=\#$. Apply $g$ to the result of the previous step and you are done.

Note that I could have used a more specific version of $h$, but the general version I used here is helpful in many other cases as well.