NFA_vs_DFA_flashcards
Are NFAs more powerful than DFAs?
No. Every NFA can be converted into an equivalent DFA.
What does it mean for an NFA and DFA to be equivalent?
They accept the same language — i.e., for every NFA, there exists a DFA that accepts the same set of words.
What class of languages do NFAs accept?
NFAs accept exactly the regular languages — same as DFAs.
What is the Subset Construction (a.k.a. Powerset Construction)?
An algorithm to convert an NFA into an equivalent DFA by creating DFA states as sets of NFA states.
What is the goal of the subset construction algorithm?
To convert NFA A = (Q, Σ, Δ, s, F) into a DFA A′ = (Q′, Σ, δ, s′, F′) that accepts the same language.
In subset construction, what does E(q) represent?
The ε-closure of state q — all states reachable from q via ε-transitions.
What is Q′ in the DFA produced by subset construction?
Q′ is the powerset of Q — all subsets of NFA states.
What is the start state s′ of the DFA in subset construction?
The ε-closure of the NFA start state: s′ = E(s).
How is the DFA transition function δ defined in subset construction?
For state R and symbol a, δ(R, a) = union of ε-closures of all states reachable from any q ∈ R via a.
What is the set of accepting states F′ in the DFA?
All DFA states R such that R ∩ F ≠ ∅ — they contain at least one NFA accepting state.
How do DFA states relate to NFA states in subset construction?
Each DFA state represents a set of NFA states the machine could be in after reading input.
Why are NFAs considered human-friendly?
Because they are simpler to design and understand for representing languages, especially with nondeterminism.
Why are DFAs considered computer-friendly?
Because they are deterministic, faster to execute, and more suitable for implementation.
What is the first step in converting an NFA to a DFA?
Determine the language the NFA represents, so you can validate the DFA’s correctness.
How do you determine the initial state of the DFA from an NFA?
Compute the ε-closure of the NFA’s start state — this becomes the DFA’s start state.
What should you remember when handling ε-transitions during conversion?
Use ε-closure to capture all jump states that are reachable without consuming input.
How do you handle NFA transitions with multiple possible outcomes in DFA construction?
Create DFA states that represent sets of those NFA outcomes, and draw transitions accordingly.
