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

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?

• You would, if it were a context-free language. Which I think it is not. Have you tried the pumping lemma for Context Free Languages? – liamdalton Mar 13 '13 at 4:14

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$.

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.

• @Thresh: Could you please let me know whether you've seen this answer? You've now asked five questions on this site without providing any feedback on whether the answers were helpful to you. I think my general tip at the end might be quite useful for you, so it'd be nice to know whether you've seen it. – Tara B Mar 14 '13 at 12:18
• Thanks for the answer. I think i sort of get your answer... just need to apply it to the pumping lemma – Thresh Mar 14 '13 at 17:41
• @Thresh: Thanks for the reply! Brian's answer should hopefully get you started with applying the pumping lemma. If you need further clarification on any answers, just leave a comment explaining what you don't understand. – Tara B Mar 14 '13 at 17:43
• I'm still a little bit confused on which/how many cases I would have to prove in the proof. – Thresh Mar 16 '13 at 22:56