Is L a context free langauge? context-free grammar?

Question

Is $L = \{ a^{(i)} b^{(i)} c^{(j)} \mid i \le j\}$ a context-free language?

Would i just create a context free grammar for this?

Answer 1

HINT: Try using the Bar-Hillel pumping lemma to show that $L$ is not context-free. If $p$ is the pumping length, start with the word $w=a^pb^pc^p$. The pumping lemma tells you that $w$ can be decomposed as $w=uvxyz$ in such a way that $|vxy|\le p$, $|vy|\ge 1$, and $uv^kxy^kz\in L$ for all $k\ge 0$. Note that since $|vxy|\le p$, at most two of the letters $a,b$, and $c$ can occur in the substring $vxy$. With a bit of thought you can show that no matter where in $w$ the substring $vxy$ appears, you’ll get a word not in $L$ either by pumping up to a $k>1$ or by pumping down to $k=0$.

Answer 2

You've already got a hint for a proof. I just want to explain how you could guess that $L$ probably isn't context-free. This is NOT at all a proof!

Suppose you have a pushdown automaton recognising $L$. First you read $a^i$. You're going to have to remember how many $a$'s there were, so you can check them against the coming $b$'s. That's fine, you can do it on the stack. But now to check them against the $b$'s, you're probably going to have to pop the $a$'s off the stack. While you're doing that, you have no way of storing the number of $b$'s if you have more of them than states. And you've gotten rid of the information about how many $a$'s you had. So you have no way to check that $i\leq j$ when you read the $c$'s.

It's a good idea to check whether you can make this sort of argument for it seeming to be impossible for $L$ to be context-free before you launch into trying to construct a grammar for it! (And then if you can, try the pumping lemma as Brian and meh have suggested.)

A general tip is that if you have to check the number of occurrences of one symbol against the numbers of occurrences of at least two other symbols, there's a very good chance it won't be context-free.