# I'm trying to prove this language is not context-free: {a^x b^y c^z | where x=z and x<y}

So far i've tried with making x = z = p and y = 2*p, but it seems that if I place vxy to represent all b's then I can't get a contradiction.

• Try $y = p + 1$ Nov 18, 2020 at 14:04

The pumping lemma for context-free languages says the following:
For every context-free-language $$L$$ there exists a constant $$p$$ such that for every word $$s \in L$$ of length at least $$p$$, we can write $$s = uvwxy$$ and:

• $$|vx| \ge 1$$
• $$|vwx| \le p$$
• $$uv^nwx^ny \in L$$ for $$n \ge 0$$

To prove that $$L = \{a^xb^yc^z: x < y \land x = z \}$$ is not context-free we will do the following:
Assume language $$L$$ i context-free and let $$p$$ be the constant from the pumping lemma.
Take the word $$s = a^pb^{p+1}c^p$$, which is clearly in $$L$$, and express it as $$s = uvwxy$$ as is stated in the lemma.
We know that $$|uvw| \le p$$ so $$v$$ consists only of $$a$$'s.
Denote $$s_n = uv^nwx^ny$$
Now consider the possible cases:

1. If either $$v$$ or $$x$$ contain more than one letter, than $$s_2$$ will not be of the form $$a^*b^*c^*$$, so we know that $$v$$ and $$x$$ will consist of at most one letter.
2. If $$v$$ is empty and $$x$$ consists of $$b$$'s then $$s_0$$ will not have more $$a$$'s than $$b$$'s. If $$x$$ consists of $$c$$'s then $$s_2$$ will have more $$c$$'s than $$a$$'s.
3. If both $$v$$ and $$x$$ are non-empty then if $$v$$ consists of $$a$$'s and $$x$$ of $$b$$'s then we in $$s_2$$ we will have more $$a$$'s than $$c$$'s. If $$v$$ consists of $$a$$'s and $$x$$ of $$c$$'s than for large enough $$m$$ in $$s_m$$ we will have more $$a$$'s than $$b$$'s. If $$v$$ consists of $$b$$'s and $$x$$ of $$c$$'s then in $$s_2$$ we will have more $$c$$'s than $$a$$'s.
4. If $$v$$ and $$x$$ consist of the same letter (i.e $$w$$ is empty) then following the same type of reasoning we will also reach a contradiction.

Thus we have reached a contradiction for every possible case and so $$L$$ is not context-free.

• You don't have the pumping lemma for context free languages quite right. The second condition should be $|vwx| \leq p$, so your case analysis comes out wrong. There's nothing that forces $v$ to be near the start of the string, so you can't assume it's only $a$s. However, you can state three similar cases: $vx$ contains some $a$s and hence no $c$s, only $b$s, or some $c$s and hence no $a$s. The first and third give the $x \neq z$ contradiction, and the second (with $s_{0}$) gives the $x = y$ contradiction. Nov 18, 2020 at 14:20
• You're right got that mixed up, will try to fix it in a minute :) Nov 18, 2020 at 14:21
• Should be ok now :) Nov 18, 2020 at 14:30