Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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? –  meh Mar 13 '13 at 4:14

2 Answers 2

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

share|improve this answer

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.

share|improve this answer
    
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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