Context Free or Context Sensitive and why

Question

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.

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.