Show that the following language is decidable by finding the algorithm for the finite automaton

Question

Given the language $K$ = $\{<M>: M$ is a finite automaton on the alphabet {0,1}) and $L(M)$ contains at least one word of the form $0^k1^l$ with $k,l\geq 0$}. In other words, describe an algorithm with the entry $M$ ( a finite automaton) and that decide after a finite number of steps if $M$ accept at least one word of the form described above.

So this is my attempt but i am really not sure if my algorithm is good.

we can see that the accepted words can be : 1, 0 , 001, 011, ..000001 , 011111.., 1111111.., 000000.., the empty word can't be in this i think since $l$ would be equal to $k$ (unless i am wrong)

This was my idea about what the finite automaton (it's not required but helpful for automaton) :

And my algorithm would look something like this:

Input : < M >

If q0 is a final state and if a loop of $0$ exists around q0 return true

Verify that in $M$ if from q0 we can read a 1 and follow a path that leads us to a final state that can have a loop of 1s, if it exists return true.

Else return false.

Thanks a lot for your help.

Answer 1

I think you've got it all wrong, you don't have to construct a finite automata but you are given an encoding of a finite automata you have to decide whether the given automata accept the string of type 0*1*. The algorithm should be something like this:

1. Convert the given FA to minimal Deterministic Finite Automata.
2. If minimal DFA contains n states, then generate all strings of language from 0*1* of length upto n.
3. Run the strings on a simulated DFA, if any one of the string is accepted the FA $\in$ L, else not.

The algorithm gives both yes and no answer given an encoding of an FA, so it is Turing decidable. The algorithm is correct as we know that if a string of length n of type 0*1* is not accepted on n-state DFA then and string of length > n will never be accepted from the pumping lemma of regular languages.