1
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Nov 18, 2020 at 14:20
  • $\begingroup$ You're right got that mixed up, will try to fix it in a minute :) $\endgroup$ Nov 18, 2020 at 14:21
  • $\begingroup$ Should be ok now :) $\endgroup$ Nov 18, 2020 at 14:30

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.