# How can I prove that this language is regular?

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!

-
Ignore regular expressions for this. Just start with an automaton that recognizes $L$ and construct another one that recognizes $K$. – Henning Makholm Oct 25 '11 at 15:34
The regular expressions don't really matter, they're just a way to construct a NDFA. But since I don't have an actual language 'L', I wouldn't know how to create an automaton that recognizes L... I have to do it for any language L, so wouldn't I have to show how it would work for Kleene-star, union and concat? – GoingPlaces Oct 25 '11 at 15:37
You don't need to construct the automaton. Just assume you have one (which you're allowed to do because you're told that $L$ is regular), and then find a general algorithm for systematically constructing an automaton for $K$ if you're given an automaton for $L$. (Obscure hint: "bipartite"). – Henning Makholm Oct 25 '11 at 15:39
I have an algorithm that works for automatons that don't have loops, and I end up with a bipartite, so I think I'm on the right track. However, when I introduce loops, it falls apart completely... – GoingPlaces Oct 25 '11 at 16:13
How can the presence or absence of loops influence the algorithm? Try editing the question to include your current algorithm, and we'll see if we can get it straightened out. – Henning Makholm Oct 25 '11 at 16:21

## 2 Answers

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

-
This is a very nice solution as well. It may be instructive to think of this construction as "cloning" M and making transitions jump between the copies. – Gadi A Oct 25 '11 at 19:40
Thanks, I've used this method and it worked great. I never thought about looking at it from a more abstract side. (I was just trying to transform graphical DFA's). – GoingPlaces Oct 25 '11 at 23:00
It is even simpler to use the same idea on NFA's because no collapsing is needed then. – Henning Makholm Oct 26 '11 at 2:07

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.

-