# How can I prove this language is not context-free?

I have the following language

$\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$

I am trying to determine which Chomsky language class it fits into. I can see how it could be made using a context-sensitive grammar so I know it is atleast context-sensitive. It seems like it wouldn't be possible to make with a context-free grammar, but I'm having a problem proving that.

It seems to pass the fork-pumping lemma because if $uvwxy$ is all placed in the third part of any word (the section with all of the $2$s). It could pump the $v$ and $x$ as many times as you want and it would stay in the language. If I'm wrong could you tell me why, if I'm right, I still think this language is not context-free, so how could I prove that?

• I'm not sure how to make it a formal proof, but ensuring i<=j<=k requires context (the value of the previous variable). – Kevin Mar 21 '12 at 18:32
• possible duplicate of How to prove that a language is not context-free? – Raphael Mar 21 '12 at 21:37
• @Raphael, I read that post before this one and didn't know how to apply it to my example because of it's abstractness. With the relationship of each character being >= the number of previous characters, I couldn't see how to split the uxyzv into the word to use Ogden's lemma. BlueMagister and jmad expanded on the other post to make it clear for my example. – justausr Mar 21 '12 at 22:26
• @Raphael I disagree that this is a trivial application of the general case. Choosing which method to use and what example to apply it to is not so easy. – Gilles 'SO- stop being evil' Mar 21 '12 at 22:58

You can force the pumping to be in some places, using Ogden's lemma, for example by marking all the 0's.

Suppose it is context free, then Ogden's lemma gives you a $p>0$, you give it $w=0^p1^p2^p$ which is in the language, and you "mark" all the 0's. Then any factorisation $w=uxyzv$ must be such that there is a $0$ in $x$ or $z$. You can also assume $x=a^k$ and $z=b^m$ since $xx$ and $zz$ must be substrings of your language.

1. If $z=0...0$ then $w=ux^2yz^2v$ has more 0's than 1's

2. If $x=0..0$ and $z=1..1$ then $w=ux^2yz^2v$ has more 1's than 2's.

3. If $x=0..0$ and $z=2..2$ then $w=ux^2yz^2v$ has more 0's than 1's.

So $ux^2yz^2v$ is not a word of your language. Therefore, it is not context-free.

For other techniques, see the discussion: How to prove that a language is not context-free?

• Is this for the same language that I have? It seems to be for the similar language where all of the 0's 1's and 2's are of equal length. This language has the number of 2's >= the number of 1's >= the number of 0's – justausr Mar 21 '12 at 18:53
• Yes it is, but using any of all the pumping lemmas, you get to choose the word (and I chose $0^p1^p2^p$): Ogden's lemma is supposed to work for all of them. – jmad Mar 21 '12 at 18:55
• Gotcha, I've never heard of ogden's lemma so I'll have to look into it. Was I right is stating it fails the pumping lemma? – justausr Mar 21 '12 at 18:57
• @justausr neither have I, until recently (and thanks to the discussion I referred to). And yes you were right: the pumping lemma does almost the same thing but not choosing where to pump makes it useless here. – jmad Mar 21 '12 at 19:28

The pumping lemma should solve your problem regarding the third part of the word; note that when you split $z = uvwxy$, any combination of $uv^nwx^ny$ is also in the language, including when $n = 0$. Try that.

EDIT: As jmad states, the Pumping Lemma is like a game:

1. The pumping lemma gives you a $p$
2. You give a word $s$ of the language of length at least $p$
3. The pumping lemma rewrites it like this: $s=uvxyz$ with some conditions ($|vxy|≤p$ and $|vy|≥1$)
4. You give an integer $n≥0$
5. If $uv^nxy^nz$ is not in $L$, you win, $L$ is not context free.

So what you have to do is state a word, break down 3 into cases, and show that for each case you can find an $n$ such that the resulting word isn't in the language.

When you split $s=uvxyz$, think of all the cases that $vxy$ can fall into. You note that if $vxy$ does not fall into the 2's, then it is easy to pump the 0's and 1's until they outnumber the 2's, and then you have a word that's not in the language. My suggestion is that, if $vxy$ falls into 2 territory, you can also make $v$ and $y$ disappear by setting $n=0$, so $uv^nxy^nz = uxz$. Then by eliminating a 2 you could arrive at a word that doesn't fall in the language.

• Are you saying put all of uvwxy in the section with 2's? – justausr Mar 21 '12 at 22:04
• If it's given the right word. I'll elaborate in my answer. – Blue Magister Mar 21 '12 at 22:05
• Here, try it now. I'm not sure if my pumping lemma is the same as your pumping lemma, so I appeal to Wikipedia. – Blue Magister Mar 21 '12 at 22:38