Skip to content

Twenty-six instruments for one course.

Every tool runs step by step and writes down what it did in the language your exam expects. Nothing here hides its working.

26tools

5modules

simulateM1Simulate a finite automatonRun a DFA, NFA or ε-NFA on an input and watch every step, branch and ε-closure.simulateM1Classroom boardDraw states and arcs freehand on a dark board; each stroke is recognised and redrawn, and the machine it makes runs from the same screen.learnM1Strings and languagesAlphabets, powers, Σ*, length and concatenation, with every string of length ≤ k listed.convertM1 M2NFA → DFA (subset construction)Watch the subset construction build each state, one reachable subset at a time.convertM2Minimise a DFATable filling and partition refinement, with the distinguishable pairs marked as they are found.convertM2Regular expression playgroundThompson construction from a regular expression, and state elimination back again.convertM2Closure labUnion, intersection, complement, difference, reversal and homomorphisms — each built step by step.simulateM1Text and keyword searchKeywords to a guessing NFA to a recognising DFA, scanning real text with overlapping matches.learnM1 M2Applied case studiesThe department's own Module 1 and 2 case studies, as machines you can run.learnM2UNIX regular expressionsWhich extended operators are shorthand and which are not, plus a longest-match lexer.decideM2Practice — the question bankConstruction exercises graded exactly, with the shortest disagreeing string as feedback.proveM2The pumping lemma gamePlay the adversary, or watch it play you, on a language that is not regular.convertM3 M4Grammars, derivations and parse treesDerivations with growing parse trees, the ambiguity detector, and left recursion elimination.simulateM3Pushdown automataRun a PDA with state, input and stack in sync, the branch tree for every guess, and the ID sequence written out.simulateM3Build a PDAType δ line by line, see the machine drawn with a, X/YX labels, and check whether it is deterministic — pair by overlapping pair.convertM3PDA acceptance modesFinal state to empty stack and back, with the bottom marker doing the work.convertM3Grammar → PDAThe one-state construction of Theorem 6.13, then the built machine run on real inputs.convertM4Simplification and CNFε-productions, unit productions, useless symbols and Chomsky Normal Form as one pipeline in the safe order, the grammar diffed at each stage.proveM4CFL closure labUnion, concatenation, closure, reversal, substitution, intersection with a regular language, inverse homomorphism — and the intersection that fails.simulateM5Turing machinesThe chapter 8 machines run on a scrolling tape, the ID sequence written out, and a non-halting run stopped honestly.simulateM5Build a Turing machineType δ one move per line, see the diagram with X/Y → labels, and run it — one tape or several.convertM5Many tapes to oneTheorem 8.9 animated, with the 4n + 2k cost of Theorem 8.10 counted live.proveM5UndecidabilityRecursive inside RE inside everything, the four places a language and its complement can sit, and what the two classes are closed under.proveM5The diagonalization tableFig. 9.1 with every cell computed: machines decoded from binary strings, run under a step budget, and a diagonal you can complement.proveM5The reduction builderDrop one problem onto another to build A ≤ B, with the construction and the contradiction drawn — and the wrong direction refused.learnM1 M2 M3 M4 M5The hierarchy of language classesNested rings from regular out to every language, each with its machine, its closure and its pumping lemma, and the languages that separate them.