# Proving that a specific language is a CFL, and that another language is not a CFL

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.

• 1. Use the non-determinism of PDAs (if you use a PDA) 2. If $x'1z' \in C_1$ and the $1$ is the middle $1$ mentioned in the definition, what do you know about $|x'|$ and $|z'|$.? $C_2:$ Consider a long word with few (not to close) $1$s. If you found a solution, consider answering yourself. Mar 10 '13 at 23:17
• I like the question! Harder than the usual ones. Mar 10 '13 at 23:26
• @frafl, for the PDA, $|x'|=|z'|$, right? I'm not sure how to keep track of the length of the middle section though. If I use the stack to keep track of the lengths of the left and right sections, how can I make sure that the length of the middle section is shorter? The moment I start popping off the stack to test the middle section's length, I lose information about the left section's length, which I need for the right section. Mar 11 '13 at 2:55
• No, they don't have to be equal (see the answer below). Using this extremes you don't have to count the length of the middle part, because their is no middle part anymore, only left and right. Now let your PDA guess, which part is longer and whether a $1$ is the one you search. Mar 11 '13 at 6:53

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.
• That is wrong. The description of $C_1$ only says there is a 1 somewhere near the middle (and two for $C_2$), so $1111 \ldots 11 \in C_{1,2}$. Mar 11 '13 at 1:11