patternMinor
In a DFA, does the restriction for a total transition function apply to accepting states?
Viewed 0 times
totaldfatheapplystatesrestrictionfunctionacceptingfordoes
Problem
I recently discovered the idea of a total transition function in Automata Theory. To my understanding this means that every state has at least one outgoing state.
My question is whether this restriction applies to accepting states, since my initial intuition tells me that this would be an overly strict enforcement of the state machine.
Thanks in advance for any answers.
My question is whether this restriction applies to accepting states, since my initial intuition tells me that this would be an overly strict enforcement of the state machine.
Thanks in advance for any answers.
Solution
Unfortunately there seem to be several different definitions of DFAs in the literature. Here is the classical definition:
A DFA is a quintuple $\langle \Sigma,Q,q_0,F,\delta \rangle$, where $\Sigma,Q$ are non-empty finite sets, $q_0 \in Q$, $F \subseteq Q$, and $\delta \colon Q \times \Sigma \to Q$.
We extend $\delta$ to a function $\hat\delta \colon Q \times \Sigma^* \to Q$ using the recurrence $\hat\delta(q,w\sigma) = \delta(\hat\delta(q,w),\sigma)$, with base case $\hat\delta(q,\epsilon)=q$.
The language accepted by the DFA is $\{ w \in \Sigma^* : \hat\delta(q_0,w) \in F \}$.
Other definitions are possible. For example, you might allow $\delta$ to be a partial function. However, the definition I stated has a significant advantage: the Myhill–Nerode theorem holds for it.
Under my definition, from each state there is exactly one transition for each alphabet symbol. Other definitions could be different. Only you know which definition you use.
It is important to stress that this "strict" definition doesn't restrict the power of DFAs one bit. It is known that DFAs accept the very same languages as NFAs, for example, though there could be a dramatic difference in state complexity (the number of states needed to accept a given language).
A DFA is a quintuple $\langle \Sigma,Q,q_0,F,\delta \rangle$, where $\Sigma,Q$ are non-empty finite sets, $q_0 \in Q$, $F \subseteq Q$, and $\delta \colon Q \times \Sigma \to Q$.
We extend $\delta$ to a function $\hat\delta \colon Q \times \Sigma^* \to Q$ using the recurrence $\hat\delta(q,w\sigma) = \delta(\hat\delta(q,w),\sigma)$, with base case $\hat\delta(q,\epsilon)=q$.
The language accepted by the DFA is $\{ w \in \Sigma^* : \hat\delta(q_0,w) \in F \}$.
Other definitions are possible. For example, you might allow $\delta$ to be a partial function. However, the definition I stated has a significant advantage: the Myhill–Nerode theorem holds for it.
Under my definition, from each state there is exactly one transition for each alphabet symbol. Other definitions could be different. Only you know which definition you use.
It is important to stress that this "strict" definition doesn't restrict the power of DFAs one bit. It is known that DFAs accept the very same languages as NFAs, for example, though there could be a dramatic difference in state complexity (the number of states needed to accept a given language).
Context
StackExchange Computer Science Q#70698, answer score: 4
Revisions (0)
No revisions yet.