patternMinor
Can every state in a DFA be an accepting state?
Viewed 0 times
dfacaneveryacceptingstate
Problem
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
Thanks
Solution
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.
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.
Context
StackExchange Computer Science Q#47554, answer score: 3
Revisions (0)
No revisions yet.