523 views

### How to prove that $L = \{a^n b^m a^n b^m \mid n,m \ge 0\}$ is not a CFL?

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 ...
### Is the language $\{a^n b^n c^i | i \leq n\}$ context free?
I'm trying to apply the CFL pumping lemma. And, I've already tried words $a^pb^p$ and $a^pb^pc^p$. Not sure where to go from here.