DFA and NFA Study Notes

Learning Objectives

• Identify the formal definition of deterministic accepters (DFAs).
• Understand another type of automaton that acts nondeterministically (NFAs).
• Identify the formal definition of nondeterministic accepters (NFAs).
• Identify the essential distinction between deterministic and nondeterministic automata.

What is a Finite Automaton?

• An abstract machine with a finite number of states.
• Accepts or rejects input strings.
• Processes input one symbol at a time.
• Comes in two types: DFA and NFA.

Deterministic Finite Accepters (DFA)

• A DFA is a 5-tuple $(Q, \Sigma, \delta, q_0, F)$
  • $Q$: Set of states
  • $\Sigma$: Input alphabet
  • $\delta$: Transition function $Q \times \Sigma \rightarrow Q$
  • $q0$: Initial state with $q</em>0 \in Q$
  • $F$: Set of accepting states with $F \subseteq Q$
• Key properties:
  • For every state and input symbol, there is exactly one next state (one path).
  • No ε-transitions.
• Example task: Design a DFA that accepts strings over $\Sigma = {0,1}$ that end with the substring "01".
  • Language: $L(M) = { w \in \Sigma^* \mid w \text{ ends with } "01" }$.
• Practical intuition: DFA processes input deterministically by following a single computation path for each input string.

Nondeterministic Finite Accepters (NFA)

• An NFA is a 5-tuple $(Q, \Sigma, \delta, q_0, F)$
  • $Q$, $\Sigma$, $q_0$, $F$ defined as in DFA
  • $\delta$: Transition function $Q \times \Sigma \rightarrow 2^Q$ (i.e., it can transition to a set of possible next states)
• Key properties:
  • Multiple possible next states for a given (state, input) pair.
  • ε-transitions (transitions on the empty string $\varepsilon$) are allowed.
• Example task: Design an NFA that accepts strings over $\Sigma = {0,1}$ that contain the substring "01".
  • Language: $L(M) = { w \in \Sigma^* \mid w \text{ has substring } "01" }$.
• Practical intuition: NFA can explore many possible computation paths in parallel (nondeterminism).

NFA vs DFA — Key Differences

• Determinism vs Non-determinism:
  • DFA: One path for each input (deterministic).
  • NFA: Multiple paths may be pursued in parallel ( nondeterministic).
• Transitions:
  • DFA: Exactly one next state for each pair $(q, a)$.
  • NFA: A set of possible next states, $\delta(q, a) \subseteq Q$.
• ε-transitions:
  • DFA: Not allowed.
  • NFA: Allowed.
• Implementation:
  • DFA: Easier to implement and reason about.
  • NFA: More flexible in design and often easier to construct for a given language.
• Expressiveness vs. power:
  • NFAs are more expressive in design but not in power compared to DFAs; both recognize the same class of languages (see equivalence below).
• Summary phrase from slides: NFAs are more flexible in construction but they accept the same set of languages as DFAs for the same alphabets.

Equivalence of DFA and NFA

• Theorem (subset construction): For any NFA, we can construct an equivalent DFA.
  • Idea: Use the subset construction to simulate all possible NFA states that could be reached at each step.
  • Formal intuition: DFA states correspond to subsets of $Q$ (i.e., elements of $2^Q$).
  • The DFA transition function $\delta_D$ is defined by collecting all possible NFA transitions from the subset:
  • • $\delta<em>D(T, a) = \bigcup</em>{q \in T} \delta(q, a) \quad \text{for } T \subseteq Q, a \in \Sigma$
• Formal equivalence statements:
  • A DFA is essentially an NFA with exactly one transition per input and no $\varepsilon$-transitions.
  • Both models recognize the same class of languages: the regular languages.
  • Therefore, for every NFA, there exists a DFA that recognizes the same language, and conversely.
• Consequence: DFAs and NFAs are equivalent in language recognition power, though they differ in construction and state behaviors.

State Reduction in DFA

• Goal: Minimize the number of states without changing the language accepted.
• Steps:
  1. Remove unreachable states (states that cannot be reached from the initial state on any input).
  2. Merge indistinguishable states (states that, for all inputs, lead to acceptance or rejection in the same way).
  3. Identify distinguishable vs indistinguishable pairs of states.
  4. Group and merge equivalent states to obtain a minimal DFA.
• Practical note: State minimization improves efficiency (smaller memory usage and faster processing).

Summary

• DFA: Deterministic transitions, no $\varepsilon$-transitions.
• NFA: Multiple transitions, allows $\varepsilon$-transitions.
• DFA and NFA are equal in expressive power for recognizing regular languages.
• State minimization reduces the number of states while preserving the language.

Practice and Homework

• Convert a given NFA to a DFA (via subset construction).
• Minimize a provided DFA.
• Design a DFA for specific patterns.
• Resources: Posted on Schoology.

Key Formal Definitions (for quick reference)

• DFA: $(Q, \Sigma, \delta, q<em>0, F)$ with $\delta: Q \times \Sigma \to Q$ and $q</em>0 \in Q$, $F \subseteq Q$.
• NFA: $(Q, \Sigma, \delta, q<em>0, F)$ with $\delta: Q \times \Sigma \to 2^Q$ and $q</em>0 \in Q$, $F \subseteq Q$, transitions may include $\varepsilon$-transitions.
• Subset construction (to convert NFA to DFA): If the NFA has states $Q$, the DFA states are subsets of $Q$, and for $T \subseteq Q$ and $a \in \Sigma$,
  $\delta<em>D(T, a) = \bigcup</em>{q \in T} \delta(q, a).$
• Language classes:
  • DFA accepts a language $L \subseteq \Sigma^*$ which is regular.
  • NFA accepts a language $L \subseteq \Sigma^*$ which is regular.