Product construction and complement

1. Minimal DFA states for strings containing 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

2. Write A − B using ∩ and complement.
   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

3. What is L(M) when no accepting state is reachable?
   Stuck? Peek at 1.1.2 Extended transition function and regular languages

   • δ̂(q, ε) = q; δ̂(q, wa) = δ(δ̂(q, w), a); δ̂(q, xy) = δ̂(δ̂(q, x), y).
   • L(M) = { w : δ̂(q₀, w) ∈ F }. Regular ⇔ accepted by some DFA. All finite languages are regular.
   • From the graph: empty ⇔ no reachable final; Σ* ⇔ all reachable states final; infinite ⇔ cycle on a path start→final.
   • Prove correctness with state meanings + induction on |w|.

   Read lesson 1.1.2

An airport scanner checks a bag for two things at once: “no liquids over 100 ml” and “no sharp objects”. It doesn’t scan twice — it runs both checks in parallel as the bag passes. A DFA can do the same: run two DFAs side by side on one pass, remembering a pair of states. This proves that combinations of regular languages are regular, and it’s how GATE expects you to count states for combined conditions.

DFA A has 3 states, DFA B has 4 states. A DFA that runs both at once would need at most how many states?

Prediction check

At most 3 × 4 = 12: one state per pair (state of A, state of B). Some pairs may be unreachable or merge after minimization, so 12 is an upper bound.

The product construction

After reading w, the product is in (δ̂₁(s₁, w), δ̂₂(s₂, w)) — it knows exactly where both machines are. Only the choice of accepting pairs changes:

• Intersection L₁ ∩ L₂: F = F₁ × F₂ (both accept).
• Union L₁ ∪ L₂: F = (F₁ × Q₂) ∪ (Q₁ × F₂) (either accepts).
• Difference L₁ − L₂: F = F₁ × (Q₂ − F₂).
• Symmetric difference: exactly one accepts.

Conclusion: regular languages are closed under union, intersection and difference — combining regular languages this way always gives a regular language.

Build only what you can reach

In practice, start from (s₁, s₂) and add pairs as transitions reach them (like BFS, Lesson 0.2.5). Unreachable pairs never matter.

Complement of a DFA

It works because a DFA run always ends in exactly one state, and that state is accepting in exactly one of M, M̅. So regular languages are closed under complement, and the number of states doesn’t change.

Using complement to save work

“Strings that do not contain aba”: build contains-aba (4 states), swap F. Same 4 states. Complementing never changes the minimal state count.

Putting it together

• Run two DFAs in parallel on pairs of states; only the accepting set decides ∩, ∪ or −.
• At most m × n states; build reachable pairs only.
• Complement = complete the DFA, then swap F. Regular languages are closed under ∪, ∩, −, complement.

Product of “#a even” (E/O) with “ends with b” (P = last symbol not b or nothing read, Q = last symbol b). Intersection accepts only EQ.

          a      b          union F      = {EP, EQ, OQ}   (E accepts or Q accepts)
→ EP      OP     EQ         intersection = {EQ}
* EQ      OP     EQ         difference L₁−L₂ = {EP}   (even a's, not ending in b)
  OP      EP     OQ
  OQ      EP     OQ
trace "abab": EP ─a→ OP ─b→ OQ ─a→ EP ─b→ EQ   ACCEPT (2 a's, ends b)
trace "ab"  : EP ─a→ OP ─b→ OQ                 REJECT (odd a's)

Phase 1, Chapter 1 complete: DFAs, their languages, design patterns, combining and complementing. But designing some DFAs is painful (try “third symbol from the end is 1”). Next chapter introduces a machine allowed to guess — and shows it is no more powerful, just far more convenient.

1. NAT

   Product construction of a 4-state and a 5-state DFA has at most how many states?

   Write your answer before opening the key.

2. MCQ

   In the product DFA, for L₁ − L₂ the accepting set is:

   1. F₁ × F₂
   2. F₁ × (Q₂ − F₂)
   3. (Q₁ − F₁) × F₂
   4. (F₁ × Q₂) ∪ (Q₁ × F₂)
3. MSQ

   Which are true?

   1. Regular languages are closed under complement
   2. Swapping F in any DFA drawing (dead state omitted) gives the complement
   3. Complementing a DFA does not change its number of states
   4. Regular languages are closed under intersection
4. NAT

   Minimal DFA states for strings over {a,b} that do NOT contain aa?

   Write your answer before opening the key.

5. MCQ

   L₁ = strings of even length, L₂ = strings of odd length over {a,b}. Product DFA for L₁ ∩ L₂ — its language is:

   1. Σ*
   2. ∅
   3. {ε}
   4. even-length strings

• product construction
• pair state (p, q)
• closure (an operation keeps the family)
• closed under union, intersection, difference, complement
• complement DFA (swap F)
• complete DFA

1. Product DFA accepting set for L₁ ∪ L₂?
   Reveal answer

   (F₁ × Q₂) ∪ (Q₁ × F₂)
2. Product DFA accepting set for L₁ ∩ L₂?
   Reveal answer

   F₁ × F₂
3. How do you complement a DFA?
   Reveal answer

   Make it complete (add dead state), then swap accepting and non-accepting states.
4. Does complementing change the minimal state count?
   Reveal answer

   No.