11
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ I'm not sure how to make it a formal proof, but ensuring i<=j<=k requires context (the value of the previous variable). $\endgroup$
    – Kevin
    Mar 21, 2012 at 18:32
  • 1
    $\begingroup$ possible duplicate of How to prove that a language is not context-free? $\endgroup$
    – Raphael ♦
    Mar 21, 2012 at 21:37
  • $\begingroup$ @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. $\endgroup$
    – justausr
    Mar 21, 2012 at 22:26
  • $\begingroup$ @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. $\endgroup$
    – Gilles 'SO- stop being evil'
    Mar 21, 2012 at 22:58

2 Answers 2

Reset to default
7
$\begingroup$

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?

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$
    – justausr
    Mar 21, 2012 at 18:53
  • 1
    $\begingroup$ 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. $\endgroup$
    – jmad
    Mar 21, 2012 at 18:55
  • $\begingroup$ 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? $\endgroup$
    – justausr
    Mar 21, 2012 at 18:57
  • $\begingroup$ @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. $\endgroup$
    – jmad
    Mar 21, 2012 at 19:28
5
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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