Theory of Computation

0. What is Theory of Computation? EASY

🌍 Real World Analogy

TOC is basically asking: "What can a computer actually do? What are its limits?" Think of it like asking: "What can a human brain do, and what is impossible for it?" TOC answers this for machines.

TOC studies three big questions:

What problems CAN be solved by a computer? (Decidability)
How efficiently can they be solved? (Complexity)
What mathematical models describe computation? (Automata)

Key Terms — Plain English

Term	Plain English	Example
Alphabet (Σ)	Set of allowed symbols	Σ = {0,1} or {a,b,c}
String	Sequence of symbols from alphabet	"0101", "abc"
Language (L)	Set of strings (that follow some rule)	All strings starting with 'a'
ε (epsilon)	Empty string — has zero characters	Like an empty box
*Σ (sigma star)**	ALL possible strings over Σ including ε	All binary strings ever
Automaton	An abstract machine that reads input and decides	A traffic light controller

1. Chomsky Hierarchy ⭐ EXAM FAV

🌍 Analogy

Think of it like levels of brain power. A simple calculator (DFA) can only check patterns. A robot with a notebook (PDA) can do more. A full computer (TM) is the most powerful. Each higher level CONTAINS all lower levels.

Type 0 — Unrestricted Grammar → Turing Machine (most powerful)

Type 1 — Context-Sensitive Grammar → Linear Bounded Automaton

Type 2 — Context-Free Grammar (CFG) → Pushdown Automaton (PDA)

Type 3 — Regular Grammar → Finite Automaton (DFA/NFA) (simplest)

Type	Grammar	Machine	Example Language
Type 3	Regular	FA (DFA/NFA)	aⁿ, (a+b)*ab
Type 2	Context-Free	PDA	aⁿbⁿ
Type 1	Context-Sensitive	LBA	aⁿbⁿcⁿ
Type 0	Unrestricted	TM	Halting Problem

🧠 Memory Trick

"Regular Cooks Prepare Tasty"
R = Regular (Type 3) → C = Context-Free (Type 2) → P = Context-Sensitive (Type 1) → T = Turing (Type 0)
OR: Every Type 3 is Type 2, but NOT vice versa (like every square is a rectangle but not every rectangle is a square)

2. Deterministic Finite Automaton (DFA) ⭐ VERY IMP

🌍 Analogy — Turnstile at a metro

A metro turnstile is a DFA! It has 2 states: LOCKED and UNLOCKED.
Input coin → goes UNLOCKED. Push → goes LOCKED. That's it. Simple, deterministic, one step at a time.

Formal Definition

A DFA is a 5-tuple: M = (Q, Σ, δ, q₀, F)

Symbol	Meaning	Example
`Q`	Finite set of states	{q0, q1, q2}
`Σ`	Input alphabet	{0, 1}
`δ`	Transition function δ: Q × Σ → Q	δ(q0, 0) = q1
`q₀`	Start state (initial)	q0
`F`	Set of final/accepting states	{q2}

Key Rules of DFA

From every state, for every input symbol, there is exactly ONE transition (no choice, no missing)
A string is accepted if after reading all characters, we end in a state in F
A string is rejected if we end in a non-final state

Example — DFA accepting strings ending in '1'

Language: L = {w ∈ {0,1}* | w ends with 1}

States: q0 (start), q1 (final★) q0 --0--> q0 q0 --1--> q1 ← accepting state q1 --0--> q0 q1 --1--> q1 Reading "101": start: q0 read '1': q0 → q1 read '0': q1 → q0 read '1': q0 → q1 ← ends in q1 (final) ✓ ACCEPTED Reading "100": start: q0 read '1': q0 → q1 read '0': q1 → q0 read '0': q0 → q0 ← ends in q0 (not final) ✗ REJECTED

Transition Table (same example)

State	Input: 0	Input: 1
→q0 (start)	q0	q1
★q1 (final)	q0	q1

🧠 Exam Trick — Drawing DFA

Step 1: Figure out what "states" you need to REMEMBER while reading input.
Step 2: For "strings ending in X" → 2 states: "last was X" and "last was not X".
Step 3: For "exactly k occurrences" → need k+1 states (count 0 to k).
Step 4: Always add a dead/trap state if some transition is missing.

3. Non-Deterministic Finite Automaton (NFA) ⭐ VERY IMP

🌍 Analogy — Magic guessing machine

NFA is like a magic genie who always guesses the right path! When there's a choice, it splits into MULTIPLE copies of itself and explores ALL paths simultaneously. If ANY copy reaches a final state → ACCEPTED.

DFA vs NFA — Differences

Feature	DFA	NFA
Transitions per state	Exactly 1 per symbol	0, 1, or MORE per symbol
ε-transitions	Not allowed	Allowed (optional)
Transition function	δ: Q × Σ → Q	δ: Q × Σ → 2^Q (power set)
Acceptance	One path must end in F	ANY path ending in F
Power	Same as NFA!	Same as DFA!

⚡ KEY THEOREM

NFA and DFA are EQUIVALENT in power.
Every NFA can be converted to an equivalent DFA. They both accept exactly Regular Languages. NFA just makes it easier to design — DFA is easier to implement.

Example — NFA for strings ending in 'ab'

Σ = {a, b}, L = all strings ending with "ab" States: q0 (start), q1, q2 (final★) q0 --a--> {q0, q1} ← non-deterministic! Two choices on 'a' q0 --b--> {q0} q1 --b--> {q2} q2 --a--> {} ← no transition (dead) q2 --b--> {} Testing "aab": Start: {q0} Read 'a': {q0, q1} ← both copies alive Read 'a': {q0, q1} ← q0 reads 'a'→{q0,q1}, q1 reads 'a'→{} Read 'b': {q0, q2} ← q0 reads 'b'→{q0}, q1... wait q1 reads 'b'→{q2} Final set {q0, q2}: q2 ∈ F → ✓ ACCEPTED

4. ε-NFA (Epsilon-NFA) MEDIUM

🌍 Analogy — Free teleportation

ε-transitions are like free teleportation — you move to another state WITHOUT consuming any input. Like going through a door that costs nothing.

ε-Closure

ε-closure(q) = the set of ALL states reachable from q using ONLY ε-transitions (including q itself).

📝 Example

If q0 →ε→ q1 →ε→ q2, and q1 →ε→ q3, then:
ε-closure(q0) = {q0, q1, q2, q3}
ε-closure(q1) = {q1, q2, q3}
ε-closure(q2) = {q2}

How to process input in ε-NFA

Start with ε-closure(q₀)
For each input symbol a:
- Find all states reachable via a from current set
- Take ε-closure of that result
Accept if final set contains any state in F

🧠 Trick

ε-closure is like saying: "Wherever I am, I also teleport to all rooms connected by free doors." Always compute ε-closure FIRST (before reading input) and AFTER every transition.

5. NFA → DFA Conversion (Subset Construction) ⭐ MOST IMP

🌍 Analogy

In NFA, multiple copies run in parallel. Subset construction says: let's track ALL active copies as ONE combined state. So {q0, q1, q2} becomes a single DFA state called "q0q1q2".

Algorithm (Subset Construction)

Start state of DFA = ε-closure(q₀) of NFA
For each new DFA state (set of NFA states) and each input symbol:
- Find all NFA states reachable via that symbol from any state in the set
- Take ε-closure of the result → this is the new DFA state
A DFA state is final if it contains ANY NFA final state
Repeat until no new states

Full Worked Example

NFA over {a,b}: accepts strings ending in 'a'

NFA States: q0 (start), q1 (final)
δ_NFA:  q0 --a--> {q0, q1}
        q0 --b--> {q0}
        q1 --a--> {}
        q1 --b--> {}

Step 1: DFA start = {q0}

DFA State	On 'a'	On 'b'	Final?
→{q0}	{q0,q1}	{q0}	No (q1 not in {q0})
★{q0,q1}	{q0,q1}	{q0}	YES (q1 ∈ {q0,q1})

Only 2 DFA states needed! (often NFA→DFA can blow up to 2ⁿ states though)

⚠️ Exam Warning: In worst case, an NFA with n states needs 2ⁿ DFA states. But often the actual number is much less. Always check if some subsets are unreachable!

6. Minimization of DFA MEDIUM

🌍 Analogy — Merging duplicate rooms

If two rooms in a house behave EXACTLY the same way (same doors lead to same rooms), why keep both? Merge them! Minimization = removing redundant states.

Table Filling Algorithm (Myhill-Nerode)

Create a table with all pairs of states (qi, qj)
Mark all pairs where one is final and other is not → DISTINGUISHABLE
For each unmarked pair (qi, qj) and each symbol a:
- If δ(qi,a) and δ(qj,a) are already marked → mark (qi,qj)
Repeat until no new pairs can be marked
All UNMARKED pairs → merge those states

🧠 Quick Trick

Two states are equivalent (can be merged) if: starting from either state, reading ANY string always leads to accept/reject in the SAME way. States are distinguishable if there exists ANY string that causes different outcomes.

7. Regular Expressions ⭐ VERY IMP

🌍 Analogy — Like phone number format rules

A regular expression is like a pattern rule. "A valid Indian phone number starts with 6,7,8,9 followed by 9 digits" — that's a regex!

Basic Operators

Operator	Symbol	Meaning	Example
Union	a + b or a\|b	a OR b	(0+1) = {0,1}
Concatenation	ab	a followed by b	ab = {ab}
Kleene Star	a*	Zero or more a's	a* = {ε, a, aa, aaa,...}
Kleene Plus	a+	One or more a's	a+ = {a, aa, aaa,...}
Optional	a?	Zero or one a	a? = {ε, a}

Important Identities (Memorize!)

// These are guaranteed exam questions
ε*  = ε
∅*  = ε
a** = a*           (star is idempotent)
a+  = aa*  = a*a
a?  = (ε + a)
∅ · a = ∅          (nothing · anything = nothing)
ε · a = a           (empty concat = identity)
∅ + a = a           (union with empty language = a)
(a+b)* = (a*b*)*    (very common identity)

Common Language → Regex Patterns

Language Description	Regular Expression
Strings starting with a	a(a+b)*
Strings ending with b	(a+b)*b
Strings containing 'ab'	(a+b)ab(a+b)
Strings of even length	((a+b)(a+b))*
Strings with even no. of a's	(baba)b
All strings over {a,b}	(a+b)*
At least one 'a'	(a+b)a(a+b)
Exactly two a's	babab*

Arden's Theorem (for FA → Regex)

If R = Q + RP where P does not contain ε, then R = QP*

🧠 Arden's Trick

Think of it like algebra: R = Q + RP → subtract RP → R(1-P) = Q → R = Q/(1-P) = Q·P* (Since in languages, 1/(1-P) = P* by geometric series analogy!)

8. Regular Grammar MEDIUM

Types

Type	Rule Form	Example
Right Linear (RRG)	A → aB or A → a or A → ε	S → aS \| bS \| ε
Left Linear (LRG)	A → Ba or A → a or A → ε	S → Sa \| Sb \| ε

Key Fact

Both RRG and LRG generate Regular Languages. You can convert between them and DFA/NFA/Regex freely. But you CANNOT mix left and right in the same grammar (that breaks it).

9. Pumping Lemma for Regular Languages ⭐ EXAM FAVOURITE

🌍 Analogy — The rubber band test

If a language is regular, it's like a rubber band — you can stretch (pump) the middle part and the string should still be in the language. If stretching breaks the language → it's NOT regular!

The Lemma (Statement)

PUMPING LEMMA

If L is a regular language, then ∃ a pumping length p ≥ 1 such that
for every string w ∈ L with |w| ≥ p,
w can be split as w = xyz where:

1. |xy| ≤ p (xy is in first p characters)
2. |y| ≥ 1 (y is non-empty — this is what gets pumped)
3. ∀ i ≥ 0, xy^i z ∈ L (pumping any # of times keeps it in L)

How to PROVE a language is NOT regular (exam procedure)

PROOF TEMPLATE — Learn this by heart!

Assume L is regular. Then pumping length p exists.
Choose w = [pick a clever string in L, length ≥ p]. Usually: aᵖbᵖ, 0ᵖ1ᵖ etc.
Split w = xyz with |xy| ≤ p, |y| ≥ 1.
→ Since |xy| ≤ p, both x and y consist only of the first symbol!
→ y = aᵏ for some k ≥ 1
Pump: Let i = 0 or i = 2: xy⁰z or xy²z
Show contradiction: the pumped string is NOT in L.
Conclude: Contradiction! L is NOT regular. ■

Classic Example — aⁿbⁿ is NOT regular

📝 Full Proof

Assume L = {aⁿbⁿ | n ≥ 0} is regular. Let p be pumping length.
Choose w = aᵖbᵖ ∈ L, |w| = 2p ≥ p ✓
Split: w = xyz, |xy| ≤ p, |y| ≥ 1
→ Since |xy| ≤ p, x and y are entirely in the 'a' part
→ x = aˢ, y = aᵏ (k ≥ 1), z = aᵖ⁻ˢ⁻ᵏbᵖ
Pump i=0: xy⁰z = xz = aᵖ⁻ᵏbᵖ
This has fewer a's than b's → NOT in L ✗
Contradiction! L is NOT regular. ■

🧠 Trick — Choose w wisely!

For "aⁿbⁿ type" → choose w = aᵖbᵖ
For "equal symbols" → choose boundary where counts are equal
For primes → choose w = aᵖ where p is prime
Always pick w so that pumping y (which is in the first part) breaks the balance!

10. Closure Properties of Regular Languages MEDIUM

🌍 Analogy

"Closure" means: if I do this operation on regular languages, do I STAY in the regular language family? Like adding two even numbers always gives an even number — even numbers are "closed" under addition.

Operation	Closed?	Method
Union (L₁ ∪ L₂)	✅ YES	NFA construction or product automaton
Intersection (L₁ ∩ L₂)	✅ YES	Product automaton (both must accept)
Concatenation (L₁·L₂)	✅ YES	Connect final states of L₁ to start of L₂
Kleene Star (L*)	✅ YES	Add ε from final states back to start
Complement (L̄)	✅ YES	Swap final and non-final states in DFA
Difference (L₁ - L₂)	✅ YES	L₁ ∩ L₂̄
Reversal (Lᴿ)	✅ YES	Reverse all transitions
Homomorphism	✅ YES	Replace each symbol per function

🧠 Trick

Regular languages are closed under ALL standard operations. So if both L₁ and L₂ are regular, any combination of union, intersection, complement, concat, star → still regular!

11. Context-Free Grammar (CFG) ⭐ VERY IMP

🌍 Analogy — English grammar rules

English grammar says: Sentence → Noun Phrase + Verb Phrase. Noun Phrase → Article + Noun. CFG is exactly this! Rules that expand symbols into other symbols, until you get the actual string.

Formal Definition

CFG = (V, T, P, S) where:

Symbol	Meaning	Example
V	Variables (non-terminals), uppercase	{S, A, B}
T	Terminals (actual symbols), lowercase	{a, b}
P	Production rules A → α	S → aSb \| ε
S	Start symbol	S

Classic CFG Examples

Language: aⁿbⁿ (equal a's and b's)

S → aSb | ε
Derivation of "aabb":
S → aSb → aaSbb → aaεbb → aabb ✓

Language: Balanced Parentheses

S → SS | (S) | ε
"(())" : S → (S) → (SS) → ((S)S) → ((S)) → (()) → (())

Language: Palindromes over {a,b}

S → aSa | bSb | a | b | ε

Language: aⁿbᵐ where n ≠ m

S → AB | BA
A → aA | a        (generates aⁿ, n ≥ 1)
B → bB | b        (generates bᵐ, m ≥ 1)
... (more complex, needs careful construction)

Parse Trees and Derivations

Two Types of Derivation

Leftmost Derivation (LMD): Always expand the leftmost variable first.
Rightmost Derivation (RMD): Always expand the rightmost variable first.

A grammar is Ambiguous if a string has TWO different parse trees (or two different LMDs).

Ambiguous Grammar Example

G: E → E+E | E*E | id
String: id + id * id has TWO parse trees:
  Tree 1: (id + id) * id  → + is root
  Tree 2: id + (id * id)  → * is root  ← AMBIGUOUS!

12. Simplification of CFG MEDIUM

To simplify CFG, remove 4 types of useless things:

1. Useless Symbols

A symbol is useful if it: (a) can derive a terminal string, AND (b) is reachable from S.

2. ε-Productions (Remove Nullable Variables)

Find all nullable variables (A → ε directly, or A → B where B is nullable)
For every production with nullable var, add new production with that var removed
Remove all A → ε rules (except S → ε if ε ∈ L)

3. Unit Productions (A → B)

Find all unit pairs: (A,B) where A ⟹* B by unit steps
For each (A,B), add A → α for every B → α (non-unit)
Remove all unit rules

4. Order to Apply

🧠 Correct ORDER (very important for exams!)

Step 1: Remove ε-productions
Step 2: Remove unit productions
Step 3: Remove useless symbols
If done in wrong order, results may differ!

13. Normal Forms: CNF and GNF ⭐ EXAM IMP

Chomsky Normal Form (CNF)

CNF RULE

Every production must be EITHER:
• A → BC (two variables only)
• A → a (single terminal only)
• S → ε (only if ε ∈ L)

Converting to CNF — Algorithm

Remove ε-productions
Remove unit productions
Remove useless symbols
For any terminal 'a' in long rules: replace 'a' with new variable Tₐ, add Tₐ → a
Break rules with 3+ variables: A → BCD becomes A → BX, X → CD

📝 CNF Conversion Example

Original: S → aBC
Step 4: Replace 'a' → Tₐ: S → Tₐ BC, Tₐ → a
Step 5: 3 vars → Break: S → Tₐ X, X → BC, Tₐ → a  ← CNF! ✓

Greibach Normal Form (GNF)

GNF RULE

Every production: A → a α
where 'a' is a terminal and α is a (possibly empty) string of variables.
Every RHS starts with a terminal!

🧠 CNF vs GNF Memory Trick

CNF: "Two variables or One terminal" → C for "Couple or Singleton"
GNF: "Terminal FIRST, then variables" → G for "Go terminal first"

GNF is useful because: each step in derivation consumes exactly ONE terminal → useful for parsing proofs.

14. Pushdown Automaton (PDA) ⭐ VERY IMP

🌍 Analogy — FA with a stack of plates

PDA = NFA + a stack (like a pile of plates — you can only add/remove from the top). The stack gives it infinite memory, which is why it's more powerful than DFA. This is what allows it to match aⁿbⁿ — push n A's, then pop one for each b!

Formal Definition

PDA = (Q, Σ, Γ, δ, q₀, Z₀, F) where:

Symbol	Meaning
Q	Finite states
Σ	Input alphabet
Γ	Stack alphabet
δ	Transition: Q × (Σ∪{ε}) × Γ → 2^(Q×Γ*)
q₀	Start state
Z₀	Initial stack symbol (bottom marker)
F	Final states

Transition Notation

δ(q, a, X) = {(r, γ)} means: "In state q, reading input 'a', with 'X' on top of stack → go to state r, replace X with γ on stack"

Stack Operations

You write	Meaning
γ = ε	POP X from stack (replace with nothing)
γ = X	No change to stack (keep X)
γ = YX	PUSH Y (Y goes on top of X)
γ = Y	REPLACE X with Y

Two Acceptance Modes

Mode	Accept when...
By Final State	Input exhausted AND in final state (stack can have anything)
By Empty Stack	Input exhausted AND stack is empty (state doesn't matter)

Both modes are equivalent — you can convert between them!

PDA for aⁿbⁿ

States: q0 (start), q1, q2 (final)
Stack alphabet: {A, Z₀}

Phase 1 (reading a's): push A for each 'a'
  δ(q0, a, Z₀) = {(q0, AZ₀)}   ← first 'a': push A on Z₀
  δ(q0, a, A)  = {(q0, AA)}    ← each 'a': push A on A

Phase 2 (reading b's): pop A for each 'b'
  δ(q0, b, A)  = {(q1, ε)}     ← first 'b': pop A, go to q1
  δ(q1, b, A)  = {(q1, ε)}     ← each b: pop A
  δ(q1, ε, Z₀) = {(q2, Z₀)}   ← stack has only Z₀ → accept

Input "aabb":
  (q0, aabb, Z₀) → (q0, abb, AZ₀) → (q0, bb, AAZ₀)
  → (q1, b, AZ₀) → (q1, ε, Z₀) → (q2, ε, Z₀) ✓ ACCEPTED

🧠 PDA Design Strategy

For matching patterns (aⁿbⁿ): PUSH first type, POP on second type
For palindromes: PUSH first half, POP second half
For ww^R (reverse): same as palindrome
Non-determinism helps! You can guess the middle point.

15. Pumping Lemma for Context-Free Languages ⭐ IMP

CFL PUMPING LEMMA

If L is CFL, ∃ pumping length p ≥ 1 such that every w ∈ L with |w| ≥ p can be split as w = uvxyz where:
1. |vy| ≥ 1 (v or y is non-empty)
2. |vxy| ≤ p (middle part ≤ p)
3. ∀ i ≥ 0: uvⁱxyⁱz ∈ L (pump both v and y together)

🧠 Key Difference from RL Pumping Lemma

RL: w = xyz, pump y alone (one part)
CFL: w = uvxyz, pump v and y SIMULTANEOUSLY (two parts)
Think: CFL has a stack, so two things are being tracked!

Classic Example — aⁿbⁿcⁿ is NOT CFL

📝 Proof

Assume L = {aⁿbⁿcⁿ} is CFL. Let p be pumping length.
Choose w = aᵖbᵖcᵖ ∈ L
Split w = uvxyz, |vxy| ≤ p, |vy| ≥ 1
→ Since |vxy| ≤ p, vxy cannot span all three sections (a,b,c)
→ Case 1: v,y only in a's and b's. Pump i=2: more a's+b's but same c's → NOT in L ✗
→ Case 2: v,y only in b's and c's. Pump i=2: same a's but more b's+c's → NOT in L ✗
→ Case 3: v or y spans two symbol types (e.g., aᵏbʲ). Pump i=2: order violated → NOT in L ✗
All cases → contradiction! aⁿbⁿcⁿ is NOT CFL. ■

16. Turing Machine (TM) ⭐ MOST IMP

🌍 Analogy — The ultimate supercomputer on a tape

Imagine a robot with a pencil reading a tape of paper (infinite in both directions). It can: read the current symbol, write a new symbol, move left or right, change its internal state. That's a Turing Machine — the most powerful computer model possible!

Formal Definition

TM = (Q, Σ, Γ, δ, q₀, B, F) where:

Symbol	Meaning
Q	Finite states
Σ	Input alphabet (Σ ⊂ Γ)
Γ	Tape alphabet (includes blank B)
δ	δ: Q × Γ → Q × Γ × {L, R}
q₀	Start state
B	Blank symbol (represents empty tape)
F	Final/accepting states

Transition Meaning

δ(q, a) = (r, b, L) means: In state q, reading 'a' → go to state r, write 'b', move Left

Configuration (Instantaneous Description)

Written as: α q β where q = current state, α = tape left of head, β = tape at+right of head

TM for aⁿbⁿ — Step by Step

Idea: Repeatedly cross off one 'a' and one 'b' until all done.

Input: "aabb"
Tape: [a][a][b][b][B]

Strategy:
  → Replace leftmost 'a' with X
  → Scan right to find leftmost 'b', replace with Y  
  → Go back left, find next 'a'...
  → When no more 'a': verify no more 'b' remain

States: q0(start), q1(scan right for b), q2(scan left for a),
        q3(check all done), q_accept, q_reject

δ(q0, a) = (q1, X, R)   ← cross off 'a', go right to find 'b'
δ(q1, a) = (q1, a, R)   ← skip over a's
δ(q1, Y) = (q1, Y, R)   ← skip over already-marked Y's
δ(q1, b) = (q2, Y, L)   ← cross off 'b', go left
δ(q2, a) = (q2, a, L)   ← scan left
δ(q2, Y) = (q2, Y, L)   ← scan left past Y's
δ(q2, X) = (q0, X, R)   ← found X, go right for next pair
δ(q0, Y) = (q3, Y, R)   ← no more a's, check no b's
δ(q3, Y) = (q3, Y, R)   ← skip Y's
δ(q3, B) = (q_accept, B, R)  ← all matched! ACCEPT

TM Acceptance Modes

Mode	Meaning
Accept	TM enters q_accept state
Reject	TM enters q_reject state (explicit rejection)
Loop	TM runs forever (never halts) — the problem!

Church-Turing Thesis

Any algorithm that can be executed by ANY computer can also be simulated by a Turing Machine. TM is the universal model of computation — nothing is more powerful.

17. Variants of Turing Machines MEDIUM

Variant	Description	Power
Standard TM	1 tape, infinite right	Base
Multi-tape TM	k tapes, k heads	= Standard TM
Non-deterministic TM	Multiple choices at each step	= Standard TM
2-way infinite tape	Tape extends left AND right	= Standard TM
Universal TM (UTM)	Simulates ANY TM given its description	= Standard TM
Linear Bounded Automaton (LBA)	TM restricted to input-length tape	CSL (Type 1)

🧠 Trick — All TM variants = same power!

No matter how many tapes, heads, or non-determinism you add → still same as basic TM. The only exception is LBA (restricted TM) which is strictly weaker.

Universal Turing Machine (UTM)

A UTM takes as input: ⟨M, w⟩ (encoding of TM M and input w) → simulates M on w. This is the theoretical basis of modern programmable computers!

18. Decidability & Undecidability ⭐ VERY IMP

🌍 Analogy — Questions with definitive answers

Decidable = "Is 7 prime?" — a computer can always answer YES or NO.
Undecidable = "Will this program run forever?" — no computer can EVER answer this reliably, even in principle.

Language Classification

Class	Also Called	TM Behavior	Example
Decidable (Recursive)	Recursive	Always halts with accept/reject	aⁿbⁿ, all CFLs
Semi-Decidable (RE)	Recursively Enumerable	Halts on accept; may loop on reject	A_TM
Not RE	—	No TM can recognize it	Complement of Halting Problem

The Halting Problem (HP)

HALTING PROBLEM — Undecidable!

HP: Given TM M and input w, does M halt on w?

A_TM = {⟨M, w⟩ | TM M accepts input w} — also undecidable!

These are the most famous undecidable problems — guaranteed in exams.

Proof that A_TM is Undecidable (Diagonalization)

📝 Proof Sketch

Assume H is a TM that decides A_TM (decides if ⟨M,w⟩ accepts).
Construct D(⟨M⟩): runs H(⟨M, ⟨M⟩⟩) then does the OPPOSITE:
  • If H says "M accepts ⟨M⟩" → D REJECTS
  • If H says "M rejects ⟨M⟩" → D ACCEPTS
Run D on itself: D(⟨D⟩):
  • If D accepts ⟨D⟩ → by definition, D rejects → contradiction!
  • If D rejects ⟨D⟩ → by definition, D accepts → contradiction!
Both cases are impossible → H cannot exist → A_TM is undecidable. ■

Reduction

To prove language L is undecidable: reduce a known undecidable problem to L.

If A is undecidable and A ≤ₘ B (A reduces to B), then B is also undecidable.

🧠 Know These Undecidable Problems

• Halting Problem (HP)
• A_TM (acceptance problem)
• E_TM (does TM accept empty language?) — undecidable
• EQ_TM (are two TMs equivalent?) — undecidable
• Rice's Theorem: ANY non-trivial property of TM-recognized languages is undecidable!

Rice's Theorem (Big Shortcut!)

RICE'S THEOREM

Any non-trivial semantic property of Turing Machines is undecidable.

Non-trivial = property that is TRUE for some TMs and FALSE for others.
Semantic = about the language it recognizes (not about implementation).

Examples of undecidable (by Rice's): "Does TM accept empty string?", "Does TM accept at least 3 strings?", "Is L(M) regular?"

19. Complexity Theory: P, NP, NP-Complete ADVANCED

🌍 Analogy

P: Problems a computer can solve quickly (like finding shortest path in a map).
NP: Problems where if someone gives you an answer, you can CHECK it quickly — but finding the answer yourself might be slow.
Like a jigsaw puzzle: checking if it's solved is easy, solving from scratch is hard!

Definitions

Class	Definition	Examples
P	Solvable in polynomial time O(nᵏ)	Sorting, shortest path, primality testing
NP	Solution verifiable in polynomial time	SAT, TSP, Graph Coloring, Subset Sum
NP-Hard	Every NP problem reduces to it; at least as hard as NP	Halting problem, TSP optimization
NP-Complete	In NP AND NP-Hard (hardest problems in NP)	SAT, 3-SAT, Vertex Cover, Clique

The Big Question: P = NP?

The most famous unsolved problem in computer science!
If P = NP: every problem whose solution can be checked fast can also be solved fast.
Most experts believe P ≠ NP but it has never been proven.

Polynomial-Time Reductions

To show B is NP-Complete:

Show B ∈ NP (give a polynomial verifier)
Show some NP-Complete problem A ≤ₚ B (A reduces to B in poly time)

Important NP-Complete Problems to Know

Problem	Description
SAT	Boolean formula satisfiability (first proven NP-C by Cook)
3-SAT	SAT with clauses of exactly 3 literals
Vertex Cover	Find k vertices that touch all edges
Clique	Find k mutually connected vertices
Hamiltonian Path	Path visiting every node exactly once
TSP (decision)	Is there a tour of cost ≤ k?
Subset Sum	Does a subset sum to target T?

🧠 Relationships to Remember

P ⊆ NP ⊆ NP-Hard
NP-Complete = NP ∩ NP-Hard
If any NP-Complete problem is in P → P = NP (and world breaks!)
Venn diagram: P is a circle inside NP; NP-Complete sits on the boundary of NP; NP-Hard extends beyond NP.

20. Quick Revision Cheat Sheet 🚀

Hierarchy Summary

Language Class	Machine	Grammar	Closed Under
Regular	DFA/NFA	Regular	Everything
CFL	PDA	CFG	Union, Concat, Star (NOT ∩, complement)
CSL	LBA	CSG	All boolean ops
RE (r.e.)	TM (halts on accept)	Unrestricted	Union, Concat, Star, ∩
Recursive	TM (always halts)	—	All boolean ops

CFL Closure Properties

Operation	CFL closed?
Union	✅ YES
Concatenation	✅ YES
Kleene Star	✅ YES
Intersection	❌ NO (counterexample: {aⁿbⁿcⁿ})
Complement	❌ NO
Intersection with Regular	✅ YES

Must-Know Non-Regular Languages

aⁿbⁿ (equal a's and b's)
ww (string repeated) — use pumping lemma
aⁿ² (square number of a's)
Set of all palindromes
Set of prime-length strings

Must-Know Non-CFL Languages

aⁿbⁿcⁿ (equal three symbols)
{ww | w ∈ {a,b}*} (string is its own copy)
{a^(n²)} — but this IS NOT CFL (also not regular)
{aⁿbⁿcⁿdⁿ}

Key Formulae Flashcards

MUST MEMORISE

Fact	Value
Max DFA states for n-state NFA	2ⁿ
Min states DFA for strings divisible by k	k states
\|Σ*\| (all strings over Σ)	Infinite (countably)
\|Power set of Q\| (\|2^Q\|)	2^\|Q\|
Pumping length for Myhill-Nerode	# of equivalence classes
TM tape alphabet vs input	Γ ⊇ Σ, B ∈ Γ, B ∉ Σ

Last-Minute Exam Tips

⚠️ Top 5 things students get wrong:
1. DFA must have transition for EVERY state-symbol pair — don't forget dead states!
2. NFA→DFA: the empty set ∅ can be a DFA state too (dead/trap state)
3. Pumping Lemma: |y| ≥ 1 (NOT |y| ≥ 0) — y must be non-empty!
4. CFL Pumping Lemma: pump v AND y together (both by i), not separately
5. Undecidable ≠ Non-RE — Halting Problem IS RE (semi-decidable), just not decidable!

🧠 Final Memory Map

Regular → DFA/NFA/Regex ← all equivalent ← prove NOT regular with Pumping Lemma
CFL → CFG/PDA ← equivalent ← prove NOT CFL with CFL Pumping Lemma
Decidable → TM always halts ← closed under complement
RE → TM halts on yes ← NOT closed under complement
NP-Complete → hardest in NP ← show by reduction from known NP-C problem

TOC Exam Notes

0. What is Theory of Computation? EASY

Key Terms — Plain English

1. Chomsky Hierarchy ⭐ EXAM FAV

2. Deterministic Finite Automaton (DFA) ⭐ VERY IMP

Formal Definition

Key Rules of DFA

Example — DFA accepting strings ending in '1'

Transition Table (same example)

3. Non-Deterministic Finite Automaton (NFA) ⭐ VERY IMP

DFA vs NFA — Differences

Example — NFA for strings ending in 'ab'

4. ε-NFA (Epsilon-NFA) MEDIUM

ε-Closure

How to process input in ε-NFA

5. NFA → DFA Conversion (Subset Construction) ⭐ MOST IMP

Algorithm (Subset Construction)

Full Worked Example

6. Minimization of DFA MEDIUM

Table Filling Algorithm (Myhill-Nerode)

7. Regular Expressions ⭐ VERY IMP

Basic Operators

Important Identities (Memorize!)

Common Language → Regex Patterns

Arden's Theorem (for FA → Regex)

8. Regular Grammar MEDIUM

Types

9. Pumping Lemma for Regular Languages ⭐ EXAM FAVOURITE

The Lemma (Statement)

How to PROVE a language is NOT regular (exam procedure)

Classic Example — aⁿbⁿ is NOT regular

10. Closure Properties of Regular Languages MEDIUM

11. Context-Free Grammar (CFG) ⭐ VERY IMP

Formal Definition

Classic CFG Examples

Language: aⁿbⁿ (equal a's and b's)

Language: Balanced Parentheses

Language: Palindromes over {a,b}

Language: aⁿbᵐ where n ≠ m

Parse Trees and Derivations

Ambiguous Grammar Example

12. Simplification of CFG MEDIUM

1. Useless Symbols

2. ε-Productions (Remove Nullable Variables)

3. Unit Productions (A → B)

4. Order to Apply

13. Normal Forms: CNF and GNF ⭐ EXAM IMP

Chomsky Normal Form (CNF)

Converting to CNF — Algorithm

Greibach Normal Form (GNF)

14. Pushdown Automaton (PDA) ⭐ VERY IMP

Formal Definition

Transition Notation

Stack Operations

Two Acceptance Modes

PDA for aⁿbⁿ

15. Pumping Lemma for Context-Free Languages ⭐ IMP

Classic Example — aⁿbⁿcⁿ is NOT CFL

16. Turing Machine (TM) ⭐ MOST IMP

Formal Definition

Transition Meaning

Configuration (Instantaneous Description)

TM for aⁿbⁿ — Step by Step

TM Acceptance Modes

17. Variants of Turing Machines MEDIUM

Universal Turing Machine (UTM)

18. Decidability & Undecidability ⭐ VERY IMP

Language Classification

The Halting Problem (HP)

Proof that A_TM is Undecidable (Diagonalization)

Reduction

Rice's Theorem (Big Shortcut!)

19. Complexity Theory: P, NP, NP-Complete ADVANCED

Definitions

Polynomial-Time Reductions

Important NP-Complete Problems to Know

20. Quick Revision Cheat Sheet 🚀

Hierarchy Summary

CFL Closure Properties