Theory of Computation — CS3103-1 Unit-I (Animated)

01Central Concepts — Alphabet, String, Language

An alphabet Σ is a finite set of symbols. A string is a finite sequence of symbols. A language is a set of strings over Σ. Automata are machines that decide membership in a language.

Three symbols that trip everyone up

Symbol	What it is	Cardinality
∅	The empty set — a language with no strings	0 strings
ε	The empty string — a string of length 0	1 string
{ε}	The language containing the empty string	1 string

⚠ Common mistake ∅ is not the same as {ε}. ∅ has nothing in it; {ε} has one string, the empty string. And ε is not a symbol of the alphabet — it's the identity under concatenation: εw = wε = w.

✓ Notations to know |w| = length of w · w^k = w repeated k times · Σ^* = all strings over Σ (including ε) · Σ⁺ = Σ^* − {ε} · w^R = reversal.

02Deterministic Finite Automata (DFA)

A DFA = 5-tuple (Q, Σ, δ, q₀, F): states, alphabet, transition function, start state, accept states. Deterministic = exactly one move per input symbol — the machine can never be in two states at once.

✓ The 5-tuple for "ends in 01" Q = {A, B, C} · Σ = {0, 1} · q₀ = A · F = {C} · δ = {A·0→B, A·1→A, B·0→B, B·1→C, C·0→B, C·1→A}.

Four designs, one recipe (design → draw → test)

Ends with 01

A = nothing useful yet · B = last symbol was 0 · C = just read 01 (accept). On 0 from C, go back to B (the "0" might start a new 01).

Starts with 01

After the first char goes wrong, jump to a dead state q_d that eats everything. A dead state is not accepting and has no way out.

Even zeros AND even ones

Track parity of each count in the state itself: EE, OE, EO, OO. A 0 flips the first letter, a 1 flips the second.

Binary numbers divisible by 3

State = current remainder. Reading bit b: new = (2·old + b) mod 3. Accept only state 0. Try 10110 (=22, remainder 1 → reject).

⚠ Common mistake A dead state is not a "trap that accepts" — a dead state rejects (not in F) and loops on itself forever. "Trap" sometimes means dead; always check whether F includes it.

03Nondeterministic Finite Automata (NFA)

An NFA may have zero, one, or many moves for a given symbol. It accepts if any path ends in an accept state. Conceptually it explores all paths in parallel — the active state is a set.

NFA for "ends in 01" — multiple states light up at once↻ reset

q₀ loops on 0 and 1; on 0 it may also move to q₁. If we're in q₁ and read 1, we reach q₂ — accept! The whole string is accepted if the active set ever contains q₂ after the last symbol.

Subset construction — NFA → DFA, one set becomes one DFA state

DFA state (subset)	on 0	on 1	accept?
A = {q₀}	{q₀,q₁} = B	{q₀} = A	no
B = {q₀,q₁}	{q₀,q₁} = B	{q₀,q₂} = C	no
C = {q₀,q₂}	{q₀,q₁} = B	{q₀} = A	yes (q₂ ∈ C)

The DFA you get is exactly the "ends in 01" machine from section 2 — every NFA has an equivalent DFA, so the two formalisms recognise the same class: the regular languages.

04ε-NFA — Free Moves

An ε-NFA adds ε-transitions: moves you can take for free, without consuming any input. The machine can always be in the ε-closure of its current state set.

ε-closure in action — language a*b ("any number of a's, then a b")↻ reset

Before reading anything, ε-closure(q₀) = {q₀, q₁}. On 'a' we stay, on 'b' we must be in q₁ (accept) — so a*b is recognised.

✓ How to compute ε-closure ε-closure(S) = start with S; repeatedly add every state reachable by one ε-move; repeat until nothing new. Then, to move on symbol a: collect all a-transitions from states in the closure, and take the ε-closure of that result.

05Regular Expressions — and the bridge to Automata

Regular expressions are a notation for regular languages. Kleene's theorem: something is regular iff it can be described by a regex — and every regex can be mechanically converted into an NFA (Thompson's construction), and vice-versa.

Identity laws (memorise — exam gold)

∅R = R∅ = ∅	R + ∅ = R	εR = Rε = R
R + R = R	RR = R*	(R) = R*
RR* = R*R = R⁺	∅* = ε	ε* = ε
R + R* = R*	(R₁R₂)R₁ = R₁(R₂R₁)	(R₁+R₂)* = (R₁R₂)*

Patterns → regexes

Language	Regex
ends in 01	(0+1)*01
starts with 1	1(0+1)*
exactly two 0s	10 10 1*
even number of 0s	(1010)* 1*
no two 1s together	(0+10)*(ε+1)
contains 010	(0+1)010(0+1)

Regexes → patterns

Regex	Language (words of length ≤ 2)
010	{10, 010, 100, 0100, …} — exactly one 1
(00)*	{ε, 00, 0000, …} — even-length all-zeros
(0+1)01	{001, 101}
0+1	{ε, 0, 00, 1, 11, …} — all 0s OR all 1s

✦ Exam point Operator precedence in regexes: * > concatenation > +. So 0+10 means (0) or (10), not (0+1)0. Always bracket carefully!

06Thompson's Construction — Regex → NFA, built from 3 pieces

Every regex is assembled from tiny NFAs with a union (parallel), concat (series), and star (loop) gadget. Building (0+1)*01 uses all three.

Construction sequence — press play and watch the parts connect↻ replay

① build 0-NFA and 1-NFA → ② merge into (0+1) with new ε start → ③ wrap in * → ④ concatenate 0 then 1 → final NFA for (0+1)*01.

✓ The full NFA for (0+1)*01 New start s: s →ε→ 0-fragment and 1-fragment, both ε-loop back to s (the star). Then ε→ concatenated 0 → 1 → accept. This NFA has 15 states and accepts exactly the strings ending in 01.

07Pumping Lemma — Proving a Language is NOT Regular

The pump lemma says: in any regular language, sufficiently long strings can be pumped — a middle part repeats, and the result is still in the language. To prove non-regularity, show a string that can't be pumped without breaking the language.

The lemma (memorise the 3 conditions)

If L is regular, ∃ pumping length n such that every w ∈ L with |w| ≥ n can be split w = xyz where: 1. |xy| ≤ n · 2. y ≠ ε · 3. xyⁱz ∈ L for all i ≥ 0.

Pumping { 0ⁿ1ⁿ } — the "loop" that ruins the equality↻ replay

w = 0³1³. The first n symbols are all 0s, so y sits inside the 0s. Pumping once more: more 0s than 1s → not in the language → contradiction.

✓ Proof 1 — L = {0ⁿ1ⁿ} is not regular Assume regular, pumping length n. Take w = 0ⁿ1ⁿ (|w| = 2n ≥ n). Split w = xyz with |xy| ≤ n, y ≠ ε. Then y is all 0s. Pump up: xy²z has more 0s than 1s → ∉ L. Contradiction. ∎

✓ Proof 2 — L = {w : equal 0s and 1s} via closure (shortcut) Regular languages are closed under intersection. If L were regular, then L ∩ 0*1* would be regular. But L ∩ 0*1* = {0ⁿ1ⁿ}, which proof 1 just showed is not regular. Contradiction. ∎

✓ Proof 3 — L = {0ⁱ1ʲ : i > j} (pump down) w = 0ⁿ⁺¹1ⁿ ∈ L. y is all 0s. Pump down: xy⁰z = xz loses ≥1 zero, so zeros ≤ ones → ∉ L. Contradiction. ∎

⚠ Common mistake The pumping lemma only proves languages are not regular. It cannot prove a language IS regular — for that, build a DFA/NFA/regex or use closure properties (union, concat, star, intersection, complement, reversal, homomorphism).

08Summary Sheet & 5 Near-Certain Questions

Concept	One-line truth
DFA	One state at a time; total, deterministic δ
NFA	Set of states; may have ε moves; accepted if any path accepts
NFA → DFA	Subset construction (2^\|Q\| states worst case)
Regex ↔ NFA	Thompson / Kleene; both describe exactly the regular languages
Closure	Regular languages close under ∪ · · * ∩ ¬ R homomorphism
Pumping	Proves non-regularity only

Q1 · Design a DFA for strings over {0,1} ending in 01 and write its 5-tuple.

Q={A,B,C}, Σ={0,1}, q₀=A, F={C}; δ: A·0→B, A·1→A, B·0→B, B·1→C, C·0→B, C·1→A.

Q2 · Convert NFA for (a+b)*abb to a DFA (first 3 subsets).

Start {q₀}: on a → {q₀,q₁}, on b → {q₀}. Then {q₀,q₁}: on a → {q₀,q₁}, on b → {q₀,q₂}… continue until no new subsets.

Q3 · Write a regex for "at least two consecutive 0s".

(0+1)*00(0+1)* — anywhere, two 0s in a row.

Q4 · Compute ε-closure({q₀}) for the a*b NFA.

Start {q₀}; q₀ has ε→q₁, so add q₁ → {q₀, q₁}.

Q5 · Prove {0ⁿ1ⁿ} is not regular.

Assume regular, take w=0ⁿ1ⁿ, y ⊂ 0's by |xy|≤n; pump xy²z → more 0s than 1s, contradiction.