I was given two languages

$$L_1=\{0^k1^k0^m\mid k,m \in \mathbb{N}\text{ and }k < m\}$$



and I was asked to prove whether they are context free or sensitive.

For $L_1$ : I did pumping lemma and I cannot clearly rule out the context free. So I accepted that it is and tried to do a high level description of a pda. I check the first part of the language $0^k1^k$ like this: push A for every 0 you read pop A when you read 1. If the stack is not empty reject. But I have trouble finding how to check the second part, $1^m$ with $m>k$. So now I do not know if it is indeed a context free.

For $L_2$ I followed a similar method with $L_1$ and again I stuck in the $m+1$ part.

Can someone help me? I am not proficient in grammar creation and pdas and lbas were only taught in our class in high level descriptions like the above.

  • 2
    $\begingroup$ Note that context-free and context-sensitive are not mutually exclusive. In fact, every context-free language is context-sensitive as well. $\endgroup$
    – FrankW
    Commented Aug 27, 2014 at 11:06
  • 1
    $\begingroup$ Our reference questions should help you. $\endgroup$
    – Raphael
    Commented Aug 27, 2014 at 15:31

1 Answer 1


Hint 1: You can write the languages as $0^k1^k0^k0^{m-k}$ and $a^mb^mb$.

Hint 2: If a language looks non-context-free, but the pumping lemma does not show this, you can try Ogden's lemma.

  • $\begingroup$ Ok thank you for both the answer and the edit. So with your hint the L1 is context sensitive, can be proved with ogden's lemma and the L2 is context free? $\endgroup$
    – Saraki
    Commented Aug 27, 2014 at 11:56
  • 1
    $\begingroup$ You can not show that a language is context-free with the pumping lemma. $\endgroup$
    – FrankW
    Commented Aug 27, 2014 at 11:59

Your Answer

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

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