patternMinor
Does a DFA accept an empty string if $q_0$ is the accept state?
Viewed 0 times
dfatheacceptemptyq_0statedoesstring
Problem
Suppose $q_0$ is the start state, does this mean that if it's the accept state, then the machine must accept the empty string since it cannot have a transition with the empty string?
Solution
Yes. This is immediate from the definitions.
A DFA accepts if it's in an accepting state after it's read its input. If the input is the empty string, the DFA makes no transitions so, after reading it's input, it's still in its initial state, $q_0$. If $q_0$ is an accepting state, the automaton accepts the empty string.
Note that you write "the accepting state" but an automaton may have multiple accepting states.
A DFA accepts if it's in an accepting state after it's read its input. If the input is the empty string, the DFA makes no transitions so, after reading it's input, it's still in its initial state, $q_0$. If $q_0$ is an accepting state, the automaton accepts the empty string.
Note that you write "the accepting state" but an automaton may have multiple accepting states.
Context
StackExchange Computer Science Q#51986, answer score: 9
Revisions (0)
No revisions yet.