Advanced~6h

Theory of Computation Drills

The procedures, until they are fast

CS304 teaches each of these once, against one example, and moves on. This is the volume — thirty-two procedures from tracing a DFA to reading a reduction, on questions generated fresh that never run out. Each stays green only while your recent answers hold.

Start this project See the modules

Modules: 9
Drills: 32
Build steps: 0
Time: ~6h

Walk out able to

Trace a machine, place a language among the classes, and read a reduction’s direction — without stopping to rebuild the definition first.

What you drill

Automata and languages

Runs, closures, subsets, and what a fixed memory cannot do.

Grammars and stacks

Chomsky types, derivations, ambiguity, one stack’s budget.

Machines and decidability

Configurations, the four bands, Rice, reduction direction.

P, NP and above

Certificates, completeness, gadgets, PSPACE and gaps.

The pitch

What you practise, and what you leave with

Not an artifact — a set of reflexes. Thirty-two procedures that are each either current or not, and a rail that says which.

You will practise

DFAs, NFAs, closures and subset steps
Regular and context-free, or provably not
Configurations, decidability, reductions
P, NP, completeness, PSPACE and gaps

Afterwards you can

Trace a DFA, an NFA and a stack first time
Classify a language by its memory budget
Read a reduction’s direction and say why
Place a language in P, NP, coNP or open

Modules

9 modules, 35 items

Lessons explain one idea. Drills repeat it until it sticks. Build steps make something that exists afterwards.

1
Strings, and what a language is
~13 min
Apply the identities and the language operations without re-deriving them first.
- LessonWhat this project is for4 min
- DrillApply the identities9 min
2
Run a finite automaton
~33 min
Trace a DFA, an NFA and a subset step to the end of the input, first time.
- DrillRun a DFA to the end12 min
- DrillAccept on some branch10 min
- DrillClose, then read a symbol11 min
3
Regular, and provably not
~1h
Read an expression, count classes, classify a language, and play the pumping game.
- LessonWhat the pumping drills do not mark10 min
- DrillRead a regular expression9 min
- DrillTell two states apart14 min
- DrillRegular, or provably not13 min
- DrillPlay the pumping adversary17 min
4
Grammars and their trees
~40 min
Classify, derive, spot ambiguity and name the normal-form step still owed.
- DrillClassify the productions9 min
- DrillCount the derivation steps11 min
- DrillTwo trees, or one12 min
- DrillName the normal-form step8 min
5
One stack
~51 min
Track a stack, tell DCFL from CFL, and beat every window of the five-piece split.
- DrillWatch the stack10 min
- DrillDeterministic, or only context-free12 min
- DrillContext-free, or provably not13 min
- DrillBeat every window16 min
6
Machines that may not halt
~1h
Step a configuration, place a language, and read a reduction’s direction.
- LessonWhat a reduction proof owes10 min
- DrillStep a configuration12 min
- DrillSame power, or only easier9 min
- DrillPlace the language13 min
- DrillWhich way a reduction runs15 min
- DrillDoes Rice apply12 min
7
Time, space, P and NP
~41 min
Relate the bounds, name a certificate, and place a language in P, NP, coNP or open.
- DrillTime against space9 min
- DrillPolynomial in what12 min
- DrillName the certificate9 min
- DrillNP, coNP, or open11 min
8
NP-completeness
~34 min
Separate hard from complete, name the roster’s budgets, and find a gadget’s bug.
- DrillHard, or complete9 min
- DrillThe classic roster10 min
- DrillFind the gadget bug15 min
9
Above NP
~36 min
Place the space and randomized classes, and read a ratio as a gap.
- DrillSpace is reusable9 min
- DrillWhich error is allowed9 min
- DrillA ratio is a gap9 min
- DrillThesis, or theorem9 min