[Solved]: Can every state in a DFA be an accepting state?

Problem Detail: 

I know that we can have 0 accepting states in a DFA, it would just recognize the empty language. What about the case of all states being accepting? Would that mean it would recognize all of the strings in the DFA's particular alphabet?

Thanks

Asked By : Enis

Answered By : D.W.

Yes, every state can be accepting. Assuming the transition function is total (complete), so every state has a transition out on every possible letter in the alphabet, then yes, this would recognize all strings in the DFA's alphabet: the DFA would recognize $\Sigma^*$.

If the transition function is not complete -- in other words, if there is some state $q$ and some letter $a$ where there is no transition out of $q$ on letter $a$ -- then the DFA doesn't necessarily recognize all of $\Sigma^*$.

See In a DFA, does every state have a transition on every symbol of the alphabet? for more on that distinction. To avoid confusion, I generally recommend sticking to DFAs whose transition function is complete (total), at least until you understand the concepts well.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47554