Is the language context free?

Question

Consider the language

$$L=\{0^n w 1^m \mid \text{where}\; w \text{ belongs to } (a+b)^* , n \text{ is number of } a \text{'s in }w, m \text{ is no of } b\text{'s in }w \text{ and }n>m \}$$

I can surely say that this is not a DCFL but I am not sure about it being CFL or recursive. I have no idea how to proceed.

Can someone please help ?

Answer 1

A language $L_1$ is recursive if there exists a Turing machine that accepts every string in $L_1$ and rejects every string not in $L_1$.

Hint: How can you use this to prove that $L$ is recursive?

If $L$ is a context-free language, then there exists a $p \in \mathbb{N}$ such that for every $s \in L$ with $|s| \geq p$ we have that we can write $s = uvwxy$ such that

1. $|vx| > 0$
2. $|vwx| \leq p$
3. For all $i \geq 0$ we have that $uv^iwx^iy \in L$

Hint: How can you use this to show that your $L$* is not context-free?

Hint: Consider $s = 0^{p+1}a^{p+1}b^p1^p$.