Showing a language is decidable

Question

I am trying to show that the language

{ (B,w) | B is a DFA that accepts at least one string w}

is decidable.

I have:

M = "On input (B,w) where B is a DFA and w is a string:

1. Simulate B on input w

2. Repeat until an accept state is marked.

   If any w reaches ends in an accept state mark it.
   

3. If an accept state is marked, accept; otherwise reject.

I'm not sure this is right, because what if it keeps checking and in reality the DFA accepts no strings, then 2. will be infinite right? Am I anywhere near the right answer?

Answer 1

Your answer will work more or less. A few remarks:

1. It is not completely trivial how to run through all strings in some order without repetiton. Repetition might lead to infinite computations although the DFA accepts some string.
2. The "otherwise" in your point 3. will never be reached.
3. "if it keeps checking and in reality the DFA accepts no strings" is just fine: an infinite computation is a rejecting one, and a DFA that accepts no strings should be rejected.

Another way to solve this would be to analyze the DFA. If there exists any path from the start state to an accepting state, then the DFA accepts at least one string. This will in general be more efficient, because you have an upper bound in the order of the number of states. In your case the upper bound would depend on when the first accepted string is encountered and then on the total length of all strings up to that point.