Short, self-checking practice for Theoretical Computer Science I. Every answer is checked by a fixed key, with the slide reference and an explanation.
Daily mix
…Loading your progress…
StartPhase 1 · Basics
Definitions, statements, closure facts and the lecture algorithms.
- B1Words, languages, regular expressions21 itemsCh. 1 · Prop 1.10, 1.11
- B2Finite automatasoonCh. 2–3 · Prop 2.3, Thm 2.6, Prop 3.3–3.7
- B3Minimisation and Myhill–NerodesoonCh. 4 · Thm 4.3, Lemma 4.5, 4.6
- B4Closure properties and pumpingsoonCh. 5 · Thm 5.1–5.7
- B5Grammars and CNFsoonThm 8.4, Lemmas 8.5–8.9, Thm 8.11, 8.13
- B6Pushdown automatasoonProp 9.5, Thm 9.6, Lemma 9.7, Thm 9.9, Prop 9.10
- B7Context-free theorysoonThm 10.1–10.7, 11.1–11.13
- B8Models of computationsoonProp 14.6, Thm 14.9–14.14, 15.6, 16.1–16.3
- B9DecidabilitysoonLemma 17.3–17.11, Thm 17.7–17.14, 18.1–18.3
- B10ComplexitysoonLemma 19.2–22.2, Thm 21.5–21.8, 22.10
- T/FTrue or false, and whysoonAll chapters
Phase 2 · Advanced
Reductions, rigorous proofs and constructions. Coming after Phase 1.
- A1Reduction workshopBuild f, check it on instances, prove both directions.
- A2Undecidability proofsReductions from K, H, H₀, PCP; Rice.
- A3Rigorous proofsInduction, pumping adversary, Myhill–Nerode.
- A4Constructions for new operationsDefine Q, δ, s, F for operations you haven't seen.
- A5ClassificationRegular? Context-free? In P? Pick the tool and prove it.
- A6Turing machine analysisTrace configurations, find the computed function.
- A7Mock exams180 minutes, real structure, Part I / Part II rule.