Unit I: Theory of Computation – Complete Exam Preparation Notes

Basic Concepts + Automata Theory
Clear explanations, examples & exam-oriented points

---

1. Introduction to Theory of Computation

Theory of Computation (TOC) deals with what can be computed and how efficiently.

Three Major Branches:

Branch	Question it Answers	Models/Tools
Automata Theory	What can be computed by simple machines?	DFA, NFA, PDA, Turing Machines
Computability	Which problems are solvable at all?	Turing Machines, Decidability, Recursion
Complexity	How much time/space is needed?	P, NP, NP-Complete, Reductions

2. Basic Definitions

Term	Definition	Example
Alphabet (Σ)	Finite, non-empty set of symbols	Σ = {0,1}, Σ = {a,b,c}
Symbol	An atomic element of alphabet	'a', '0'
String / Word	Finite sequence of symbols from alphabet	w = 0011, ε (empty string)
Length (|w|)	Number of symbols in w	|0011| = 4
Language (L)	Any set of strings over an alphabet	L = {0ⁿ | n≥0}
Σⁿ	All strings of length exactly n	Σ² = {00,01,10,11}
Kleene Star (Σ*)	All possible strings including ε	{ε, 0, 1, 00, 01, …}
Kleene Plus (Σ⁺)	Σ* excluding ε	All non-empty strings

3. Deterministic Finite Automaton (DFA)

Formal Definition (5-tuple)

M = (Q, Σ, δ, q₀, F)

• Q : finite set of states
• Σ : alphabet
• δ : Q × Σ → Q (exactly one transition)
• q₀ : start state
• F ⊆ Q : accepting states

Language Accepted

L(M) = { w ∈ Σ* | δ̂(q₀, w) ∈ F }

Example 1: Strings ending with 01 (Σ = {0,1})

States: q0 (start), q1, q2 (accept)

δ(q0,0)=q1    δ(q0,1)=q0
δ(q1,0)=q1    δ(q1,1)=q2
δ(q2,0)=q1    δ(q2,1)=q2

Accepts: 01, 001, 101, 1101 …
Rejects: ε, 0, 10, 11

4. Non-deterministic Finite Automaton (NFA)

δ : Q × (Σ ∪ {ε}) → 2^Q (multiple or zero transitions allowed)

Example: NFA for strings ending with 01

q0 --0--> q0
q0 --1--> q0
q0 --0--> q1
q1 --1--> q2 (accept)

Much smaller than equivalent DFA!

5. Equivalence of DFA and NFA

Theorem: Every NFA has an equivalent DFA → Both recognize Regular Languages

Subset Construction (Power Set Construction) – Most Important for Exam

1. Start state of DFA = ε-closure(q₀)
2. For each set S and symbol a → new state = ε-closure(δ(S, a))
3. Repeat until no new states
4. Accepting states = subsets containing at least one original final state

Max 2^|Q| states in DFA

6. NFA with ε-Transitions (ε-NFA)

• ε-closure(q) = all states reachable from q via ε only
• ε-NFA ≡ NFA ≡ DFA (same power)

7. Finite Automata with Output

Type	Output Depends On	Output Function
Mealy Machine	Current state + Input	λ : Q × Σ → Δ
Moore Machine	Only current state	λ : Q → Δ

Mealy is more compact | Moore → Mealy easy, Mealy → Moore may increase states

8. Minimization of DFA

Goal: Smallest DFA accepting same language

Myhill-Nerode Theorem (Very Important)

Two strings x ≡ y iff ∀ z, xz is accepted ⇔ yz is accepted

• Number of equivalence classes = number of states in minimal DFA
• Language is regular ⇔ finite equivalence classes

Minimization Steps

1. Remove unreachable states
2. Initial partition: Π = {F, Q−F}
3. Refine partitions until stable
4. Each final group → one state in minimal DFA

9. Summary Table (Quick Revision)

Concept	States	Deterministic?	ε-moves?	Language Class
DFA	Finite	Yes	No	Regular
NFA	Finite	No	No	Regular
ε-NFA	Finite	No	Yes	Regular
Mealy/Moore	Finite	Yes	No	Regular (with output)
PDA	Finite + Stack	—	—	Context-Free
Turing Machine	Finite + Tape	—	—	Recursively Enumerable

Most Important Exam Questions (Repeated Every Year)

1. Convert NFA/ε-NFA → DFA (subset construction)
2. Construct DFA for ends with / contains / even-odd
3. Minimize given DFA (table-filling / Myhill-Nerode)
4. Convert Mealy ↔ Moore machine
5. Design sequence detector (011, 110, etc.) using Mealy/Moore
6. State & prove Myhill-Nerode Theorem
7. Prove equivalence of DFA & NFA

Quick Revision One-Liners

• Regular languages closed under union, concatenation, kleene star
• NFA can be exponentially smaller than DFA
• ε-moves add convenience, not power
• Minimal DFA is unique (up to renaming)
• Myhill-Nerode gives theoretical basis of minimization

---

You are now fully prepared for Unit-1 Exam!
Practice 10 conversion + minimization questions → Full marks guaranteed! 🚀