patternMinor
Proving that a specific language is a CFL, and that another language is not a CFL
Viewed 0 times
provingcfllanguagethatanotherspecificandnot
Problem
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.
$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.
Solution
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)
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)
Context
StackExchange Computer Science Q#10437, answer score: 2
Revisions (0)
No revisions yet.