[Solved]: Proving that a specific language is a CFL, and that another language is not a CFL

Problem Detail: 

I have two languages $C_1$ and $C_2. \left(\Sigma=\{0,1\}\right)$:

$C_1=\left\{xyz\mid x,z \in \Sigma^*, y \in \Sigma^*1\Sigma^*, \text{ where } |x|=|z| \geq |y|\right\}$, and $C_2=\left\{xyz\mid x,z \in \Sigma^*, y \in \Sigma^*1\Sigma^*1\Sigma^*, \text{ where } |x|=|z| \geq |y|\right\}$

I want to show that $C_1$ is a CFL, while $C_2$ is not a CFL. I'm trying to create a grammar / pushdown automata that accepts $L(C_1)$, but the $|x|=|z| \geq |y|$ part is throwing me off. I plan on using the pumping lemma for $C_2$, but I'm not sure which string to pump.

Asked By : user1526710

Answered By : Hendrik Jan

First you have to realize that the extremes of the strings are of the form $0^n10^{2n-1}$ and $0^{2n-1}10^n$. You can get a language similar to that by the grammar $S \to 1 \mid 0S00 \mid 00S0$. From this some fine-tuning is needed. First to get $1$'s at the places where now only $0$'s are. Then to get the boundary conditions exactly right.

For the non-context-free other language I would also consider an "extreme" string, similar to $0^n10^n10^n$. That is not exactly one from the language, but close enough for a start.

(Nice exercise, that problem 2.48a in Sipser)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10437

3.2K people like this

 Download Related Notes/Documents