1
$\begingroup$

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.

2 Answers 2

1

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.

  • 0
    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.2011-12-07
  • 0
    @Brian: My suggestion is hinting at creating a machine that recognizes $\text{alt}(L)$, by effectively "ignoring" every other character.2011-12-07
  • 0
    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.2011-12-07
  • 0
    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.2011-12-07
  • 0
    You guys discussion helps me a lot ;) Great thanks.2011-12-08
1

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