3
$\begingroup$

I have an exam and in preparation I found this language. We are supposed to determine where in Chomsky hierarchy it stands. The language is $L=\{a^ib^jc^k : i\leq j\leq k\}$. I can easily build a linear turing machine, that would delete a, b and c for each a and then b and c for each b and if the only thing left, will be c, then the word belongs to the language. So I know the language is context-sensitive. What I can't figure out is if the language is context-free.

I tried to build a pushdown automata but I couldn't find any. I also tried to use the pumping lemma but wasn't able to find a good word to prove it's not context-free. Could you help me?

$\endgroup$
  • $\begingroup$ Okay so I will set n to p-1 therefor make sure that the vxy (w=uvxyz) contains max two letters. So if I get b's and c's it will work but if I get a's and b's I can easily get rid of them and the word will stll belong to the language. I could use i=high number and pump a's and b's and therefor find a word that has more a's and b's than c's which doesn't belong to the language. But I thought that the pumping lemma says I have to have one i for every splitting. Or can I find a different i for each splitting? $\endgroup$ – user64003 Jan 2 '17 at 13:36
  • $\begingroup$ I didn't know that. Thank you so much. Should I check something to show that the question was answered? $\endgroup$ – user64003 Jan 4 '17 at 10:48
  • $\begingroup$ At to moment you cannot accept, because this was only a comment. I will copy-paste this into an answer. $\endgroup$ – Hendrik Jan Jan 4 '17 at 11:26
1
$\begingroup$

A word like $a^nb^nc^n$ should work. Remember that the pumping lemma also allows you to pump down, i.e., delete the pumping segments.

Also, each splitting $z=uvxyz$ can have its own "contradiction" to show it does not adhere to the pumping lemma. You can use different arguments, so different $i$ for each splitting. That is very natural here as $a$ has the minimal number of occurrences, and contradiction is reached by adding occurrences, whereas for $c$ deletion (choosing $i=0$) will get you into trouble.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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