I'm stuck with the proof. I've tried Ogden's lemma but it doesn't seem to help.

The problem is: Let $N$ be the constant of Ogden, let $z = a^N b^{N+1} a^N b^{N+1}$, and $z = uvwxy$. Now I should choose which symbols to mark.

I tried with all the first $N$ $a$s (and also other combinations), but then for $v=a^j$ and $x=a^j$ (and $w=b^{N+1}$) pumping doesn't get a string out of $L$. My idea is that I should involve both $a$s and $b$s between the marked symbols and somehow force the pumping for both, but I don't know how.

  • $\begingroup$ Suppose you mark all the symbols. You're allowed to do that (which produces the pumping lemma). Now find a pumpable decomposition with no more than $p$ symbols. $\endgroup$ – rici Jul 1 '18 at 5:15
  • $\begingroup$ You can do this using the pumping lemma. Use the condition $|vwx| \leq N$. $\endgroup$ – Yuval Filmus Jul 1 '18 at 6:28
  • $\begingroup$ @rici this may be a misunderstanding of mine, but... i need to prove that for every possible decomposition of $z$ in $uvwxy$ there is a pumping that "push" $z$ out of $L$. $\endgroup$ – francesco bertolotti Jul 1 '18 at 7:13
  • 1
    $\begingroup$ Possible duplicate of How to prove that a language is not context-free? $\endgroup$ – David Richerby Jul 5 '18 at 16:51

Let $N$ be the constant of the Pumping Lemma for CFL.

Let be $z=a^N b^{N+1} a^N b^{N+1}$.

let's analyze some of the possible decompositions of $z$ in $uvwxy$:

(note that $vx$ has always at least one symbol)

  1. $u=\epsilon$, $v=a^*$, $w=a^*$, $x=a^*$, $y=b^{N+1} a^N b^{N+1}$. just pumping once we get a string out of $L$.
  2. $u=a^*$, $v=a^*$, $w=a^*$, $x=a^*$, $y=b^{N+1} a^N b^{N+1}$. same as above.
  3. $u=a^*$, $v=a^*$, $w=a^*$, $x=a^*b^*$, $y=b^* a^N b^{N+1}$. same.
  4. $u=a^*$, $v=a^*$, $w=a^*$, $x=b^*$, $y=b^* a^N b^{N+1}$. same.
  5. $u=a^*$, $v=a^*$, $w=a^*b^*$, $x=b^*a^*$, $y=a^* b^{N+1}$. it can't happen because $\mid vwx \mid$ would be $>N$.
  6. $u=a^*$, $v=a^*$, $w=a^*b^{N+1}$, $x=a^*$, $y=a^* b^{N+1}$. it can't happen because $\mid vwx \mid$ would be $>N$.
  7. $u=a^*$, $v=a^*$, $w=b^{N+1}$, $x=a^*$, $y=a^* b^{N+1}$. it can't happen because $\mid vwx \mid$ would be $>N$.
  8. $...$

Anyway the problematic case is 7. because it could be $u=a^k$, $v=a^j$, $w=b^{N+1}$, $x=a^j$, $y=a^kb^{N+1}$ with $k+j=N$, so that pumping doesn't push $z$ out of $L$. But again, it can't happen otherwise we would have $\mid vwx\mid >N$, which is not possible and it is guaranteed by the lemma.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.