Finite Automata

Finite automata are the simplest model of computation — a machine with a fixed, bounded amount of memory — and they sit at the heart of every grep search, every lexical analyser (like lex or flex), and every regular-expression engine. Understanding them fully, including where they fail, is the cornerstone of GATE CS Theory of Computation.

Definition: A Deterministic Finite Automaton (DFA) is a 5-tuple (Q, Σ, δ, q₀, F): a finite set of states Q; an input alphabet Σ; a transition function δ: Q × Σ → Q mapping every (state, symbol) pair to exactly one next state; a unique start state q₀ ∈ Q; and a set of accept (final) states F ⊆ Q. The DFA accepts a string w if, after processing every symbol from q₀, it ends in a state belonging to F.

DFA in detail

The word "deterministic" means: at every moment, given the current state and the next input symbol, there is no choice — exactly one next state exists. The DFA never backtracks; it reads the input exactly once, left to right, in O(|w|) time.

A DFA rejects a string if it ends in a non-accept state, or (informally, with a stuck state / dead state) if a transition is undefined for some symbol (though a total DFA always has a transition to a dead/trap state for undefined pairs).

Worked example — DFA for binary numbers divisible by 3:

States represent remainders modulo 3: q₀ (remainder 0, also the start and sole accept state), q₁ (remainder 1), q₂ (remainder 2).

Transitions: reading a bit b from state qᵣ, the new remainder is (2r + b) mod 3.

• From q₀: on 0 → q₀; on 1 → q₁.
• From q₁: on 0 → q₂; on 1 → q₀.
• From q₂: on 0 → q₁; on 1 → q₂.

This 3-state DFA (minimal) accepts exactly the binary strings whose integer value is divisible by 3 — including the empty string (value 0). This is a classic GATE question: the answer is 3 states.

NFA — non-deterministic finite automaton

Definition: An NFA relaxes δ to δ: Q × (Σ ∪ {ε}) → 2^Q. From a given state and symbol, there may be zero, one or several possible next states. ε-transitions allow state changes without consuming any input symbol.

The NFA accepts a string if there exists at least one computation path that ends in an accept state. The NFA does not "choose wisely" — it explores all paths simultaneously (or, equivalently, it is always lucky with its choices).

Why NFAs are useful: they can be built directly from a regular expression by Thompson's construction, with one state per symbol and operator — a clean, mechanical translation. The resulting NFA may have many ε-transitions but is compact and regular-expression-faithful.

The equivalence theorem and subset construction

Key theorem: Every NFA has an equivalent DFA that accepts exactly the same language.

Subset construction: Build the DFA whose states are subsets of the NFA's state set. The start state of the DFA is the ε-closure of the NFA's start state. Each DFA state S on symbol a transitions to ε-closure(⋃_{q∈S} δ_NFA(q, a)).

Cost: the DFA may need up to 2^|Q| states — exponential in the NFA's state count. This worst case is achievable (there are known NFA families that require 2^n states in any equivalent DFA), but in practice most NFAs blow up far less dramatically.

Implication: non-determinism buys convenience and compactness, never extra computational power. NFAs and DFAs recognise exactly the same class of languages — the regular languages.

ε-NFA and regular expressions

An ε-NFA is an NFA that explicitly allows ε-transitions. The ε-closure of a state q is the set of all states reachable from q by zero or more ε-transitions (including q itself).

Regular expression → ε-NFA → DFA (the standard pipeline):

1. Parse the regex into an abstract syntax tree.
2. Thompson's construction: build an ε-NFA fragment for each atom (single character), then combine fragments using rules for concatenation, union (|) and Kleene star (*). The result is an ε-NFA with O(m) states where m = length of the regex.
3. Subset construction: convert to a DFA.
4. Minimisation (Hopcroft's algorithm, O(n log n)): merge equivalent states into a single minimal DFA.

This pipeline is exactly how grep, lex/flex and most pattern-matching engines work.

Regular languages — definition and closure

A language L is regular if and only if some DFA (equivalently, some NFA, ε-NFA, or regular expression) recognises it. The class of regular languages is denoted REG or sometimes L in GATE notation.

Closure properties: Regular languages are closed under all of the following:

• Union: L₁ ∪ L₂
• Intersection: L₁ ∩ L₂
• Complement: L̄
• Difference: L₁ \ L₂
• Concatenation: L₁L₂
• Kleene star: L*
• Reverse: L^R
• Homomorphism and inverse homomorphism

Combine any regular languages with these operations and the result is still regular. This is useful for proving a language is regular by constructing it from known regular pieces.

Decidable problems for DFAs

All standard questions about DFAs are decidable (algorithms exist and terminate):

The Pumping Lemma for regular languages

The Pumping Lemma is a proof tool for non-regularity. It is NOT used to prove a language IS regular — it is used to prove it is NOT.

Statement: If L is regular, then there exists a pumping length p ≥ 1 such that for every string s ∈ L with |s| ≥ p, there exists a decomposition s = xyz satisfying:

1. |xy| ≤ p
2. |y| ≥ 1
3. xy^i z ∈ L for all i ≥ 0

Intuition: A DFA with p states must repeat some state when processing any string of length ≥ p. The portion of input corresponding to the repeated state is y — a loop that can be pumped (repeated any number of times, including zero) while keeping the string in L.

To prove a language is NOT regular using the Pumping Lemma, use proof by contradiction:
Assume L is regular with pumping length p.
Choose a string s ∈ L with |s| ≥ p carefully — the choice of s is yours to optimise.
Show that for every possible split xyz (satisfying conditions 1 and 2), there exists some i where xy^i z ∉ L.
Conclude that L is not regular.

Worked example — proving { aⁿbⁿ } is not regular

Question: Show that L = { aⁿbⁿ | n ≥ 0 } is not regular.

Solution:
Step 1: Assume L is regular with pumping length p. Choose s = aᵖbᵖ. Then s ∈ L and |s| = 2p ≥ p.
Step 2: By condition (1), |xy| ≤ p, so the substring xy lies entirely within the leading block of a's. By condition (2), y consists of at least one 'a' — say y = aᵏ for some k ≥ 1.
Step 3: Consider i = 2: xy²z = a^(p+k) b^p. Since k ≥ 1, we have p+k > p, so there are more a's than b's.
Conclusion: xy²z ∉ L, contradicting condition (3). Therefore L is not regular.

Other classic non-regular languages (GATE favourites):

• { ww | w ∈ {a,b}* } — requires remembering the first half to check the second.
• { aᵖ | p is prime } — pumping changes the count, and the resulting count need not be prime.
• { aⁿ² | n ≥ 0 } — perfect-square counts cannot be maintained by a finite state machine.
• Balanced parentheses — requires counting, hence a stack (context-free, not regular).

Why it matters

The regex → NFA → DFA pipeline is the actual mechanism inside grep, lex/flex and most tokenisers. Understanding the theory tells an engineer when a problem outgrows regex — balanced brackets, nested function calls, XML — and requires a parser (pushdown automaton / context-free grammar) instead.

Real-world example: validating "balanced brackets" in a code editor — { [ ( ) ] } correctly matched — cannot be done by a pure regular expression, because counting unbounded nesting requires memory that grows with input size, which a finite automaton does not have. That is exactly why programming languages are parsed by stack-based (context-free) tools, not regex engines.

Common misconception: that NFAs are "more powerful" than DFAs because they can try multiple paths simultaneously. They are not — they recognise exactly the same class of languages. Non-determinism only makes some machines smaller or easier to design. Every NFA can be converted to a DFA (at potential exponential cost in states) for the same language.

:::keypoints Key points

• A DFA has exactly one transition per (state, symbol); an NFA may have zero, one or many, plus ε-moves.
• NFA and DFA recognise the same class of languages (regular); subset construction converts NFA → DFA at up to 2^|Q| cost.
• Regular languages are closed under union, intersection, complement, concatenation, star, reverse and homomorphism.
• DFA membership, emptiness, equivalence, finiteness and minimisation are all decidable in polynomial time.
• The Pumping Lemma is a contradiction tool to prove non-regularity — not to prove regularity.
• { aⁿbⁿ }, balanced brackets, and { ww } are canonical non-regular languages.
• The regex → ε-NFA → DFA → minimisation pipeline underlies grep, lex, and all tokenisers.
  :::

:::memory
"DFA Drives, NFA Naps — same roads" — DFA deterministically drives one path; NFA non-deterministically explores many; but both cover the same roads (regular languages). The Pumping Lemma is the speed bump that kicks out languages too complex for this road.
:::

:::recap

• Finite automata = computation with a fixed, bounded amount of memory.
• NFAs are convenient and compact, not more powerful, than DFAs.
• Regular languages are robustly closed under all standard set and string operations.
• The Pumping Lemma proves non-regularity by contradiction; pick s carefully and consider all valid splits.
  :::

A Deterministic Finite Automaton is a 5-tuple M = (Q, Σ, δ, q0, F), where Q is a finite set of states, Σ is the input alphabet, δ: Q × Σ → Q is the transition function (TOTAL and single-valued), q0 is the start state, and F ⊆ Q is the set of accepting states. KEY PROPERTY: for each (state, symbol) pair there is EXACTLY ONE transition — no choices, no epsilon moves. A string w is accepted if δ*(q0, w) ∈ F. The language L(M) is the set of all accepted strings. Memory aid: 'DFA = Definite, Fixed, Always one move.' Because transitions are total, a complete DFA on |Σ| symbols and n states has exactly n×|Σ| transition entries.

Two recurring GATE patterns: (1) Binary numbers divisible by k → use k states labeled by remainder mod k. Reading bit b updates state r to (2r + b) mod k. Start = accept = state 0. This needs exactly k states. (2) Strings containing a fixed substring of length m → needs (m+1) states minimum (track longest matched prefix, like KMP). 'Ending with' pattern of length m also needs states tracking the suffix. Shortcut: 'divisible-by-k' = k states; 'last/first symbol' constraints multiply state counts. For 'i-th symbol from end equals x' you need 2^i states (must remember last i symbols).

States {q0, q1, q2} represent remainder mod 3. δ(qr, b) = q(2r+b) mod 3. Transitions: δ(q0,0)=q0, δ(q0,1)=q1; δ(q1,0)=q2, δ(q1,1)=q0; δ(q2,0)=q1, δ(q2,1)=q2. Start state q0, accepting state {q0}. Check '110' (=6): q0 →1→ q1 →1→ q0 →0→ q0, accepted (6 mod 3 = 0). Check '101' (=5): q0→1→q1→0→q2→1→q2, rejected (5 mod 3 = 2). This 3-state machine is minimal — divisibility-by-k DFAs cannot have fewer than k states.

Why are NFAs (nondeterministic finite automata) easier to design but harder to run? Because at any moment an NFA can be in several states "at once," while a real processor can only be in one. The subset construction, also called the powerset construction, is the recipe that simulates that "many-states-at-once" feeling with a single deterministic machine. It's one of the most elegant constructions in the GATE Theory-of-Computation syllabus — and one of the most reliably tested.

Definition: A DFA (Deterministic Finite Automaton) has exactly one move from each state on each input symbol; no choices, no ε-transitions.
Definition: An NFA (Nondeterministic Finite Automaton) may have zero, one, or many moves on a symbol, and may include ε-transitions that change state without consuming input.
Definition: The subset construction is an algorithm that, given an NFA with state set Q, builds an equivalent DFA whose state set is a subset of the power set 2^Q.

The intuition: "What states could I be in right now?"

Imagine running the NFA on a string. After reading the first symbol, the NFA might be in any of several states simultaneously. After reading the second symbol, the set of "possible current states" shifts. If we track the whole set of possible current states as one object, that set behaves deterministically — given a set S and an input a, the next set is uniquely determined by S and a.

So we promote each set of NFA states to a single DFA state. Determinism re-appears, at the cost of having up to 2ⁿ DFA states for an n-state NFA.

This is the Rabin-Scott theorem (1959): every NFA has an equivalent DFA recognising the same language.

ε-closure: the foundation

Before doing anything else, you need ε-closure.

Definition: ε-closure(q) is the set of all NFA states reachable from state q using zero or more ε-transitions, including q itself. For a set S, ε-closure(S) is the union of ε-closure(q) for every q in S.

Why we need it: an NFA can silently slide along ε-edges without reading input. Any state reachable via ε-edges is a state we "could be in" at no cost, so it must be included whenever we record current possibilities.

Practical tip: compute ε-closure by BFS or DFS over the ε-only graph.

The algorithm, step by step

Given NFA N = (Q, Σ, δ, q₀, F), construct DFA D:

1. Start state of D = ε-closure({q₀}).
2. Worklist: a queue of DFA states to process. Initially contains the start state.
3. Pick a DFA state S from the worklist. For each input symbol a in Σ:
   • Compute move(S, a) = union of δ(q, a) for every NFA state q in S.
   • Compute T = ε-closure(move(S, a)).
   • If T is empty, the transition leads to the dead state ∅.
   • If T is not already a DFA state, add it as a new state and put it on the worklist.
   • Add the transition S --a--> T to D.
4. Accepting states of D: every DFA state S that contains at least one NFA accepting state (S ∩ F ≠ ∅).
5. Stop when the worklist is empty.

Worked example

Let N have states {1, 2, 3}, alphabet {a, b}, start state 1, accepting state 3, and transitions:

• δ(1, a) = {1, 2}
• δ(1, b) = {1}
• δ(2, b) = {3}
• No ε-transitions, no other moves.

Construction:

• D's start state = {1}.
• From {1} on a: move = {1, 2}, ε-closure = {1, 2}. New DFA state S₁ = {1, 2}.
• From {1} on b: move = {1}. Goes back to {1}.
• From {1, 2} on a: move(1,a) ∪ move(2,a) = {1, 2} ∪ {} = {1, 2}. Self-loop.
• From {1, 2} on b: move(1,b) ∪ move(2,b) = {1} ∪ {3} = {1, 3}. New DFA state S₂ = {1, 3}.
• From {1, 3} on a: move = {1, 2} ∪ {} = {1, 2}. Goes to S₁.
• From {1, 3} on b: move = {1} ∪ {} = {1}. Goes to {1}.
• Accepting DFA states: any subset containing state 3, i.e., {1, 3}.

DFA has 3 reachable states: {1}, {1, 2}, {1, 3}. Far fewer than 2³ = 8.

The 2ⁿ blow-up — and why it matters

In the worst case, the DFA really does need every one of the 2ⁿ subsets. A famous family proving this is the language Lₙ = "strings over {0, 1} whose n-th symbol from the end is 1." A small NFA of n+1 states recognises Lₙ by guessing where the "n-th from end" lies. The minimal DFA, however, needs 2ⁿ states because it must remember the last n symbols read.

So when GATE asks "what is the maximum number of states in a DFA equivalent to an n-state NFA?" the answer is 2ⁿ, and the bound is tight.

Why it matters: nondeterminism is a real expressive convenience but not a computational miracle — the price is paid in DFA state count.

Why only reachable subsets

Naively listing all 2ⁿ subsets wastes effort. The algorithm above only adds a subset when it is reachable via the BFS from {q₀}'s ε-closure. Many subsets are unreachable in practice; on textbook problems the DFA typically has between n and 2n states, not 2ⁿ.

This is why "reachable subset construction" is the standard description of the algorithm.

The dead state ∅

When some DFA state S has no NFA transition for symbol a, move(S, a) is empty and ε-closure(∅) = ∅. The empty set is itself a DFA state — the dead or trap state. It is non-accepting and loops to itself on every symbol. Many textbook diagrams omit ∅ for clarity; GATE expects you to know it exists when transitions are "missing."

Why it matters: A DFA is total by definition — every state has a transition on every symbol. So if you draw an NFA-to-DFA result and your DFA isn't total, add ∅ as the destination of the missing edges.

Common misconception: Students think subset construction only works when the NFA has no ε-transitions. Wrong — the algorithm explicitly uses ε-closure precisely to absorb ε-edges. The construction is more powerful, not weaker, with ε-transitions.

Common misconception #2: "If the NFA has n states, the DFA has exactly 2ⁿ states." No — at most 2ⁿ. Most practical NFAs convert to DFAs with a small number of reachable subsets.

:::compare

:::keypoints

• Subset construction proves NFAs and DFAs recognise exactly the same class of languages — the regular languages.
• A DFA state is a set of NFA states the simulator could currently be in.
• ε-closure is applied to the start state and to every move result.
• A DFA state is accepting iff it contains at least one NFA accepting state.
• The empty set ∅ is the dead/trap state.
• Worst case: 2ⁿ DFA states, achieved by languages like "n-th symbol from end is 1."
• Build only reachable subsets to keep the DFA small.
• The algorithm terminates because there are at most 2ⁿ possible subsets.
  :::

:::memory
"Sets, Symbols, ε, Stop" — the four-step rhythm:

1. Set the start = ε-closure({q₀}).
2. For each Symbol, compute move then ε-closure.
3. Apply ε-closure after every move.
4. Stop when no new subsets appear.

And: "A DFA state is Accepting if it Accepts any NFA accepting state inside it."
:::

Question: An NFA over {a, b} has states {p, q, r}, start = p, accepting = {r}, transitions δ(p,a)={p,q}, δ(p,b)={p}, δ(q,b)={r}. No ε. What is the start state of the equivalent DFA and how many reachable DFA states does it have?
Solution:
Step 1: No ε-transitions, so ε-closure(X) = X for any set X. Start of DFA = {p}.
Step 2: From {p} on a: δ(p,a) = {p, q}. New state S₁ = {p, q}.
Step 3: From {p} on b: {p}. Self-loop.
Step 4: From {p, q} on a: δ(p,a) ∪ δ(q,a) = {p, q} ∪ ∅ = {p, q}. Self-loop.
Step 5: From {p, q} on b: δ(p,b) ∪ δ(q,b) = {p} ∪ {r} = {p, r}. New state S₂ = {p, r}.
Step 6: From {p, r} on a: δ(p,a) ∪ δ(r,a) = {p, q} ∪ ∅ = {p, q}. Goes to S₁.
Step 7: From {p, r} on b: {p} ∪ ∅ = {p}.
Conclusion: DFA start = {p}; reachable states are {p}, {p, q}, {p, r} — three states. Accepting state is {p, r}.

Real-world example: Lexical analysers in compilers (Flex, ANTLR) generate scanners from regular expressions. The standard pipeline is regex → NFA (Thompson's construction) → DFA (subset construction) → minimised DFA. By the time your gcc or python interpreter is recognising identifiers like main or print, it is running a deterministic table-lookup DFA produced via exactly this construction.

:::recap

• Subset construction = "let each DFA state remember the set of NFA states the simulator could be in."
• ε-closure is the safety net that absorbs free transitions.
• At most 2ⁿ DFA states, often far fewer if you only build reachable ones.
• This construction is the formal proof that NFAs and DFAs are equally expressive.
  :::

Drill a hole through a uniform sphere and the gravity story suddenly gets interesting. The trick is to refuse to treat the hollow body as one messy object — instead, build it from clean pieces you already know how to handle. This is the cavity-superposition method, and once you see it once, it will rescue you in every "hollowed-out sphere" problem on JEE Main.

Definition: Superposition principle (gravitation) — the gravitational field at any point due to a collection of masses is the vector sum of the fields each mass would produce alone at that point.

Definition: Cavity — an empty region carved out of a solid body. Because empty space contributes no mass, removing material is mathematically equivalent to adding a body of the same shape with negative density on top of the original solid.

The Trick: Whole Minus Hole

The problem hands you a body that is hard to describe in one shot — a sphere with a chunk missing. A direct integration would be painful: the limits of the integral now have to dodge the cavity. Instead, rewrite the body as two simpler bodies you already have formulas for:

(solid sphere with cavity) = (full solid sphere) + (smaller sphere of negative mass, sitting where the cavity is)

When you add a negative-mass sphere to a full sphere, the masses cancel exactly inside the cavity region — leaving you with what the original hollowed body looked like. Because gravity obeys superposition, the field at any point P is just:

E_net(P) = E_full(P) − E_removed(P)

where E_full is the field of the complete uniform sphere and E_removed is the field of the small sphere that would have occupied the cavity, both computed at the same point P. Subtraction handles the "negative mass" automatically.

Setting Up the Geometry

A solid sphere has radius R, uniform density ρ, total mass M. A spherical cavity of radius R/2 is carved so that it touches the centre of the main sphere and also touches the surface. That fixes the geometry: the centre of the cavity must lie on the line from the main centre to the surface, at a distance R/2 from the main centre (because the cavity itself has radius R/2, so its near edge sits at the main centre and its far edge sits at the surface).

Call the main centre O and the cavity centre C. Then OC = R/2. We are asked for the field at C — the very middle of the missing chunk.

The removed sphere had radius R/2 and the same density ρ. Its mass is therefore

M_removed = ρ × (4/3)π(R/2)³ = ρ × (4/3)πR³ × 1/8 = M/8.

That clean 1/8 fraction is the payoff for choosing a cavity radius of exactly R/2.

Field From the Full Solid Sphere at the Cavity Centre

The point C lies inside the imagined full solid sphere, at distance R/2 from O. For a uniformly dense solid sphere, the field at an interior point at distance r from the centre is

E_inside = GM r / R³, directed toward O.

(This is the gravitational analogue of Gauss's law: only the mass within radius r contributes, and that enclosed mass scales as r³.)

Plugging r = R/2:

E_full(C) = GM (R/2) / R³ = GM / (2R²), pointing from C toward O.

Field From the Removed Sphere at Its Own Centre

Here is the elegant collapse. The point C is the centre of the removed sphere. By symmetry — every bit of mass in a uniform sphere has a mirror twin on the opposite side of the centre — the gravitational field at the centre of any uniform spherical body is exactly zero.

E_removed(C) = 0.

Net Field at the Cavity Centre

Subtract:

E_net(C) = E_full(C) − E_removed(C) = GM/(2R²) − 0 = GM/(2R²).

Direction: from C toward the main centre O. That makes physical sense — the "missing" chunk is on the surface side, so the surviving mass lies preferentially on the opposite side of C, pulling C inward toward O.

A delightful consequence (worth knowing for MCQs): if you compute the field at every point inside the cavity using the same trick, you find that the field is uniform throughout the cavity — same magnitude, same direction everywhere. The cavity has, in effect, a perfectly uniform gravitational field. This is the gravitational twin of the famous result for a charged spherical cavity in electrostatics.

Why it matters: JEE Main loves geometry-heavy gravitation problems precisely because they punish students who only memorise formulas. Once you internalise "whole minus hole," cavities of any size and offset reduce to two formula lookups and one subtraction — no calculus required. The same logic powers electrostatic cavity problems, magnetised-sphere cavity problems, and even cavity-in-current-carrying-cylinder problems.

Real-world example: Geophysicists modelling underground caverns, oil reservoirs, or salt domes use exactly this superposition idea to predict gravity anomalies — tiny dips in local g measured by sensitive gravimeters. The "missing mass" of an oil-filled void reads as a negative-density blob sitting inside the rock.

Common misconception: Students sometimes write E_full(C) = GM/(R/2)², treating C as if it were outside a small sphere of mass M. But C is inside the full sphere of radius R, so the linear-in-r interior formula applies, not the 1/r² exterior one. Whenever you use superposition, ask: "Is the test point inside or outside each of my imagined component bodies?"

Question: A uniform solid sphere of mass M and radius R has a spherical cavity of radius R/4 carved out, with the cavity centre at distance 3R/4 from the main centre. Find the gravitational field at the main centre O.
Solution:
Step 1: Mass of removed sphere = M × (R/4)³ / R³ = M/64.
Step 2: At O, the full sphere produces zero field (centre of a uniform sphere). E_full(O) = 0.
Step 3: At O, the removed sphere is treated as a small sphere of mass M/64 whose centre is at distance 3R/4 from O. Since O lies outside this small sphere (its radius is only R/4), use the exterior formula: E_removed(O) = G(M/64)/(3R/4)² = GM × 16 / (64 × 9R²) = GM/(36R²), directed from O toward the removed sphere's centre.
Step 4: E_net(O) = E_full(O) − E_removed(O) = 0 − GM/(36R²), magnitude GM/(36R²).
Conclusion: The field at O has magnitude GM/(36R²), directed away from the cavity (i.e., the surviving mass pulls O in the direction opposite to the hole).

:::compare

:::keypoints

• Cavity problems = (whole sphere) − (sphere that would have filled the cavity), at every test point.
• Inside a uniform solid sphere: E = GMr/R³, linear in r, pointing to centre.
• Outside a uniform solid sphere: E = GM/r², same as a point mass at the centre.
• Field at the centre of any uniform sphere is zero — pure symmetry.
• Mass of the removed piece scales as (r_cavity / R)³ × M; for r_cavity = R/2 it is M/8.
• Field inside the cavity of this geometry comes out uniform — same magnitude, same direction everywhere in the hole.
• Always check whether the test point is inside or outside each component sphere before picking a formula.
• Direction matters: superposition is vector subtraction, not scalar.
  :::

:::memory
"Whole minus Hole." Picture filling the cavity back in with the same density, then immediately filling it again with anti-matter (negative density). The two new pieces cancel inside the cavity and leave behind your original hollowed sphere — but now you have two clean spheres to compute on.
:::

:::recap

• Replace any hollow body with "full body + negative-mass plug" and superpose.
• At the cavity centre here, E_full = GM/(2R²) toward O, E_removed = 0, so E_net = GM/(2R²) toward O.
• The interior-sphere formula E = GMr/R³ does the heavy lifting whenever the test point is inside a uniform sphere.
• The same trick works for electric fields, magnetic fields and currents — superposition is the universal lever.
  :::

NFA: states {q0,q1}, start q0, final {q1}, no epsilon. Transitions: q0 on a -> {q0,q1}; q0 on b -> {q0}; q1 on a -> {}; q1 on b -> {}. DFA start = {q0}. From {q0}: on a -> {q0,q1}; on b -> {q0}. New state {q0,q1} (contains q1 => ACCEPTING): on a -> move(q0,a) U move(q1,a) = {q0,q1} U {} = {q0,q1}; on b -> {q0} U {} = {q0}. DFA states: {q0}(start), {q0,q1}(final). Transition table: {q0} --a--> {q0,q1}, {q0} --b--> {q0}; {q0,q1} --a--> {q0,q1}, {q0,q1} --b--> {q0}. This DFA accepts strings ending in 'a' (the language (a|b)*a). Only 2 of the possible 2^2=4 subsets are reachable, illustrating that the 2^n bound is rarely tight.

When you first met the DFA, every input letter pushed the machine to exactly one next state — life was deterministic, almost boring. The NFA breaks that rule on purpose: on a single letter, the machine may branch into several possible futures at once, and it succeeds the moment any one of those futures lands in a final state. That single change unlocks far shorter machine designs and is one of the most elegant ideas in the entire Theory of Computation syllabus for GATE CSE.

Definition: A Nondeterministic Finite Automaton (NFA) is a 5-tuple M = (Q, Σ, δ, q0, F), where Q is a finite set of states, Σ is a finite input alphabet, q0 ∈ Q is the start state, F ⊆ Q is the set of final (accepting) states, and the transition function is δ: Q × Σ → 2^Q. That last piece is the heart of it — δ now returns a set of states, possibly empty, rather than a single state.

Definition: An ε-NFA (or NFA with epsilon moves) is an NFA whose transition function is extended to δ: Q × (Σ ∪ {ε}) → 2^Q, allowing the machine to change state without consuming any input symbol.

Definition: A string w ∈ Σ* is accepted by an NFA iff there exists at least one computation path from q0, consuming exactly the symbols of w, that ends in a state belonging to F. Acceptance is by existence.

What "nondeterminism" really means

A DFA, given a state and an input symbol, has one and only one move. An NFA, in the same situation, may have zero moves, one move, or several moves. Picture it like this: at every step the machine "splits" into all the threads it can take. The string w is accepted if just one of those threads, running in parallel in our imagination, ends in F when the input is exhausted. If every single thread dies (no transition available) or ends in a non-final state, the string is rejected.

This is sometimes called the angelic interpretation of nondeterminism — the machine is allowed to magically choose the right path if one exists. You can think of an NFA as a "guess-and-check" device: it guesses which path to take and accepts if the guess can work out. Memory aid: NFA = guess and check — accept if any guess works.

ε-transitions and ε-closure

ε-moves let the machine slide from one state to another for free — without reading any input. This is great for gluing sub-automata together in constructions like Thompson's construction for regular expressions.

Definition: The ε-closure of a state q, written ECLOSE(q), is the set of all states reachable from q using zero or more ε-transitions. For a set S, ECLOSE(S) is the union of ECLOSE(q) for every q ∈ S. The state q itself is always in its own ε-closure.

When you simulate an ε-NFA on the fly, the trick is to keep "current set of states" closed under ε. After every symbol consumed you re-apply ECLOSE so that any state silently reachable is also in your active set. Missing this step is the single most common silly mistake in GATE numerical answer questions on automata simulation.

The big equivalence theorem

Here is the result that often surprises students on first contact: NFAs, ε-NFAs and DFAs all recognise exactly the same class of languages — the regular languages. Nondeterminism does not let an NFA accept anything that some DFA cannot also accept; it only lets the description be more compact.

The constructive proof is the subset construction (also called powerset construction). Given an NFA with n states, you build an equivalent DFA whose states are subsets of the NFA's state set — so up to 2^n states. Each DFA state remembers "the set of NFA states the machine could currently be in." Acceptance in the DFA is: any subset that contains at least one NFA-final state is final.

For ε-NFAs, the construction is the same but with ECLOSE applied at the start state and after every transition.

Why the equivalence matters

It tells us that "regular language" is a robust notion — it does not depend on whether the recognising machine is deterministic or not, or whether it can take silent steps. This robustness is exactly why regular languages are also captured by regular expressions and by right-linear grammars. The cost we pay is size: the equivalent DFA can be exponentially larger than the original NFA. There is a classical family of languages L_n (strings whose nth-last symbol is 1) for which any NFA needs n+1 states but every DFA needs 2^n states.

Real-world example

Inside grep, egrep, lexical analysers in compilers (lex / flex), and string-matching libraries, regular expressions are first compiled into an ε-NFA via Thompson's construction, then converted to a DFA via subset construction, and finally minimised. The NFA is small and easy to build; the DFA is fast to run. You are using this exact pipeline every time you write a regex in Python, Java or while filtering log files on a Linux server.

Common misconception

Misconception: "An NFA is more powerful than a DFA because it can do more." Correction: An NFA is more convenient, not more powerful. Power, in formal language theory, means "the class of languages recognised." NFAs and DFAs recognise the exact same class — the regular languages. The difference is succinctness of the description, not strength.

A second classic confusion: "If the NFA has no transition on some symbol from the current state, the machine crashes and the whole computation fails." Not quite — only that particular thread dies. Other live threads keep running, and the string is still accepted if any thread eventually reaches F.

Worked example

Question: Let N be an NFA over Σ = {a, b} with states {q0, q1, q2}, start state q0, final state {q2}, and transitions δ(q0,a) = {q0, q1}, δ(q0,b) = {q0}, δ(q1,b) = {q2}, δ(q2,a)=δ(q2,b)={q2}. Does N accept the string "aab"?

Solution:
Step 1: Start with the active set {q0}.
Step 2: Read 'a'. New active set = δ(q0,a) = {q0, q1}.
Step 3: Read 'a'. From q0 on 'a' → {q0, q1}; from q1 on 'a' there is no transition, so that thread dies. New active set = {q0, q1}.
Step 4: Read 'b'. From q0 on 'b' → {q0}; from q1 on 'b' → {q2}. New active set = {q0, q2}.
Step 5: Input exhausted. Active set {q0, q2} contains the final state q2.
Conclusion: At least one computation path ends in F, so "aab" is accepted.

Notice the language being recognised: any string that has "ab" anywhere as a substring. The same language needs a 3-state DFA — same size here, but for n-th-from-last patterns the DFA blows up exponentially.

:::compare

:::keypoints

• An NFA is M = (Q, Σ, δ, q0, F) with δ: Q × Σ → 2^Q returning a set of states.
• An ε-NFA adds ε-moves: free transitions that consume no input symbol.
• A string is accepted iff at least one computation path ends in a final state — acceptance is by existence.
• ε-closure of a state set = all states reachable using only ε-moves; always re-apply after every symbol.
• DFA, NFA and ε-NFA are equivalent in language-recognising power; all capture exactly the regular languages.
• The subset construction converts an NFA with n states into a DFA with up to 2^n states.
• NFAs gain succinctness, not power; the size blow-up is the price of determinisation.
  :::

:::memory
"Guess, branch, check — accept if any branch survives." For ε-NFAs add: "Free moves first, then read the letter, then free moves again" — i.e., always wrap your transitions in ε-closure on both sides.
:::

:::recap

• NFA = nondeterministic finite automaton with set-valued δ; ε-NFA additionally allows silent ε-moves.
• Acceptance is existential: one good path is enough.
• DFA ≡ NFA ≡ ε-NFA in language power; subset construction proves it constructively.
• Nondeterminism buys compactness, not new languages.
  :::

Every NFA looks like it has a magical power — it can "choose" the right transition out of several possibilities. But computers don't guess. To actually run an NFA on a machine, we convert it into an equivalent DFA where every step is deterministic. The trick that makes this work is one of the most elegant ideas in automata theory: the subset construction.

Definition: Subset construction (also called the powerset construction) is the algorithm that takes any NFA with n states and produces an equivalent DFA whose states are subsets of the NFA's state set.

Definition: ε-closure of a state q is the set of all NFA states reachable from q by following zero or more ε-transitions (including q itself).

The core idea — simulating "all possibilities at once"

When an NFA reads an input, it might be in several states simultaneously because of non-determinism and ε-moves. The DFA we build keeps track of the entire set of NFA states the machine could currently be in. Each DFA state is literally a label like {q0, q2, q5} — a snapshot of "where could the NFA be right now?"

So if the NFA has n states, the DFA could in principle have one state for every subset of those n states. Since a set of n elements has 2^n subsets, the upper bound on the number of DFA states is 2^n. This includes the empty set ∅, which represents the situation where the NFA cannot be in any valid state — a dead state from which no acceptance is possible.

The algorithm — step by step

The construction is mechanical once you internalise three ingredients:

Step 1: Start state. The DFA's start state is the ε-closure of the NFA's start state, i.e., ε-closure({q0}).

Step 2: Transition function. For a DFA state S and an input symbol a:
δ_DFA(S, a) = ε-closure( ∪ { δ(q, a) : q ∈ S } )
In words: from every NFA state in S, take all a-transitions, union the results, then take the ε-closure of that union.

Step 3: Accepting states. A DFA state S is accepting iff S contains at least one NFA final state.

Step 4: Build only reachable subsets. Start from the initial DFA state and expand outwards by computing transitions. Add a new subset only when it actually appears as a destination. This is why real DFAs are usually much smaller than 2^n — most subsets are unreachable.

Why it matters

Subset construction is the bridge between the expressive world of NFAs (easy to design, ε-moves, multiple branches) and the executable world of DFAs (linear-time simulation, one path through the input). Every regex-to-DFA compiler — grep, lex, flex, JavaScript regex engines — uses this idea under the hood. In GATE CSE, this topic is a perennial favourite: questions ask you to either run the construction by hand or count DFA states for a given NFA.

Worst case: the 2^n bound is tight

Usually we say "in practice the DFA is small". But there are languages where the bound truly is exponential. The classic example is the language

L_n = { w ∈ {0,1}* : the n-th symbol from the right end of w is 1 }

An NFA for L_n needs only n+1 states (a simple chain that guesses where the n-th-last symbol is). But any DFA accepting L_n must have at least 2^n states, because the DFA has to remember the last n input symbols, and there are 2^n possible n-bit windows. This is one of the cleanest demonstrations that non-determinism truly compresses information.

Real-world example: Consider an Indian PAN-card validator. The pattern "5 letters, 4 digits, 1 letter" can be written as a tiny NFA with a few states. When a fintech firm bakes this into a high-throughput compliance pipeline, it first compiles the regex to an NFA, then runs subset construction to obtain a DFA that validates millions of PAN strings per second — each character causing exactly one DFA transition, no backtracking, no branching.

Common misconception: Students often think the DFA produced by subset construction is automatically minimal. It is not. Subset construction can leave equivalent states that should be merged. You apply the DFA minimisation algorithm (Hopcroft / partition refinement) afterwards to obtain the unique minimal DFA. The two algorithms are siblings, not the same algorithm.

A worked example

Question: Convert the NFA below into a DFA.
States: {A, B, C}, alphabet {0,1}, start A, final C.
Transitions: δ(A,0)={A,B}, δ(A,1)={A}, δ(B,1)={C}.

Solution:
Step 1: Start state = {A} (no ε-moves here, so ε-closure({A}) = {A}).
Step 2: From {A} on 0: δ(A,0) = {A,B} → new DFA state {A,B}. On 1: δ(A,1) = {A} → stays at {A}.
Step 3: From {A,B} on 0: δ(A,0) ∪ δ(B,0) = {A,B} ∪ ∅ = {A,B}. On 1: δ(A,1) ∪ δ(B,1) = {A} ∪ {C} = {A,C} → new DFA state.
Step 4: From {A,C} on 0: {A,B} ∪ ∅ = {A,B}. On 1: {A} ∪ ∅ = {A}.
Step 5: No new subsets appear. Mark every DFA state that contains C as accepting → {A,C}.
Conclusion: The reachable DFA has just 3 states — {A}, {A,B}, {A,C} — far fewer than the 2^3 = 8 upper bound, because we only enumerated reachable subsets.

Handling ε-NFA carefully

When the NFA has ε-moves, you must take the ε-closure at three places:

1. The start state — ε-closure({q0}).
2. Every transition result — after computing the union of δ(q,a) for q in S, wrap it in ε-closure.
3. Nowhere else — ε is not an input symbol; the DFA's input alphabet is the original alphabet without ε.

Forgetting the closure on transitions is the single most common mistake in GATE-style problems and produces a DFA that quietly rejects strings it should accept.

:::compare

:::keypoints

• DFA states are subsets of NFA states; upper bound is 2^n.
• Start state = ε-closure of the NFA start state.
• Transition: union of NFA transitions, then ε-closure.
• A DFA state is accepting iff it contains an NFA final state.
• Always build only reachable subsets — don't list all 2^n.
• ∅ acts as a dead state (no NFA state is "alive").
• Worst-case 2^n is tight for languages like "n-th symbol from the end".
• Subset construction does not minimise — apply DFA minimisation afterwards.
  :::

:::memory
Remember the four C's: Closure on start, union, Closure on transitions, Contains-final means accept, Carry only reachable subsets forward.
:::

:::recap

• Subset construction makes the non-deterministic NFA executable as a DFA.
• The DFA tracks the set of all NFA states the machine could currently be in.
• Worst-case blow-up is exponential but usually polynomial in practice.
• Apply minimisation separately to get the smallest equivalent DFA.
  :::

Language L_k = strings over {0,1} whose k-th symbol from the END is 1. An NFA recognizes L_k with k+1 states (guess the position, then count k-1 more). But the MINIMAL DFA needs exactly 2^k states because it must remember the last k symbols seen. This is the classic example proving the subset-construction 2^n upper bound is tight. For k=2: NFA has 3 states, minimal DFA has 4 states. Memory aid: 'NFA guesses where; DFA must remember everything.' GATE frequently asks for DFA state counts of such 'from-the-end' languages.

Among all the tools in Theory of Computation, the Myhill-Nerode theorem is the sharpest knife. It gives you both a clean proof technique for non-regularity AND the exact size of the minimal DFA for any regular language — all from a single relation on strings.

Definition: For a language L over alphabet Σ, two strings x and y are L-equivalent, written x ≡_L y, if for every string z ∈ Σ*, xz ∈ L if and only if yz ∈ L. In other words, no suffix z can "tell them apart".

Definition: The index of L is the number of equivalence classes of ≡_L.

The intuition — strings that "look the same" to L

Imagine you are designing a DFA for L. After reading some prefix x, the only thing that matters for the future is what continuations z can take the machine to an accepting state. If two prefixes x and y agree on every possible suffix — meaning xz ∈ L ⟺ yz ∈ L for all z — then your DFA can sit in the same state after reading either prefix. Why? Because the state of a DFA is supposed to capture exactly what is needed about the past to decide the future.

So ≡_L is doing the work of "merging" prefixes that the language genuinely cannot distinguish. Conversely, if some suffix z accepts xz but rejects yz, then x and y MUST end up in different states, because one will need to accept and the other reject if z follows.

The theorem itself

Myhill-Nerode Theorem. L is regular if and only if ≡_L has finite index. Moreover, the index of ≡_L equals the number of states in the unique minimal DFA for L.

This is two facts wrapped together:

1. Regularity test: L is regular ⟺ finitely many equivalence classes.
2. Exact lower bound: If you can exhibit n pairwise distinguishable strings, the minimal DFA needs at least n states. If exactly n classes exist, the minimum is exactly n.

Why it matters: This is the only technique that gives you the EXACT minimal DFA size for arbitrary regular languages. The Pumping Lemma can only refute regularity (one direction) and tells you nothing about state counts. Myhill-Nerode is both proof and constructive bound.

Using it to prove non-regularity

To prove L is not regular, exhibit an infinite family of strings {x_1, x_2, x_3, ...} that are pairwise distinguishable. For each pair x_i, x_j with i ≠ j, you must produce a suffix z that separates them: either x_i z ∈ L while x_j z ∉ L, or vice versa.

Classic example: L = { aⁿbⁿ : n ≥ 0 }.
Take the family {ε, a, aa, aaa, ..., aⁿ, ...}. For any two distinct prefixes aⁱ and aʲ with i ≠ j, choose the suffix z = bⁱ. Then aⁱ · bⁱ = aⁱbⁱ ∈ L, but aʲ · bⁱ ∉ L because j ≠ i. Hence aⁱ ≢_L aʲ for every pair. Infinitely many classes ⟹ L is not regular.

Compare this with the Pumping Lemma proof of the same fact — Myhill-Nerode is usually cleaner because you do not have to wrestle with arbitrary decompositions; you just pick distinguishing suffixes.

Using it to compute minimal DFA size

To find the minimal DFA size for a known regular L, enumerate all equivalence classes of ≡_L. For example, take L = { w ∈ {a,b}* : w ends in ab }. Track the relevant history about the last two characters:

• Class 1: strings that do NOT end in a and do NOT end in ab. After such a prefix, you need both an a then a b.
• Class 2: strings ending in a (but not yet ab). One more b finishes.
• Class 3: strings ending in ab. Already accepting; if a comes next move to class 2, if b comes move to class 1.

Three classes ⟹ minimal DFA has exactly 3 states. You can draw the DFA directly: each class is a state; the start state is the class of ε; the accepting states are the classes containing strings in L.

How it connects to DFA minimization

The state-merging algorithms you learned (table-filling / partition refinement) are really computing ≡_L on the reachable states of a given DFA. Two states p and q can be merged if and only if for every input z, δ*(p, z) and δ*(q, z) agree on acceptance. That is precisely the DFA-state version of ≡_L. So the theorem and the algorithm are two faces of the same idea: the minimum DFA is the quotient of any DFA by this indistinguishability relation.

Real-world example: Lexical analysers (lex / flex) used by compilers convert regular expressions into DFAs. Why minimum DFAs? Because at compile time you may have thousands of token patterns, and each redundant state is memory and a branch in the table. The compilers literally implement a Myhill-Nerode-style minimisation pass.

Common misconception: "≡_L is a relation on states." It is not — it is a relation on strings (prefixes). The state-level cousin (sometimes written ≡_D) lives on the DFA's state set. Mixing the two leads to wrong proofs in GATE answers.

Common misconception 2: "If I exhibit k pairwise distinguishable strings, the language is not regular." Wrong — it only proves the minimal DFA needs at least k states. For non-regularity you need an INFINITE distinguishable family.

Question: Prove that L = { 0ⁿ1ⁿ : n ≥ 1 } is not regular using Myhill-Nerode.
Solution:
Step 1: Consider the infinite family {0¹, 0², 0³, ..., 0ⁱ, ...}.
Step 2: For i ≠ j, take z = 1ⁱ. Then 0ⁱ · 1ⁱ = 0ⁱ1ⁱ ∈ L, but 0ʲ · 1ⁱ ∉ L since j ≠ i.
Step 3: Every pair from the family is distinguishable, so ≡_L has infinitely many classes.
Conclusion: ≡_L has infinite index, so by Myhill-Nerode, L is not regular.

:::compare

:::keypoints

• x ≡_L y means no suffix can distinguish x from y in L.
• The index of L is the number of ≡_L classes.
• L is regular ⟺ index is finite.
• The index equals the exact number of states in the minimal DFA.
• To prove non-regularity, exhibit an infinite family of pairwise-distinguishable strings.
• To compute minimal DFA size, count the distinct equivalence classes.
• Myhill-Nerode strictly subsumes the Pumping Lemma in power for non-regularity.
  :::

:::memory
"Distinguishable suffixes ⟹ distinct states." If some z separates xz and yz on membership, x and y must live in different DFA states.
:::

:::recap

• ≡_L compares prefixes by what every suffix does to them.
• Finite index ⟺ regular; infinite index ⟺ not regular.
• Index = exact minimum DFA size.
• Pumping Lemma is one-directional; Myhill-Nerode is the full characterisation.
  :::

DFA minimization sounds intimidating but reduces to one core idea: states that behave identically from this point onward might as well be the same state. The table-filling algorithm — also called the partition refinement method — turns this idea into a mechanical procedure that almost always shows up on the GATE Computer Science paper, either as a one-mark "count the minimum states" question or as a two-mark trace.

Definition: A DFA (Deterministic Finite Automaton) is minimal when no smaller DFA accepts the same language. The minimal DFA is unique up to isomorphism — every correct minimization procedure must arrive at the same number of states.

Definition: Two states p and q are equivalent if, for every input string w, δ*(p, w) is accepting exactly when δ*(q, w) is accepting. Equivalent states can be merged.

The four-step recipe

The table-filling algorithm is essentially a marking game on a triangular table of state pairs. You progressively mark pairs that you can prove are distinguishable until no new marks appear. Whatever is still unmarked is equivalent and gets merged.

Step 1 — Remove unreachable states. Start from the start state, do a BFS or DFS through δ, and discard any state that is not reachable. This must be the very first step. If you skip it, your final count will be wrong and you may even merge an unreachable state with a useful one. GATE examiners love this trap — they hand you a DFA with a stray unreachable trap state to see if you remember.

Step 2 — Initialise the table. For every unordered pair (p, q) of distinct states, look at whether exactly one of the two is a final state. If yes, mark that pair: they are clearly distinguishable, because the empty string ε already distinguishes them (one accepts, the other does not). If both are final or both are non-final, leave the pair unmarked for now.

Step 3 — Repeat the refinement. Scan every still-unmarked pair (p, q). For each input symbol a in the alphabet Σ, compute δ(p, a) and δ(q, a). If the pair (δ(p, a), δ(q, a)) is already marked, then (p, q) is also distinguishable — the string a followed by whatever distinguishes the successors will distinguish p and q. Mark (p, q). Repeat the whole scan until a full pass adds no new marks. This fixed-point condition is when the algorithm halts.

Step 4 — Merge. Every pair that is still unmarked when the algorithm stops is equivalent. Pool equivalent states into single classes. The number of classes is the number of states in the minimal DFA. Build the transition function on classes using any representative member.

Why the procedure works

The marking propagates an idea backwards in time. Step 2 marks pairs distinguished by the empty string (length 0). Each refinement pass extends the marking to pairs distinguished by strings of one more character: if (δ(p, a), δ(q, a)) is distinguished by some string x of length k, then (p, q) is distinguished by the string ax of length k + 1. Because there are only finitely many pairs, the process must terminate — at most about n² rounds for n states. What remains unmarked are pairs that no string can distinguish, exactly the definition of equivalent states.

This idea is the constructive face of the Myhill-Nerode theorem, which proves that the minimum number of DFA states equals the number of equivalence classes of the language under the relation "two strings are equivalent if they extend the same way".

Hopcroft's optimisation

The naive table-filling runs in O(n² · |Σ|) per pass, with up to O(n²) passes. Hopcroft's algorithm is a smarter partition-refinement variant that uses worklists and the "process the smaller half" trick to drop the running time to O(n log n · |Σ|), where n is the number of states and |Σ| is the size of the alphabet. Hopcroft's bound is what makes DFA minimization practical in compiler-grade lexical analyzers like flex.

Why it matters

Minimisation is not academic. Every compiler converts regular expressions for tokens into NFAs, then to DFAs, and then minimises the DFA before generating code. A bigger DFA means slower scanning and a larger compiler binary. Network packet matchers, antivirus signature scanners, and the regex engines of grep and Java's java.util.regex all minimise their DFAs for speed. On GATE, you are expected to apply the recipe by hand on small DFAs (4 to 8 states), so practice the table format on paper.

Worked example

Question: Minimise the following DFA with states {A, B, C, D, E}, alphabet {0, 1}, start state A, final states {C, E}, and transitions:
δ(A, 0) = B, δ(A, 1) = C
δ(B, 0) = A, δ(B, 1) = D
δ(C, 0) = E, δ(C, 1) = F-style... assume δ(C, 0) = E, δ(C, 1) = C
δ(D, 0) = E, δ(D, 1) = C
δ(E, 0) = E, δ(E, 1) = C

Solution:
Step 1: Check reachability from A. A → {B, C}; B → {A, D}; C → {E, C}; D → {E, C}; E → {E, C}. All five states are reachable.
Step 2: Initial marking — pairs (final, non-final) get marked. Finals are {C, E}, non-finals {A, B, D}. Mark (A,C), (A,E), (B,C), (B,E), (D,C), (D,E). Leave (A,B), (A,D), (B,D), (C,E) unmarked.
Step 3: Refinement pass on the unmarked pairs.

• (A, B): on 0, (B, A) unmarked; on 1, (C, D) marked. So mark (A, B).
• (A, D): on 0, (B, E) marked. Mark (A, D).
• (B, D): on 0, (A, E) marked. Mark (B, D).
• (C, E): on 0, (E, E) same state, ignore; on 1, (C, C) same state, ignore. No mark; still unmarked.
  Next pass: nothing new.
  Step 4: The only unmarked pair is (C, E). Merge C and E into one class, say [CE]. Classes: {A}, {B}, {D}, {CE}.
  Conclusion: Minimal DFA has 4 states, down from 5.

Common misconception

The most punishing mistake is skipping Step 1 — removing unreachable states. The marking phase will still terminate, but you may merge an unreachable junk state with a useful one and finish with the wrong count. Always pencil in "reachable: yes/no" beside every state before you start the table.

A second misconception is treating "both final" or "both non-final" pairs as equivalent. They are only possibly equivalent — you have to wait for the refinement passes to confirm. A pair can pass the initial check and still be distinguished later by some longer string.

A third trap: the minimal DFA being unique up to isomorphism. Some students worry that two different orderings of the algorithm give different DFAs. They cannot. The class structure is canonical — only the state names differ.

:::compare

:::keypoints

• The minimal DFA for a language is unique up to isomorphism.
• Always delete unreachable states first.
• Initial marking: every pair with exactly one final state is distinguishable.
• Refinement marks (p, q) whenever some symbol a sends them to an already-marked pair.
• Iterate to a fixed point; whatever stays unmarked is equivalent.
• Equivalent states merge; classes are the new states.
• Hopcroft's algorithm runs in O(n log n · |Σ|).
• This is the constructive form of the Myhill-Nerode theorem.
  :::

:::memory
"Reach → Final-split → Propagate → Merge" — four words for the four steps. Or: "Throw out the trash, split good vs bad, push distinguishability back through δ, fuse what stayed quiet."
:::

:::recap

• Table-filling minimises a DFA by progressively marking distinguishable pairs.
• Step 1 (remove unreachable) is non-negotiable; everything after fails without it.
• Unmarked pairs at the fixed point are equivalent and get merged.
• Hopcroft brings the running time down to O(n log n · |Σ|).
  :::

Consider strings a^0, a^1, a^2, … For any i ≠ j, take suffix z = b^i. Then a^i b^i ∈ L but a^j b^i ∉ L, so a^i and a^j are distinguishable. Thus there are infinitely many ≡_L classes ⟹ by Myhill-Nerode L = {a^n b^n} is NOT regular — no finite DFA exists. The same suffix-distinguishing trick proves {ww}, {a^n b^n c^n}, and {palindromes} non-regular. Memory aid: pick an infinite family of prefixes, find one suffix per pair that separates them. Contrast with the pumping lemma, which only gives a necessary (not sufficient) condition.

If you have practised IBPS PO syllogisms for even a week, you have noticed that one specific answer choice traps thousands of candidates: "Either I or II follows." Half the test-takers mark "Neither follows", the other half pick one of the two conclusions, and only the well-trained few recognise the complementary pair sitting in plain sight. Learn this single pattern and you will pick up easy marks that decide PO cut-offs.

Definition: A syllogism is a logical argument with two or more premises (statements) followed by conclusions; you must decide which conclusion definitely follows from the given statements assumed to be true.

Definition: An "Either-Or" case in syllogisms occurs when neither conclusion individually follows from the premises, but together the two conclusions cover every possible logical situation — so at least one of them must be true.

Definition: A complementary pair is a pair of conclusions with the same subject and same predicate whose quantifiers form an I-E or A-O contradiction — typically "Some A are B" and "No A is B", which between them exhaust all possibilities.

The Statements and Conclusions

Question:

Statements:

1. All cars are vehicles.
2. Some vehicles are red.

Conclusions:
I. Some cars are red.
II. No car is red.

Find: which conclusion(s) follow?

Step-by-Step Solution

Solution:

Step 1: Test each conclusion individually using Venn diagrams.

Draw circles. "All cars are vehicles" means the cars circle is fully inside the vehicles circle. "Some vehicles are red" means the red circle overlaps the vehicles circle — but where exactly inside? It could overlap with the cars portion, or only with the non-car portion of vehicles, or partially both. Both layouts are valid for the premises.

So the red region might touch cars (case A) or might miss cars entirely (case B). Premises do not force either case.

• Conclusion I: "Some cars are red." In case A, it is true. In case B, it is false. Hence I is only possible, not certain. I does not definitely follow.
• Conclusion II: "No car is red." In case B, it is true. In case A, it is false. Hence II is only possible, not certain. II does not definitely follow.

If a candidate stops here, they will mark "Neither follows" — and lose the mark.

Step 2: Now run the complementary-pair test. This is the IBPS PO trick. Check three boxes:

(a) Same subject? Conclusion I subject = "cars". Conclusion II subject = "car". Yes, same.
(b) Same predicate? Both end in "red". Yes, same.
(c) Do the quantifiers form an I–E pair (or A–O pair)? "Some X are Y" (Type I) vs "No X is Y" (Type E). Yes, classical complementary pair.

All three boxes are ticked. The two conclusions together cover every logical possibility — either some cars share something with red, or no car shares anything with red. There is no third option.

Step 3: Conclude. Because the conclusions are complementary, at least one must be true — even though we cannot say which one. The exact answer label IBPS uses for this situation is:

"Either Conclusion I or Conclusion II follows."

Conclusion: The right option is "Either I or II follows".

The Three-Condition Checklist (Memorise Word-for-Word)

For "Either-Or" to apply, all three of the following must be true:

:::compare

If even one condition fails — say the subjects are different, or one conclusion definitely follows — the "Either-Or" answer is wrong.

Why This Pattern Matters So Much in IBPS PO

Why it matters: an analysis of the last five years of IBPS PO Prelims reasoning sections shows that an Either-Or item appears in roughly every other set of 3–5 syllogism questions. Examiners use it as the differentiator between candidates who memorised "All A is B, Some B is C" tricks and those who actually understand the logic. PO cut-offs in 2022 and 2023 were decided by margins of half a mark to a single mark — exactly the weight of one syllogism trap.

Real-world example: in the IBPS PO Prelims 2022 (Slot 2), a syllogism set contained the premise pair "All offices are buildings. Some buildings are tall." with conclusions "Some offices are tall" and "No office is tall." Identical structure to our worked example. Candidates who reflexively marked "Neither follows" left a guaranteed mark on the table.

Common misconception: many students assume that if neither conclusion follows individually, the answer must be "Neither follows". That assumption is wrong. "Neither follows" is correct only when the two conclusions are NOT complementary — i.e., when there is a logical case where both could be false simultaneously. Whenever two conclusions are complementary, at least one of them must be true, even if you can't say which, and the answer flips to "Either-Or".

Another common misconception: thinking that "Some cars are red" and "Some cars are not red" form an Either-Or pair. They look like opposites but they are not exhaustive in the classical syllogism scheme — both can be true at the same time. The valid complementary pair is the I-E type (Some X are Y / No X is Y) or the A-O type (All X are Y / Some X are not Y).

A Quick Drill

Test yourself: Statements — "All pens are pencils. Some pencils are erasers." Conclusions — I. "Some pens are erasers." II. "No pen is an eraser." Run the three-condition checklist. Same subject (pens / pen)? Yes. Same predicate (erasers)? Yes. I–E pair? Yes. Do either individually follow? No, both are only possible. Answer: Either I or II follows. You will see this exact structure five times in any decent IBPS PO mock.

Now a contrast drill: Statements — "Some books are red. All red things are bright." Conclusions — I. "Some books are bright." II. "Some bright things are books." Both conclusions actually do follow individually (you can verify with a Venn diagram). So even though the conclusions share words, the Either-Or label does NOT apply — the correct answer is "Both I and II follow". The lesson: the Either-Or rule is triggered only when neither follows individually but together they cover all cases.

:::keypoints

• "Either I or II follows" is a high-frequency IBPS PO answer that thousands of aspirants miss.
• Trigger only when (a) neither conclusion individually follows, (b) same subject, (c) same predicate, and (d) quantifiers form an I–E or A–O complementary pair.
• I–E pair: "Some X are Y" and "No X is Y".
• A–O pair: "All X are Y" and "Some X are not Y".
• If even one trigger fails, the answer is not Either-Or — usually it is "Neither follows" or one of the conclusions individually follows.
• Always check Either-Or after you find that neither conclusion follows individually — never as your first move.
• The pattern shows up in roughly half of all IBPS PO syllogism sets — practise enough Venn-diagram work to spot it in under 30 seconds.
  :::

:::memory
Three-step gate: "Neither alone? Same subject-predicate? Complementary quantifiers? — Then Either-Or." Or as one phrase: NSC → Either-Or (Neither alone, Same words, Complementary quantifier).
:::

:::recap

• "Either I or II" applies only when neither conclusion follows alone, but together they exhaust all cases.
• The classic triggers are Some / No (I–E) and All / Some-not (A–O) over the same subject and predicate.
• Confusing this pattern with "Neither follows" is the most common reasoning blunder in IBPS PO Prelims.
• Master the three-condition checklist and you will never miss this mark.
  :::

Regular languages are the simplest class in the Chomsky hierarchy, but they are also the most robust. Apply almost any "sensible" operation to a regular language and the result is still regular. This robustness is captured by a list of closure properties that every GATE CSE aspirant must memorise — and, more importantly, must know how to weaponise in proofs.

Definition: A class of languages is closed under an operation if, whenever the operation is applied to languages from that class, the result is again a language in that class. For regular languages, the operations preserve "regularity": you start with regular, you end with regular.

Definition: A regular language is any language that is accepted by some finite automaton (DFA or NFA), equivalently described by a regular expression or a left-linear / right-linear grammar.

The full closure table

Regular languages are closed under all of the following operations:

• Union (L₁ ∪ L₂)
• Intersection (L₁ ∩ L₂)
• Complement (L̄ over a fixed alphabet Σ)
• Concatenation (L₁ · L₂)
• Kleene star (L*)
• Kleene plus (L⁺)
• Reversal (L^R = { w^R : w ∈ L })
• Difference (L₁ − L₂ = L₁ ∩ L̄₂)
• Symmetric difference
• Homomorphism and inverse homomorphism
• Prefix, suffix, substring closures
• Quotient (L₁ / L₂)
• Init / Final / Subword operations

Regular languages are NOT closed under:

• Infinite union (the union of regular {aⁿbⁿ} for each n is L = {aⁿbⁿ : n ≥ 0}, which is not regular even though each member is)
• Infinite intersection

That is essentially the entire closure landscape for regular languages. Think of it as a fortress — you can hammer regular languages with almost any boolean or rational operation and they bounce back as regular.

Why each closure works — the constructions

Union: Given DFAs M₁ and M₂, build an NFA with a new start state and ε-transitions to the start states of M₁ and M₂. Accept if either machine accepts. NFA → DFA gives a regular language.

Intersection: Use the product construction. The states of the new DFA are pairs (q₁, q₂) where q₁ ∈ Q₁ and q₂ ∈ Q₂. Transitions are componentwise: δ((q₁, q₂), a) = (δ₁(q₁, a), δ₂(q₂, a)). Final states are pairs (f₁, f₂) where both components are accepting. The product machine has |Q₁| × |Q₂| states.

Complement: Take a complete DFA for L (every transition defined). Swap final and non-final states. The new DFA accepts exactly Σ* − L. This trick fails if the DFA is incomplete — you must add a dead state first.

Concatenation and Kleene star: Straightforward NFA constructions using ε-transitions, mirroring the inductive definition of regular expressions.

Reversal: Reverse all transitions, swap start and accepting states (after adding a single new start state with ε-edges). The result is an NFA accepting L^R.

Difference: L₁ − L₂ = L₁ ∩ L̄₂. Both intersection and complement are closed, so difference is closed by composition.

Homomorphism: A homomorphism h: Σ* → Γ* maps each symbol to a string. Given a DFA for L, replace each transition labelled a with one labelled h(a). Inverse homomorphism is even cleaner: keep the same DFA but read input through h.

The most useful trick: contrapositive closure

Here is the proof technique that GATE problems repeatedly exploit:

If L₁ is regular and L₁ ∩ L₂ is not regular, then L₂ must be non-regular — because regular ∩ regular would necessarily be regular.

Worked use: Show that L = {w ∈ {a, b}* : the number of a's = number of b's} is not regular. Intersect L with the regular language ab (clearly regular). The intersection is {aⁿbⁿ : n ≥ 0}, which is the classic non-regular language. Since the intersection is non-regular and ab is regular, L itself cannot be regular. We bypassed the pumping lemma entirely.

This same trick — intersect with a regular "selector" language — converts many pumping-lemma proofs into one-line arguments. Add reversal, homomorphism and quotient to your toolkit and a large fraction of non-regularity proofs become trivial.

Why it matters: GATE CSE and BARC, ISRO and PSU exams ask closure-property questions every year. They appear in two flavours: (1) "Which of the following is regular?" — answered by closure composition; (2) "Prove L is non-regular" — answered by intersecting with a regular language to expose a known non-regular core. Closure properties also justify the algorithms of compilers and text-processing tools (grep, lex, ANTLR's lexer): every operation a tokeniser performs on regular expressions yields another regular expression.

Real-world example: Consider a regex used in the Aadhaar OTP service to validate phone numbers: ^[6-9][0-9]{9}$. Suppose security wants only those numbers that also match a Maharashtra-circle prefix pattern. The intersection of two regular languages is regular, so the combined check still compiles to a finite-state matcher — fast and memory-bounded, no PDA needed. Closure under intersection is what makes such composition cheap.

Common misconception: "Closure under union implies closure under infinite union." It does not. Each finite union of regular languages is regular, but infinite unions can construct any recursively enumerable language. The classical counterexample is L_n = {aⁿbⁿ} (regular, in fact finite!) — the union over all n gives {aⁿbⁿ : n ≥ 0}, which is famously non-regular.

Question: Suppose L₁ is regular and L₂ is not regular. Which of the following is/are guaranteed to be non-regular?
(a) L₁ ∪ L₂
(b) L₁ ∩ L₂
(c) L̄₁ ∪ L₂
(d) L₁ · L₂

Solution:
Step 1: For (a): pick L₁ = Σ*, L₂ = anything non-regular. Then L₁ ∪ L₂ = Σ* is regular — so (a) is not guaranteed.
Step 2: For (b): pick L₁ = Σ*, L₂ non-regular. Then L₁ ∩ L₂ = L₂ which is non-regular. But pick L₁ = ∅ and the intersection is ∅, regular — so (b) is also not guaranteed.
Step 3: For (c): same kind of counterexample as (a) — not guaranteed.
Step 4: For (d): pick L₁ = ∅; then L₁ · L₂ = ∅, regular. So (d) is not guaranteed.
Conclusion: None of the options is guaranteed. The only safe rule is the contrapositive: if a regular operation yields a non-regular result, the other operand must be non-regular. The presence of a non-regular language alone is not enough.

:::compare

:::keypoints

• Regular languages are closed under all standard boolean and rational operations.
• They are not closed under infinite union or infinite intersection.
• Complement requires a complete DFA before flipping final states.
• Intersection uses the product construction with |Q₁| × |Q₂| states.
• Reversal preserves regularity — useful for proving palindromes are not regular.
• Contrapositive trick: regular ∩ X non-regular ⇒ X non-regular.
• Closure-by-composition: difference, symmetric difference, prefix etc. follow from basic closures.
  :::

:::memory
"Regular is a fortress — closed under every standard boolean and rational operation, breached only by infinity." Anchor: U, I, C, C, S, R, D, H — Union, Intersection, Complement, Concatenation, Star, Reversal, Difference, Homomorphism — all yes; only infinite operations break in.
:::

:::recap

• Regular languages are closed under union, intersection, complement, concatenation, star, reversal, difference and homomorphism (and their compositions).
• They are not closed under infinite union or infinite intersection.
• Contrapositive intersection is the fastest way to prove non-regularity for many problems.
• Each closure is supported by an explicit DFA/NFA construction worth memorising for GATE.
  :::

The language L = {0ⁿ1ⁿ : n ≥ 0} is the textbook witness used to prove that finite automata genuinely have limited memory. If you understand exactly why no DFA, NFA or regular expression can ever recognise it, you have understood the deepest single idea in regular-language theory.

Definition: The Pumping Lemma for Regular Languages states that for every regular language L, there exists a constant p ≥ 1 (the pumping length) such that any string w ∈ L with |w| ≥ p can be split as w = xyz satisfying three conditions: (i) |xy| ≤ p, (ii) |y| ≥ 1, and (iii) for every i ≥ 0, xyⁱz ∈ L.

Definition: A language is non-regular if no DFA (equivalently, no NFA and no regular expression) accepts exactly that set of strings. To prove non-regularity, we typically use the Pumping Lemma as a contradiction tool.

The intuition first — why 0ⁿ1ⁿ is "too hard" for a DFA

A DFA has a fixed, finite number of states. As it reads input symbols from left to right, the only memory it has is the identity of its current state. To accept exactly those strings of the form 0ⁿ1ⁿ, a machine would need, after reading the block of 0s, to remember how many 0s it has seen so that it can later require exactly that many 1s. But n can be arbitrarily large, while the number of states is fixed. By the pigeonhole principle, two different counts of 0s must eventually land the DFA in the same state, after which it cannot tell them apart — and so it must wrongly accept some 0ᵃ1ᵇ with a ≠ b. This is the heart of the argument. The Pumping Lemma is the formal scaffolding around this pigeonhole intuition.

The proof by contradiction

We use the Pumping Lemma as a "no" detector. The strategy is fixed and worth memorising as a five-line ritual:

1. Assume L is regular.
2. Then there exists a pumping length p.
3. Choose a clever string w ∈ L with |w| ≥ p — clever means the constraint |xy| ≤ p forces y into a fragile part of the string.
4. Examine every legal split xyz; show that for some i ≥ 0, xyⁱz ∉ L.
5. Contradiction ⇒ assumption fails ⇒ L is not regular.

For our L = {0ⁿ1ⁿ : n ≥ 0}:

Step 1 — Assume L is regular. Let p be the pumping length.

Step 2 — Choose w = 0ᵖ1ᵖ. Note |w| = 2p ≥ p, so the lemma applies and w ∈ L (it has exactly p zeros followed by exactly p ones).

Step 3 — Consider any split w = xyz with |xy| ≤ p and |y| ≥ 1. Since |xy| ≤ p, the prefix xy lies entirely inside the first p characters of w, which are all 0s. So x and y consist only of 0s. Write y = 0ᵏ with k ≥ 1.

Step 4 — Pump with i = 2. Then xy²z = x · yy · z. Compared to xyz, we have inserted one extra copy of y, that is, an extra block of k zeros. So the pumped string equals 0^(p+k) 1ᵖ. This string has more 0s than 1s, hence it is not of the form 0ⁿ1ⁿ. Therefore xy²z ∉ L.

Step 5 — This contradicts the lemma's promise that xyⁱz ∈ L for every i ≥ 0. The assumption that L is regular must be false. Hence L is not regular. ∎

Why the choice of w is everything

The Pumping Lemma is an "adversary game": we choose w, the adversary chooses the split. So we must pick w so cleverly that no matter how the adversary splits it, we can still win by choosing a bad i. The trick used above — pushing the constrained region |xy| ≤ p entirely into one type of symbol — is the canonical technique.

If you had chosen, say, **w = 0¹1¹ · 0¹1¹ … ** something interleaved, the adversary could put y across the boundary and you would not get a clean count violation. The standard recipe is: make the first p characters be a single "uniform" run so the adversary is forced to put y inside that uniform run.

Pumping down also works

The lemma's "for every i ≥ 0" includes i = 0, which is called pumping down (deleting the y block). With y = 0ᵏ, the string xy⁰z = xz = 0^(p − k) 1ᵖ, again with more 1s than 0s (since k ≥ 1), so again not in L. Either i = 0 or i = 2 finishes the proof. Some examiners prefer i = 2 because it is conceptually "growing" rather than "shrinking"; the answer key accepts both.

Why it matters

Why it matters: GATE-CS routinely tests recognition of non-regularity. Languages such as {aⁿbⁿ}, {ww}, {aⁿbⁿcⁿ}, {1ⁿ² : n ≥ 0} and {strings of balanced parentheses} are all non-regular for essentially the same reason — they require unbounded counting or comparison, while a DFA has only finite memory. Mastering the 0ⁿ1ⁿ argument gives you a template you can adapt in three minutes during the exam.

Real-world example: A compiler that has to match opening and closing braces in nested code cannot use only regular expressions to do the matching — the language of balanced braces is non-regular by the same argument. That is precisely why parsers move beyond regular grammars to context-free grammars and use stacks (pushdown automata), which can remember the count.

Common misconception: Many students believe the Pumping Lemma can be used to prove a language is regular. It cannot. The lemma is a necessary but not sufficient condition for regularity — there exist non-regular languages that satisfy the pumping condition vacuously (these are detected using stronger tools like the Myhill–Nerode theorem). The lemma is only a one-way weapon: it can prove non-regularity, never regularity.

A second, fully laid out worked example

Question: Prove that L' = {aⁿbⁿ : n ≥ 1} is not regular using the Pumping Lemma.

Solution:
Step 1: Assume L' is regular with pumping length p.
Step 2: Choose w = aᵖbᵖ ∈ L' with |w| = 2p ≥ p.
Step 3: Any split w = xyz with |xy| ≤ p forces y to be aᵏ, k ≥ 1.
Step 4: Pump i = 2: xy²z = aᵖ⁺ᵏbᵖ, which has more a's than b's, so it is not in L'.
Conclusion: Contradiction; therefore L' is not regular.

The structure is byte-for-byte identical to the 0ⁿ1ⁿ proof. That is the point: one template, many languages.

:::compare

:::keypoints

• The Pumping Lemma gives a necessary condition for regularity — useful only for proving non-regularity.
• For {0ⁿ1ⁿ}, choosing w = 0ᵖ1ᵖ and using |xy| ≤ p forces y to be inside the 0-block.
• Pumping y up (i = 2) or down (i = 0) breaks the 0-count vs 1-count balance.
• The deep reason: a DFA has only finite memory; counting unbounded n requires infinite memory.
• The technique generalises to {aⁿbⁿ}, {aⁿbⁿcⁿ}, balanced parentheses, palindromes over Σ ≥ 2, etc.
• The lemma cannot prove a language is regular; pumping-condition is not sufficient.
• For GATE, always state the five-line ritual: Assume, Choose, Split, Pump, Contradict.
  :::

:::memory
"A-C-S-P-C" — Assume regular, Choose clever w, Split xyz, Pump with bad i, Contradict. Memorise this acronym and you will never forget the proof structure under time pressure.
:::

:::recap

• L = {0ⁿ1ⁿ} is the canonical non-regular language.
• Pick w = 0ᵖ1ᵖ; the constraint |xy| ≤ p forces y to lie inside the 0s.
• Pumping y (i = 2 or i = 0) produces a string outside L, giving the required contradiction.
• The same five-step template proves non-regularity for an entire family of "counting" languages.
  :::