Extended transition function and regular languages

1. What does “deterministic” mean for δ?
   Stuck? Peek at 1.1.1 States and the DFA

   • DFA = (Q, Σ, δ, q₀, F), δ : Q × Σ → Q total. One step per symbol; always halts.
   • Accept iff the last state ∈ F. ε accepted ⇔ q₀ ∈ F.
   • Dead state: non-accepting, all self-loops. GATE counts it in minimal-DFA questions.
   • Exactly one string of length k: k + 2 states. #DFAs (n states, m symbols, fixed start) = nⁿᵐ · 2ⁿ.

   Read lesson 1.1.1

2. When are there infinitely many paths from u to v in a graph?
   Stuck? Peek at 0.2.5 Directed graphs

   • Directed graph (V, E ⊆ V×V); self-loop; in/out-degree; labelled edges spell words along paths.
   • Path length = #edges. Cycle = path returning to start. Self-loop = cycle of length 1.
   • Reachable set: grow from u until nothing new (BFS). Shortest path in n-node graph ≤ n−1 edges.
   • Infinitely many u→v paths ⇔ some cycle lies on a u→v route.

   Read lesson 0.2.5

3. What is Σ⁰?
   Stuck? Peek at 0.3.2 Σᵏ, Σ*, Σ⁺ and languages

   • |Σᵏ| = |Σ|ᵏ; Σ⁰ = {ε}; Σ* = ⋃ Σᵏ (k ≥ 0); Σ⁺ = Σ* − {ε}.
   • #strings of length ≤ n over k symbols = (kⁿ⁺¹ − 1)/(k − 1); binary: 2ⁿ⁺¹ − 1.
   • Language = any subset of Σ*. ∅ (no strings) ≠ {ε} (one string). Exactly r of one symbol in length n (binary): C(n, r).
   • Shortlex order lists every string at a finite position.

   Read lesson 0.3.2

δ tells you one step. But you never ask a DFA about one symbol — you hand it a whole string, like a file to scan. We need a single function that answers “starting here, after reading this whole string, where am I?”, and then a precise name for the set of strings a DFA accepts. That name — regular language — is the first of the great language families in this subject.

For the “ends with 01” DFA below, without tracing step by step: what state will it be in after reading 110101? (Hint: what does each state “mean”?)

Prediction check

Answer: q2. Each state has a meaning: q0 = “last symbol was 1 and not part of …01, or nothing read”, q1 = “last symbol was 0”, q2 = “last two symbols were 01”. 110101 ends in 01, so it is in q2. Thinking in meanings instead of tracing is the fastest way to work with DFAs.

The extended transition function δ̂

δ̂(q, w) is simply “the state reached from q by following the path that spells w”. A key property: δ̂(q, xy) = δ̂(δ̂(q, x), y).

Acceptance and the language of a DFA

“M accepts the language L” means L(M) = L exactly (Lesson 0.3.4: yes on all of L, no on everything else).

Regular languages

This is the definition used throughout. Every finite language is regular (build a branching DFA with one path per string). The even-a’s language, “ends with 01”, “divisible by 3” are regular. Whether something like {aⁿbⁿ} is regular is a real question — answered in Phase 2.

Proving a DFA correct: the invariant method

Give each state a meaning (an invariant), then prove by induction on |w| that δ̂(q₀, w) = q exactly when w has q’s meaning. Base: ε lands in q₀ and has q₀’s meaning. Step: one more symbol moves to the state whose meaning now holds. Finally check that F is exactly the states whose meanings mean “in L”.

Reading a DFA’s language from its graph

• L(M) = ∅ iff no accepting state is reachable from q₀.
• L(M) = Σ* iff every state reachable from q₀ is accepting.
• L(M) is infinite iff some cycle lies on a path from q₀ to an accepting state (Lesson 0.2.5).
• Strings of length n accepted: count paths of length n from q₀ into F (a small table, row by row).

Putting it together

• δ̂(q, ε) = q and δ̂(q, wa) = δ(δ̂(q, w), a): the walk for a whole string.
• L(M) = { w : δ̂(q₀, w) ∈ F }; a language is regular iff some DFA accepts it.
• Emptiness, everything, infiniteness and counting are graph questions about the diagram.

δ̂ unrolled on w = 1101 (ends-with-01 DFA)
δ̂(q0, ε)    = q0
δ̂(q0, 1)    = δ(q0,1) = q0
δ̂(q0, 11)   = δ(q0,1) = q0
δ̂(q0, 110)  = δ(q0,0) = q1
δ̂(q0, 1101) = δ(q1,1) = q2  ∈ F   → ACCEPT

rejected: w = 011 → q0 ─0→ q1 ─1→ q2 ─1→ q0 ∉ F → REJECT

state meanings (invariants)
 q0 : w = ε, or w ends in 1 but not in 01  (i.e. ends in 11)
 q1 : w ends in 0
 q2 : w ends in 01                          F = {q2}

We can now say precisely what a DFA accepts. Next: a toolbox of design patterns — starts-with, ends-with, contains, counting mod n, divisibility — that covers most GATE DFA questions, with formulas for the number of states.

1. MCQ

   δ̂(q, ε) equals:

   1. q₀
   2. q
   3. the dead state
   4. undefined
2. MSQ

   Which are regular languages over {a,b}?

   1. ∅
   2. {ε}
   3. {a, ab, abb}
   4. Σ*
3. NAT

   The contains-aa DFA from the GATE example: how many strings of length 3 does it accept?

   Write your answer before opening the key.

4. MCQ

   L(M) is infinite iff:

   1. M has a cycle
   2. M has a self-loop
   3. a cycle lies on some path from q₀ to an accepting state
   4. M has more than one accepting state
5. MCQ

   For any DFA, δ̂(q, xy) equals:

   1. δ̂(q, x) · δ̂(q, y)
   2. δ̂(δ̂(q, x), y)
   3. δ̂(δ̂(q, y), x)
   4. δ(q, xy)

• extended transition function δ̂
• M accepts w
• language of a DFA L(M)
• regular language
• state invariant (meaning of a state)
• counting accepted strings by paths

1. Definition of δ̂?
   Reveal answer

   δ̂(q, ε) = q; δ̂(q, wa) = δ(δ̂(q, w), a).
2. Definition of a regular language?
   Reveal answer

   A language accepted by some DFA.
3. Is every finite language regular?
   Reveal answer

   Yes.
4. When is L(M) infinite (graph view)?
   Reveal answer

   When some cycle lies on a path from q₀ to an accepting state.