1
$\begingroup$

I was given two languages

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

and

$$L_2=\{a^mb^{m+1}\}$$

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.

Improve this question
$\endgroup$
2
  • 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, 2014 at 11:06
  • 1
    $\begingroup$ Our reference questions should help you. $\endgroup$
    – Raphael ♦
    Aug 27, 2014 at 15:31

1 Answer 1

Reset to default
0
$\begingroup$

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.

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

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.