Nondeterminism, epsilon closure and regular expressions
Goals and notation
Convert an ε-NFA to a DFA and connect finite automata to regular expressions. An NFA may have zero, one or several transitions for a symbol. An ε-transition consumes no input. A word is accepted if at least one finite path consumes the entire word and ends in a final state. Other failing or infinite ε-paths do not invalidate that witness. Nondeterminism is existential choice, not probability and not a requirement that all branches accept.
1. Subset construction with a worked ε-NFA
Let states be s,p,f; start s; final f. There is ε:s→p; p has a-loop and b→f; f has b-loop; all other transitions are empty. This recognizes a*b+. ε-closure(S) is every state reachable from S using zero or more ε-steps, so it includes S itself.
The DFA start subset is closure({s})={s,p}. From any subset T on symbol c, first take every c-transition from states in T, then take ε-closure of the result. A subset accepts if it intersects the NFA's final set. Our reachable subsets are {s,p}, {p}, {f}, and ∅. From {s,p} or {p}, a leads to {p}, b to {f}. From {f}, a leads to ∅, b to {f}. ∅ loops on both. Only {f} accepts. Thus aab is accepted, ba is rejected and ε is rejected.
For n NFA states there are at most 2^n subsets, including ∅, but many may be unreachable or equivalent. This is an upper bound, not a mandatory answer for every conversion. Correctness invariant: after reading w the DFA subset is exactly the set of NFA states reachable after consuming w, including possible ε-moves. The acceptance tests then coincide.
2. Regular expression semantics
Base expressions are ∅, ε and each alphabet symbol. Union R|S, concatenation RS and Kleene star R* represent union, language concatenation and zero-or-more repetitions. Precedence is star, then concatenation, then union unless parentheses override it. Here + on a language denotes one-or-more repetitions; it is not union. Thus a*b+ means zero or more a followed by at least one b.
Over {0,1}, (0|1)01 denotes exactly strings ending in 01. Expression 0|10 denotes {0} together with a 1 followed by any number of zeros; it does not mean (0|1)0. Algebra follows language semantics: R|R=R, Rε=R and R∅=∅. In general RS≠SR and (R|S)≠R|S. For R=a,S=b, ab belongs to the left starred union but neither a* nor b*.
3. Why expressions and automata agree
Build ε-NFAs inductively: union branches from a fresh start; concatenation connects final states of the first fragment to the second start; star permits zero repetitions and a return for another repetition. Combined with subset construction, every regular expression has a DFA.
In the other direction, label generalized automaton edges by expressions. When eliminating state k, update each remaining i→j label to R_ij | R_ik (R_kk)* R_kj, using old labels for the elimination step. A path either avoids k or reaches k, loops there zero or more times, then leaves. Add fresh start/final states as needed so neither is eliminated. This produces an expression for every finite automaton's language.
Worked local elimination: labels i→j=c, i→k=a, k→k=b, k→j=d produce c|ab*d. The new expression includes c and ad, not just strings that use the b-loop at least once.
Pitfalls
- Take ε-closure at the initial state and after every consumed symbol.
- One accepting branch suffices, but it must consume all input.
- Complementing an NFA by flipping finals is generally wrong; determinize first.
- ε is an expression for one empty word; ∅ denotes no words.
- Programming regex backreferences are beyond the classical regular-expression syntax used here.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. An NFA has one accepting and one rejecting full-input branch. Its result is:
A. Accept B. Reject C. Undefined D. Accept only if branches are equiprobable
Answer: A
A: Acceptance needs one witness.
B: Rejecting branches do not cancel acceptance.
C: The existential definition determines the result.
D: No probabilities are part of NFA semantics.
P02. The start subset in the worked ε-NFA is:
A. {s} B. {p} C. {s,p} D. {f}
Answer: C
A: This omits an ε-reachable state.
B: Closure includes the original state too.
C: s and p are reachable before consuming input.
D: f requires consuming b.
P03. For an n-state NFA, subset construction gives at most:
A. n states B. 2n states C. n! states D. 2^n states
Answer: D
A: Some NFAs need more than n DFA states.
B: This is not the general subset bound.
C: Subsets are not permutations.
D: Each state may be present or absent in a subset.
P04. Which string belongs to 0|10*?
A. 00 B. 101 C. 100 D. ε
Answer: C
A: The isolated alternative is only one 0.
B: After 1 only zeros may follow.
C: Choose 1 followed by two zeros.
D: Neither alternative produces ε.
P05. Eliminating k with labels c,a,b,d as taught gives:
A. cabd B. c|ab*d C. (c|a)bd D. ab+d
Answer: B
A: The alternatives are not concatenated.
B: Keep the direct path or take any number of k loops.
C: This forces b and d after the direct c path.
D: This loses c and incorrectly requires a b.
P06. Why can final-state flipping fail for an NFA?
A. NFAs read infinite input B. Existential acceptance does not become universal rejection C. NFAs cannot have final states D. Every NFA accepts ε
Answer: B
A: Inputs are finite strings here.
B: A word may have both final and nonfinal endpoints.
C: Final states are part of the NFA definition.
D: ε acceptance depends on reachable finals.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Theory of Computation syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in