HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Can every state in a DFA be an accepting state?

Submitted by: @import:stackexchange-cs··
0
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

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.

Context

StackExchange Computer Science Q#47554, answer score: 3

Revisions (0)

No revisions yet.