I have been working on the following two problems:
1) Given any context free language L, form a new language by taking symbols at the odd positions, i.e. $w=a_1a_2\dots a_n \mapsto w'=a_1 a_3 a_5 \dots a_k$ if n is even then k=n-1 otherwise n. Is the resulting language context free for any given context free language $L$?
2) How to show $\{a^n b^n : n\geq 0\} \cup \{a^n b^{2n}: n\geq 0\}$ is not deterministic context free?
For the second problem, my initial thought was trying to prove its complement (maybe intersecting with some regular languages) is not context free. But it did not work out so well. So I think it might be reasonable to prove that it or its complement is inherently ambiguous then it is not deterministic context free. However, the ideas are quite hard to implement. Any thoughts?
Best Answer
(1) The details look a bit messy, but if you have a PDA $M$ that recognizes $L$, you can modify it so that when it reads a symbol $s$, it takes one of the actions that $M$ could have taken on reading $st$ for any $t$ in the alphabet; this is a finite set of possibilities. You now have a PDA $M_0$ that recognizes any word of the new language that is derived from a word of $L$ of even length. You can also modify $M$ to get a PDA $M_1$ that reads the first symbol of the input exactly as $M$ would, but thereafter on reading a character $s$ takes a choice of actions corresponding to what $M$ can do on reading $ts$ for each possible input character $t$. $M_1$ recognizes the words of the new language that are derived from words of $L$ of odd length. Now combine $M_0$ and $M_1$ into a PDA $M'$ that begins by choosing whether to run in $M_0$ or in $M_1$.