Nondeterminism and the NFA

1. Product DFA for L₁ ∩ L₂: accepting set?
   Stuck? Peek at 1.1.4 Product construction and complement

   • Product: states Q₁×Q₂, δ((p,q),a) = (δ₁(p,a), δ₂(q,a)), start (s₁,s₂).
   • ∩: F₁×F₂. ∪: F₁×Q₂ ∪ Q₁×F₂. −: F₁×(Q₂−F₂). ≤ |Q₁|·|Q₂| states.
   • Complement: complete the DFA (add dead state), swap F ↔ Q−F; same state count.
   • Regular languages closed under ∪, ∩, −, complement.

   Read lesson 1.1.4

2. Minimal DFA for strings ending with ab?
   Stuck? Peek at 1.1.3 DFA design patterns

   Language (|w| = k pattern)	Minimal states
   starts with w	k + 2
   contains w / ends with w	k + 1
   |x| ≡ r mod n	n
   |x| = k, |x| ≤ k	k + 2
   |x| ≥ k	k + 1
   #a mod m and/or #b mod n	m·n (typical)
   binary value ≡ 0 mod k, k odd	k
   binary ÷ 2ʲ	j + 1
   k-th symbol from start fixed	k + 2

   Divisibility update: r ← (base·r + digit) mod k.

   Read lesson 1.1.3

3. What does |P(Q)| equal when |Q| = n?
   Stuck? Peek at 0.2.1 Sets

   • x ∈ A (element) vs X ⊆ A (subset). ∅ ⊆ every set. A = B ⇔ A ⊆ B and B ⊆ A.
   • A ∪ B, A ∩ B, A − B = A ∩ B̅, A̅ = U − A. De Morgan: (A∪B)̅ = A̅∩B̅, (A∩B)̅ = A̅∪B̅.
   • |A ∪ B| = |A| + |B| − |A ∩ B|. |A × B| = |A|·|B|. |P(A)| = 2^|A|.
   • |∅| = 0, |{∅}| = 1, P(∅) = {∅}.

   Read lesson 0.2.1

You’re looking for a friend in a maze of corridors. A DFA must commit to one corridor at every junction. But imagine you could split into copies at every junction, each copy exploring one corridor at once; if any copy finds your friend, you succeed. That’s nondeterminism. No real machine clones itself — but as a design tool it is spectacular: some languages that need huge DFAs have tiny machines of this kind.

For “strings over {0,1} whose 3rd symbol from the end is 1”, a guessing machine needs only 4 states (below). How many states do you think the smallest DFA for the same language needs?

Prediction check

Answer: 8 = 2³. The DFA must remember the last 3 symbols — every one of the 8 combinations behaves differently. The guessing machine just “guesses” which 1 is third from the end and verifies that exactly two symbols follow. Chapter 1.2.3 shows where the 2ⁿ comes from.

What changes from a DFA

In a Nondeterministic Finite Automaton (NFA), from a state on a symbol there may be zero, one, or several next states. Zero moves = that copy dies quietly. Several = the machine splits.

How an NFA accepts

Two equivalent ways to picture it:

• Guessing: the machine magically guesses the right choice at every split.
• Parallel copies (set of states): track the set of all states some copy could be in. Start {q₀}; on symbol a, the new set is the union of δ(q, a) over all q in the current set. Accept iff the final set contains an accepting state.

Extended δ̂ for NFAs

δ̂(q, ε) = {q}; δ̂(q, wa) = ⋃ over p ∈ δ̂(q, w) of δ(p, a). L(N) = { w | δ̂(q₀, w) ∩ F ≠ ∅ }.

Every DFA is an NFA

A DFA is just an NFA where every δ(q, a) has exactly one element. So NFAs can do at least what DFAs do. The surprising theorem (Lesson 1.2.3) is the converse: every NFA can be converted to an equivalent DFA. NFAs accept exactly the regular languages — they are convenient, not stronger.

Why missing moves are fine

An NFA does not need a dead state: a missing move simply kills that copy. So NFA state counts are often smaller, and “minimal NFA” is a different (and much harder) question than “minimal DFA”.

Putting it together

• An NFA may have 0, 1 or many moves; it accepts if any path ends in F.
• Track the set of active states — that is the bridge to DFAs.
• NFAs are more convenient, not more powerful; swapping F does not complement them.

set-of-states trace for "aab" on the ends-with-ab NFA
start      {q0}
read a  →  {q0, q1}        (q0 stays, q0 also guesses "this a starts the final ab")
read a  →  {q0, q1}        (q1 has no move on a: that copy dies; q0 splits again)
read b  →  {q0, q2}        (q0 stays; q1 ─b→ q2)
end: q2 ∈ F → ACCEPT

"aba": {q0} ─a→ {q0,q1} ─b→ {q0,q2} ─a→ {q0,q1}   no final state → REJECT

An NFA reads one symbol per move. What if a machine could also jump between states without reading anything? That small extra freedom makes gluing machines together trivial — next lesson.

1. MCQ

   For an NFA, δ maps Q × Σ to:

   1. Q
   2. P(Q)
   3. Σ
   4. Q × Q
2. MSQ

   Which are true?

   1. Every DFA is an NFA
   2. Some NFA accepts a non-regular language
   3. NFA accepts w if some path ends in F
   4. An NFA must have a dead state
3. NAT

   The 3rd-from-end NFA: how many states are in the active set after reading “111”?

   Write your answer before opening the key.

4. MCQ

   The ends-with-ab NFA with F swapped (F = {q0, q1}) accepts:

   1. strings not ending in ab
   2. Σ* (every string, including ab)
   3. only ε
   4. ∅

• nondeterminism
• NFA, δ : Q × Σ → P(Q)
• computation path / branch
• NFA acceptance (some path)
• active set of states
• δ̂ for NFAs

1. When does an NFA accept w?
   Reveal answer

   When at least one path spelling w ends in an accepting state.
2. Are NFAs more powerful than DFAs?
   Reveal answer

   No — they accept exactly the regular languages.
3. Does swapping F complement an NFA?
   Reveal answer

   No.
4. States of a smallest NFA for “k-th symbol from the end is 1”?
   Reveal answer

   k + 1.