Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

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?

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

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

share|cite|improve this answer
Nice! Just a quick question about $M_1$, can we take care of the last symbol separately (instead of the first)? It seems it has some uncertainties, but the non-deterministic feature will make sure the language is accepted when there exists a corresponding string in $L$. – Jing Zhang Sep 30 '12 at 2:01
@JingZhang: I think so, yes; I just found it easier to think about what happens the other way when I was writing up the answer. – Brian M. Scott Sep 30 '12 at 2:15

(1) Non-messy implementation of the construction is as follows. Change the state set from $Q$ into $Q\times \{0,1\}$ and change the instructions so that upon reading a symbol we switch between $0$ and $1$. Additionally when reading an even numbered symbol in the original machine, the new one will read the empty word $\lambda$.

Thus from $(p,a,X,q,\alpha)$ we get $(p0,a,X,q1,\alpha)$ and $(p1,\lambda,X,q0,\alpha)$ assuming $a\in\Sigma$. Also from $(p,\lambda,X,q,\alpha)$ we get $(p0,\lambda,X,q0,\alpha)$ and $(p1,\lambda,X,q1,\alpha)$.

(2) That is harder, but as in (1) above makes simple changes in the instructions based on info stored in the states. Assume we run a variant of the deterministic PDA for the given language (on nonempty strings). When the new PDA sees the first final state we ignore that (and keep track of that event in the state). When this has happened change the transitions so that we will read $c$ instead of $b$, otherwise the machine is a copy of the original one. Accept when the (second) final state is reached. The new machine will accept $a^nb^nc^n, n\ge 1$. This is due to the fact that for a deterministic machine the computations on $a^nb^n$ must be a prefix of computations on $a^nb^{2n}$. One technical point to take notice is that there must be a real symbol between before we start accepting. Otherwise long computations on $\lambda$ get you into trouble.

(edit) Ah, I forgot to add that in this way we get a contradiction, so there is no deterministic PDA for the original language.

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.