CEUC302 · Theory of Computation · CHARUSAT, 5th Semester

Seven chapters, one running set of examples

A complete study guide across all five units — language foundations through Turing machines — built so a beginner and a strong student can read the same page and each get something out of it. Every chapter is fully self-contained: open any one directly, or work through them in order.

7chapters
28sections
266practice & self-test problems
11interactive figures
The thread running through every chapter

Leven (even number of a's) and Leq = {anbn} appear in Chapter 1 as two similarly-simple-looking languages that turn out to need very different amounts of memory — the question that organises the entire course. Leq is proven not regular three times over (Chapters 1, 2, 3) before finally getting an actual machine in Chapter 6. L3eq = {anbncn} goes one step further — not regular, then not context-free either (Chapter 5) — before Chapter 7 finally builds it a Turing machine. The arithmetic-expression grammar (id + id * id) carries Chapters 4–6 the same way, ambiguous at first, then fixed, then converted, then parsed, then turned into a pushdown automaton.

teal — accept / member / correct rose — reject / non-member / broken violet — non-terminals / secondary structure amber — whatever is in focus right now
Chapter 1 · Unit 14 sections · 38 problems

Language Foundation

Alphabets, strings, and Kleene star; grammars and ambiguity introduced; the Chomsky hierarchy as nested rings; pigeonhole and adjacency matrices previewed for the proofs to come.

1.1 Alphabets, Strings & Languages · 1.2 Grammars & Production Rules · 1.3 The Chomsky Hierarchy · 1.4 Proof Tools You'll Need Soon
Unit 2 · part 1 of 24 sections · 38 problems

Finite Automata I

DFA and the extended transition function; minimization and the Myhill–Nerode proof that Leq isn't regular; NFA and subset construction; regular expressions and Kleene's theorem.

2.1 Deterministic Finite Automata · 2.2 Minimization & Myhill–Nerode · 2.3 NFA & Subset Construction · 2.4 Regular Expressions & Kleene's Theorem
Unit 2 · part 2 of 24 sections · 38 problems

Finite Automata II

Closure under ∩, ∪, and complement via product construction; the formal Pumping Lemma; lexical analysis and the longest-match rule; a real DFA-based scanner, built and run.

3.1 Closure Properties · 3.2 The Pumping Lemma · 3.3 Lexical Analysis · 3.4 DFA-based Scanners
Unit 3 · part 1 of 24 sections · 38 problems

CFG I

Context-free grammars formalised; leftmost and rightmost derivations over the same parse tree; arithmetic-expression and dangling-else ambiguity, fixed by restructuring; the harder case where no fix exists at all.

4.1 Context-Free Grammars, Formally · 4.2 Derivations & Parse Trees · 4.3 Ambiguity · 4.4 Inherent Ambiguity
Unit 3 · part 2 of 24 sections · 38 problems

CFG II

Chomsky and Greibach Normal Form, fully converted and verified; the context-free Pumping Lemma; the surprising loss of closure under intersection; the CYK parsing table, filled in live.

5.1 Normal Forms · CNF & GNF · 5.2 The Pumping Lemma for CFLs · 5.3 Closure & Decidability · 5.4 Parsing · CYK & Top-Down
Chapter 6 · Unit 44 sections · 38 problems

Pushdown Automata

A stack added to the finite automaton; Leq finally recognised outright; the PDA↔CFG equivalence theorem; the one place nondeterminism stops being free — and where a stack shows up in real systems.

6.1 Pushdown Automata, Formally · 6.2 Designing PDAs · 6.3 PDA ↔ CFG Equivalence · 6.4 Determinism & Applications
Chapter 7 · Unit 54 sections · 38 problems

Turing Machines

The tape that moves both ways; L3eq finally decided; decidable versus recognisable made precise; the Halting Problem, proved undecidable by explicit construction — closing the loop Chapter 1 opened.

7.1 Turing Machines, Formally · 7.2 Designing a Turing Machine · 7.3 Decidable & Recognisable Languages · 7.4 The Halting Problem

CEUC302 · Theory of Computation · each chapter is a standalone HTML file — open any one directly, no server or network required.