HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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.

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)

Context

StackExchange Computer Science Q#10437, answer score: 2

Revisions (0)

No revisions yet.