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
    $\begingroup$ 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. $\endgroup$
    – frafl
    Commented Mar 10, 2013 at 23:17
  • 3
    $\begingroup$ I like the question! Harder than the usual ones. $\endgroup$ Commented Mar 10, 2013 at 23:26
  • $\begingroup$ @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. $\endgroup$ Commented Mar 11, 2013 at 2:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – frafl
    Commented Mar 11, 2013 at 6:53

1 Answer 1


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)

  • $\begingroup$ Brilliant, didn't think of using extreme forms of the string to achieve desired effect! I'll try it out. $\endgroup$ Commented Mar 10, 2013 at 23:47
  • $\begingroup$ 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}$. $\endgroup$
    – vonbrand
    Commented Mar 11, 2013 at 1:11
  • 2
    $\begingroup$ It is not a solution, it is a hint. $\endgroup$ Commented Mar 11, 2013 at 7:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.