2
$\begingroup$

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?

2 Answers 2

1

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

  • 0
    @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.2012-09-30
1

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