Asked By : Duncan
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/12587
Answered By : Wandering Logic
- a finite set of states ($Q$)
- a finite set of input symbols called the alphabet ($Sigma$)
- a transition function ($delta : Q times Sigma rightarrow Q$)
- a start state ($q_0 in Q)$
- a set of accept states ($F subseteq Q$).
Let $w = a_1 a_2 cdots a_n$ be a string over the alphabet $Sigma$. The automaton $M$ accepts the string $w$ if a sequence of states, $r_0, r_1, ldots, r_n$, exists in $Q$ with the following conditions:
- $r_0 = q_0$
- $r_{i+1} = delta(r_i, a_{i+1})$, for $i = 0, ldots, n−1$
- $r_n in F$.
The ambiguity, and the controversy is over the defintion of the transition function, $delta$ (number “3” in the first bulleted list.) We all agree that what differentiates a DFA from an NFA is that $delta$ is a function rather than a relation. But is $delta$ a partial function or a total function? The definition of the DFA works just fine if $delta$ is a partial function. Given an input string, if you reach a state $q_i$ with an input symbol $a_j$ where there is no next state then the automata simply does not accept. Moreover when you extend this definition to create the definition of push-down automata it will be the case that you must make the distinction that push-down automata with transition functions that are partial functions are classified as deterministic, not nondeterministic. If the partial function bothers you then here is a trivial transformation that makes $delta$ a total function. (This transformation is not like the subset construction algorithm, it adds at most O(1) states, is linear in the original number of states, and can be extended to work with PDAs. None of those facts is true of the subset construction algorithm.)
- add a state $q_{mathrm{error}}$
- for every pair $(q_i, s_j)$ where $delta$ is undefined, define $delta(q_i, s_j) = q_{mathrm{error}}$.
This automata has a $delta$ that is a total function and accepts and rejects exactly the same set of states that your original automata accepted and rejected.