TCS Study

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…

Start

Phase 1 · Basics

Definitions, statements, closure facts and the lecture algorithms.

  • B1Words, languages, regular expressions21 items
    Ch. 1 · Prop 1.10, 1.11
  • B2Finite automatasoon
    Ch. 2–3 · Prop 2.3, Thm 2.6, Prop 3.3–3.7
  • B3Minimisation and Myhill–Nerodesoon
    Ch. 4 · Thm 4.3, Lemma 4.5, 4.6
  • B4Closure properties and pumpingsoon
    Ch. 5 · Thm 5.1–5.7
  • B5Grammars and CNFsoon
    Thm 8.4, Lemmas 8.5–8.9, Thm 8.11, 8.13
  • B6Pushdown automatasoon
    Prop 9.5, Thm 9.6, Lemma 9.7, Thm 9.9, Prop 9.10
  • B7Context-free theorysoon
    Thm 10.1–10.7, 11.1–11.13
  • B8Models of computationsoon
    Prop 14.6, Thm 14.9–14.14, 15.6, 16.1–16.3
  • B9Decidabilitysoon
    Lemma 17.3–17.11, Thm 17.7–17.14, 18.1–18.3
  • B10Complexitysoon
    Lemma 19.2–22.2, Thm 21.5–21.8, 22.10
  • T/FTrue or false, and whysoon
    All chapters

Phase 2 · Advanced

Reductions, rigorous proofs and constructions. Coming after Phase 1.

  • A1Reduction workshop
    Build f, check it on instances, prove both directions.
  • A2Undecidability proofs
    Reductions from K, H, H₀, PCP; Rice.
  • A3Rigorous proofs
    Induction, pumping adversary, Myhill–Nerode.
  • A4Constructions for new operations
    Define Q, δ, s, F for operations you haven't seen.
  • A5Classification
    Regular? Context-free? In P? Pick the tool and prove it.
  • A6Turing machine analysis
    Trace configurations, find the computed function.
  • A7Mock exams
    180 minutes, real structure, Part I / Part II rule.