DFA vs NFA
DFA (deterministic finite automaton)
Definition: A deterministic finite automaton is a 5-tuple (Q, \Sigma, \delta, q_0, F) where
- Q is a finite set of states,
- \Sigma is a finite alphabet,
- \delta: Q \times \Sigma \rightarrow Q is the transition function,
- q_0 \in Q is the start state, and
- F \subseteq Q is the set of accept states.
Features / behavior:
- Every state has exactly one transition out for each symbol in the alphabet
- No other transitions permitted
- Executes step by step on a single machine
Computation: Let M = (Q, \Sigma, \delta, q_0, F) and let w = w_1w_2 \dots w_n where each w_i \in \Sigma, then M accepts w if a sequence of states r_0, r_1, \dots, r_n exists in Q with three conditions:
- r_0 = q_0
- \delta(r_i, w_{i+1}) = r_{i+1}, for i = 0, \dots, n - 1, and
- r_n \in F
NFA (nondeterministic finite automaton)
Definition: A nondeterministic finite automaton is a 5-tuple (Q, \Sigma, \delta, q_0, F) where
- Q is a finite set of states,
- \Sigma is a finite alphabet,
- \delta: Q \times \Sigma_\epsilon \rightarrow \mathcal{P}(Q) is the transition function,
- q_0 \in Q is the start state, and
- F \subseteq Q is the set of accept states.
Features / behavior:
- Each state may have 0, 1 or more transitions out for each symbol in the alphabet
- Permits transitions on empty string: \epsilon transitions (notice the domain of \delta is Q \times \Sigma_\epsilon)
- Splits into multiple copies of itself and performs computations in parallel
Computation: Let N = (Q, \Sigma, \delta, q_0, F) and let w = y_1y_2 \dots y_m where each y_i \in \Sigma_{epsilon}, then N accepts w if a sequence of states r_0, r_1, \dots, r_n exists in Q with three conditions:
- r_0 = q_0
- r_{i+1} \in \delta(r_i, y_{i+1}), for i = 0, \dots, m - 1, and
- r_m \in F
Copyright 漏 2023 Clayton Cafiero