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

Problem Given a language $L$ is context-free, must $\operatorname{alt}(L)$ is also context free? where $$\operatorname{alt}(L) = a_1a_2a_3 \ldots, \quad L = a_1b_1a_2b_2a_3b_3 \ldots$$

I couldn't find a counter example so I guess it must be CF also. But I couldn't find a way how to prove it correctly. Anyone could give me a hint on this? Thank you.

share|cite|improve this question
up vote 1 down vote accepted

Hint: Create duplicates of all states in the PDA recognizing $L$, with the duplicates effectively keeping track of the parity of the index within a word. A duplicate should be accepting iff its original is accepting, and transitions should alternate between the two copies of the states to reflect the change in parity. Be careful on what gets pushed/popped from the stack on the transitions, there are some subtleties that must be dealt with.

share|cite|improve this answer
I think that Chan wants to go the other way: recognize those words which can be obtained from words in $L$ by dropping out the letters in even positions. – Brian M. Scott Dec 7 '11 at 19:41
@Brian: My suggestion is hinting at creating a machine that recognizes $\text{alt}(L)$, by effectively "ignoring" every other character. – Brandon Carter Dec 7 '11 at 19:57
Did you mean to simulate the ‘ignored’ letters by $\varepsilon$ transitions to the duplicates? If so, the hint was opaque enough that I misinterpreted it badly, but I agree that something like that could be made to work. – Brian M. Scott Dec 7 '11 at 20:13
Yes, for each transition $a/b/c$ from $s_1$ to $s_2$ in the original PDA, you put in transitions $\epsilon/b/c$ from $s_1'$ to $s_2$ and $a/b/c$ from $s_1$ to $s_2'$, where $s_1', s_2'$ are the duplicate states of $s_1, s_2$, respectively. – Brandon Carter Dec 7 '11 at 20:23
You guys discussion helps me a lot ;) Great thanks. – Chan Dec 8 '11 at 1:42

Start with a pushdown automaton $M$ that recognizes $L$. Let $s_0$ be the initial state. If there are any transitions from $s_0$ to $s_0$, add a state $s_0'$ that will be the new initial state, and add an $s_0'\to s_0$ transition for each of the original $s_0\to s_0$ transitions. This ensures that $a_1$ is handled properly.

Now suppose that you’re in state $s$ reading some letter $a$. Look at what $M$ would do from state $s$ on reading every possible pair of letters $xa$, and provide an appropriate transition for each of these actions. (Be sure to account for what happens to the stack.)

This is based on the assumption that you just want to accept words that derive from words in $L$ of even length. If you also want to accept $a_1a_2$ when some $a_1b_1a_2\in L$, for instance, you’ll probably find it easier to modify the transitions for input $a$ to mimic the possible $ax$ transition of $M$.

share|cite|improve this answer
Thanks a lot Brian, I know how to start now ;) – Chan Dec 8 '11 at 1:41

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.