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 Aug 27 '14 at 11:06
  • 1
    $\begingroup$ Our reference questions should help you. $\endgroup$ – Raphael Aug 27 '14 at 15:31

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.

| cite | improve this answer | |
  • $\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 Aug 27 '14 at 11:56
  • 1
    $\begingroup$ You can not show that a language is context-free with the pumping lemma. $\endgroup$ – FrankW Aug 27 '14 at 11:59

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.