[Math] Decide whether DFA accepts all Strings

automata

Wikipedia :
Because DFAs can be reduced to a canonical form (minimal DFAs), there are also efficient algorithms to determine:

  • whether a DFA accepts any strings.
  • whether a DFA accepts all strings.
  • whether two DFAs recognize the same language.

I am not able prove how first two properties are decidable or by which algorithms we can determine same.

Best Answer

Do you know the algorithm for minimizing a DFA? That is what Wikipedia is discussing here.

After minimization, if the resulting DFA has only one state, it either accepts every string, if its one state is an accepting state, or accepts no strings, if its one state is non-accepting.

Related Question