Is this language Recursively Enumerable or Not RE?

Question

$L = \{\langle M, k\rangle : M\;\text{is a Turing Machine and } |\{w \in L(M) : w \in a^*b^*\}| \geq k \}$

My Interpretation of language is that $L$ is a language which contains Turing machine whose language contains string greater than equal to $k$ and also strings belong to $a^* b ^*$.

My Analysis : Using Rice's Theorem,

$T_{yes} = L$ and $T_{no} = a^*b^*$

By rice's first theorem we can say that this language is Undecidable and by using rice's second theorem we can say this it is not even recognizable because $T_{yes} \subset T_{no}$.

My intuitive approach : As we know language $L$ is a set of TM which accept a set of strings length greater than or equal to k and are a subset of $a^* b^*$ then for language $L$ to be Recursively Enumerable there must be yes cases for turing machines which are fulfilling the requirement and for no cases it might halt and reject or might stay in loop but the issue here is there might exist a string in $a^*b^*$ which might get accepted later and there are infinite such strings so turing machine can never give yes cases. Yes cases can only happen if TM checks all strings of ab and rejects which are not a part of language but this will not happen as there are infinite strings.

This is not a proof but just my intuition.

Hence by using Rice's theorem we got to know that $L$ is not even Recursively Enumerable but I've been told that my interpretation of language itself is wrong and $L$ is Recursively Enumerable.

Answer 1

$L = \{\text{<M, k>| M is a Turing Machine and } |w \in L(M) : w \in a^*b^*| \geq k \}$

Now we want to find whether $L$ is $RE$ or not.

Yes, indeed your interpretation of language $L$ is wrong.

$L$ is a language of strings of form $\langle M, k \rangle$ where $M$ is turing machine which accepts atleast $k$ strings of form $a^*b^*$.

So, now it's easy to see that $L$ is indeed $RE$. For that we can run $M$ on all strings of form $a^*b^*$ by using dove tailing approach. If $\langle M, k \rangle \in L$ then eventually $M$ will accept $k$ strings of form $a^*b^*$. And at that point we will accept $\langle M, k \rangle$.

So as per your question answer is that $L$ is $RE$.

Answer 2

Use the power of nondeterminism: Guess $k$ strings of the form $a^* b^*$, check that $M$ accepts all of them. So your language is r.e.

The property "contains at least $k$ strings of the form $a^* b^*$" is certainly not trivial, so your language isn't decidable by Rice's theorem.