1
$\begingroup$

I have following language $L:= \{a^n b^n c^m \mid n \neq m; n,m \ge 0 \}$ and would like to use proof by contradiction by applying Pumping Lemma for CFLs to show that $L$ is not a CFL.

In any case, i need to choose $w = uv^iwx^iy$ so that $w \in L$.

I tried $a^p b^p c^{p+1}$ , $a^p b^p c^{p+p!}$ ($p$ - Pumping Length) and couple of others. All of my proofs converged to 5 cases:

  1. Only A (both $v$ and $x$ pump $a$'s),
  2. A & B ($v$ pumps $a$'s, $x$ pumps $b$'s),
  3. Only B (both - $b$'s),
  4. B & C ($v$ - $b$'s, $x$ - $c$'s),
  5. Only C (both - $c$'s).

Cases #1-#4 are not a problem, but in #5 $w \in L$ regardless $i$ chosen (cause condition is not broken). Thus, how do i choose the word here?

This page hints to take p!-Trick, but it doesn't work here..?

$\endgroup$

1 Answer 1

1
$\begingroup$

Your analysis is correct. In order to keep the $a^n b^n c^m$ structure of the string, the only ways to pump are case (2) pump both $a$'s and $b$'s, or case (5) pump only $c$'s. All other case will distroy the structure of the string.

You applied the $p!+p$-trick, and consider the string $a^p b^p c^{p!+p}$. In case (2) this will indeed pump to a string of the form $a^{p!+p} b^{p!+p} c^{p!+p}$ outside of the language because all segments are of equal length. No luck in case (5), you are right.

The solution is to apply Ogden's Lemma. The Lemma is like the common Pumping Lemma for CF languages where we count so called "marked" positions in a word. By marking the $a$'s in the string one is forced to pump $a$'s, so only case (2) applies.

Apart from a mirror-like symmetry this is explained in the application for inherent ambiguity of Ogden in wikipedia.

$\endgroup$
2
  • $\begingroup$ Thanks for quick answer! I tried to understand Ogden's Lemma alone, but have no materials that explain it in simplified way :( So, we have w = $a^p b^p c^{p! + p}$. Then we apply Ogden's Lemma and mark $a$'s. After that we apply conditions of Ogden's Lemma ($vxy$ has $\leq$ p $a$'s & $vy$ has $\geq$ 1 $a$'s & $uv^i x y^i z \in L$. Altogether it means we pump $a$'s, leaving $b$'s and $c$'s constant, thus coming to (1) & breaking it's condition successfully. Why are we allowed to ignore (5) while applying Ogden's Lemma though? Don't get it :( $\endgroup$ Sep 19, 2023 at 22:00
  • $\begingroup$ [ Sorry. My text was OK, but I wrote the wrong number. I hope I am OK now. ] For (ordinary) pumping we can restrict to cases (2) pumping same number of a's and b's or (5) pumping only c's. Other cases will break the pattern of the language. Using Ogden and marking a's means we have to pump a's. That forbids case (5) since it does not pump any marked symbol, and we may consider (2) as last possibility. Finally for (2) the p! trick works. $\endgroup$ Sep 20, 2023 at 2:50

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.