TOC · Reading course
Machines that gain memory.
One lesson at a time.
From languages and finite automata to Turing machines and undecidability. Read the notes, work the examples, then check your answers.
91 reading items · 7 phases · Worked examples & practice
0%
0 of 91 reading items completed
Mark an item complete when you’re ready. Your place is saved in this browser.Your path through TOC
Lessons, phase bridges, chapter reviews, checkpoints, and revision in source order.
01PHASE 0Foundations0 / 13 complete
0.1.1What “computation” meansLesson0.2.1SetsLesson0.2.2Functions, relations and equivalence classesLesson0.2.3Proof techniquesLesson0.2.4Pigeonhole principleLesson0.2.5Directed graphsLessonL0.2Math toolkitChapter review0.3.1Alphabets and stringsLesson0.3.2Σᵏ, Σ*, Σ⁺ and languagesLesson0.3.3Operations on languagesLesson0.3.4Problems as languagesLessonL0.3Strings and languagesChapter reviewCP0FoundationsCheckpoint
02PHASE 1Finite Automata0 / 16 complete
B1Foundations, recalledPhase bridge1.1.1States and the DFALesson1.1.2Extended transition function and regular languagesLesson1.1.3DFA design patternsLesson1.1.4Product construction and complementLessonL1.1DFAChapter review1.2.1Nondeterminism and the NFALesson1.2.2ε-NFA and ε-closureLesson1.2.3Subset construction and the 2ⁿ blow-upLessonL1.2NFAChapter review1.3.1Unreachable, equivalent and distinguishable statesLesson1.3.2Partition and table-filling methodsLesson1.3.3Myhill–Nerode theoremLessonL1.3DFA minimizationChapter review1.4Mealy and Moore machinesLessonCP1Finite automataCheckpoint
03PHASE 2Regular Expressions & Regular Languages0 / 16 complete
B2Finite automata, recalledPhase bridge2.1.1Regular expressions: syntax and meaningLesson2.1.2Writing regexes, identities and equivalenceLessonL2.1Regular expressionsChapter review2.2.1Regex → ε-NFA (Thompson construction)Lesson2.2.2FA → regex: state elimination and Arden’s theoremLessonL2.2ConversionsChapter review2.3.1What a grammar isLesson2.3.2Right-linear and left-linear grammarsLessonL2.3Regular grammarsChapter review2.4.1Closure properties of regular languagesLesson2.4.2Algorithms for regular languagesLesson2.4.3Pumping lemma for regular languagesLesson2.4.4Drill: regular or not?LessonL2.4Properties of regular languagesChapter reviewCP2Regular expressions & regular languagesCheckpoint
04PHASE 3CFG, PDA & Context-Free Languages0 / 19 complete
B3Regular languages, recalledPhase bridge3.1.1Context-free grammars, derivations and parse treesLesson3.1.2Writing CFGs for standard languagesLesson3.1.3AmbiguityLessonL3.1Context-free grammarsChapter review3.2.1Removing useless symbols, ε- and unit productionsLesson3.2.2Chomsky and Greibach normal formsLessonL3.2Simplification and normal formsChapter review3.3.1Stack primer and the push-down automatonLesson3.3.2Acceptance by final state vs empty stackLesson3.3.3Designing PDAs; DPDA vs NPDA; DCFL ⊂ CFLLesson3.3.4CFG ↔ PDA equivalenceLessonL3.3Push-down automataChapter review3.4.1Closure properties of CFLs and DCFLsLesson3.4.2Algorithms for CFLs: emptiness, finiteness, membership (CYK)Lesson3.4.3Pumping lemma for CFLsLesson3.4.4Drill: regular, DCFL, CFL or not CFL?LessonL3.4Properties of CFLsChapter reviewCP3CFG, PDA & context-free languagesCheckpoint
05PHASE 4Turing Machines0 / 11 complete
B4Context-free languages, recalledPhase bridge4.1.1The Turing machine: tape, head, states, haltingLesson4.1.2Designing Turing machinesLessonL4.1The Turing machineChapter review4.2TM variants, linear bounded automata and context-sensitive languagesLesson4.3.1Recursive vs recursively enumerable; deciders and recognizersLesson4.3.2The Chomsky hierarchy and the containment chainLesson4.3.3Closure of REC and RE; L and L̅ both RE ⇒ L recursiveLessonL4.3TM variants and language classesChapter review4.4Encoding TMs, the universal TM, and the Church–Turing thesisLessonCP4Turing machinesCheckpoint
06PHASE 5Undecidability0 / 9 complete
B5Turing machines, recalledPhase bridge5.1Countable vs uncountable; diagonalizationLesson5.2The diagonal language and the halting problemLessonL5.2Countability, diagonalization and haltingChapter review5.3Reductions and proving undecidabilityLesson5.4Rice’s theorem and the Post Correspondence ProblemLesson5.5The master decidability tableLessonL5.5Reductions, Rice and the master tableChapter reviewCP5UndecidabilityCheckpoint
Make the most of each lesson
01 · Predict firstTry each prompt and example before opening its solution.
02 · Check your recallUse the self-tests and answer vaults to check your understanding.
03 · Track your readingMark an item complete when you’re done. Completion is separate from page position.
Your progress, your copy.
Saved in this browser. Export a backup to move your TOC progress to another device.
Adapted from your supplied TOC Mastery notes. Reading progress is separate from the Atlas topic checklist.