Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 1 down vote accepted

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

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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