Showing the a language that does not accept an empty string is decidable

by Fox   Last Updated March 13, 2018 07:20 AM

I'm supposed to show that the following language is decidable:

{$\lt$A$\gt$ | A is a DFA and L(A) is not empty}

What I have

T = "On input $\lt$A$\gt$ where A is a DFA:

  1. Mark the start state of A
  2. Repeat until no new states gets marked

    Mark any state that has a transition coming into it from any state that is already marked. 
  3. If an accept state is marked, accept. Otherwise reject.

Does this suffice to show that the language is decidable and did I make any mistakes?

Related Questions

How to prove Kleene star to be uncounably infinite?

Updated April 06, 2017 13:20 PM

Complement of a grammar Σ and Language L equal to L

Updated September 26, 2017 07:20 AM