3
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 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 Mar 10 '13 at 23:17
  • 2
    $\begingroup$ I like the question! Harder than the usual ones. $\endgroup$ – Yuval Filmus Mar 10 '13 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$ – user1526710 Mar 11 '13 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 Mar 11 '13 at 6:53
2
$\begingroup$

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)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Brilliant, didn't think of using extreme forms of the string to achieve desired effect! I'll try it out. $\endgroup$ – user1526710 Mar 10 '13 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 Mar 11 '13 at 1:11
  • 1
    $\begingroup$ It is not a solution, it is a hint. $\endgroup$ – Hendrik Jan Mar 11 '13 at 7:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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