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?

justausr

Posted 2012-03-21T18:21:10.833

Reputation: 425

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 – 2012-03-21T18:32:55.363

possible duplicate of How to prove that a language is not context-free?

– Raphael – 2012-03-21T21:37:23.450

@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 – 2012-03-21T22:26:42.513

@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' – 2012-03-21T22:58:53.197

Answers

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.

If $z=0...0$ then $w=ux^2yz^2v$ has more 0's than 1's
If $x=0..0$ and $z=1..1$ then $w=ux^2yz^2v$ has more 1's than 2's.
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?

jmad

Posted 2012-03-21T18:21:10.833

Reputation: 9 129

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 – 2012-03-21T18:53:31.587

1Yes 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 – 2012-03-21T18:55:48.120

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 – 2012-03-21T18:57:23.347

@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 – 2012-03-21T19:28:18.877

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:

The pumping lemma gives you a $p$

You give a word $s$ of the language of length at least $p$

The pumping lemma rewrites it like this: $s=uvxyz$ with some conditions ($|vxy|≤p$ and $|vy|≥1$)

You give an integer $n≥0$

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.

Blue Magister

Posted 2012-03-21T18:21:10.833

Reputation: 151

Are you saying put all of uvwxy in the section with 2's? – justausr – 2012-03-21T22:04:02.013

If it's given the right word. I'll elaborate in my answer. – Blue Magister – 2012-03-21T22:05:58.900

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 – 2012-03-21T22:38:37.587