Akdeniz University · Department of Computer Engineering · Fall 2026
Every other course in this degree teaches you to build things. This one tells you what cannot be built, and why. Four machines, four impossibility theorems — and on these pages you can build every one of the machines and break it yourself.
A fixed number of states and one pass over the input. No memory at all.
defeated by 0ⁿ1ⁿOne stack, which you cannot read without popping. Enough for nesting, not for counting three things.
defeated by aⁿbⁿcⁿUnbounded tape, unrestricted movement. Nothing is missing — and that is exactly the problem.
defeated by ATMA Turing machine with a clock. Checking a solution is easy; finding one may not be.
defeated (probably) by SATEach page is a single self-contained HTML file. Nothing is installed, nothing is uploaded, and everything runs in your browser — so they work on the lab machines, on your phone, and offline.
Draw a machine, step a string through it, and list every string it accepts up to a given length. It tells you when your δ is not total.
week 02 · Sipser 1.2ε-moves, the active set of states, and the subset construction revealed one row at a time — then sent straight to the DFA builder.
week 02 · Sipser 1.3Thompson's construction and the subset construction, chained. Also why the "regex" in your favourite language is not a regular expression.
weeks 03, 05–06 · Sipser 1.4, 2.3Both pumping lemmas as a game against an adversary that always plays its best division. Win, and it writes your proof out for you.
week 04 · Sipser 2.1Derivations, parse trees, live ambiguity detection, and Chomsky normal form done in its four steps.
week 04 · Sipser 2.2Every nondeterministic branch searched, the accepting computation stepped through, and the stack drawn as it grows.
week 07 · Sipser 3.1Tape, head, configurations. Deciders for 0ⁿ1ⁿ and 0^(2ⁿ), a busy beaver, and one machine that never stops.
weeks 12–14 · Sipser 7.2–7.5Verify an assignment instantly, then watch brute force double with every variable. Then see 3SAT turn into CLIQUE.
The schedule is the one in your syllabus. Bring the printed handout to the lecture; open the tool afterwards and rebuild what we did on the board without looking at it.
| wk | date | subject | Sipser | tool |
|---|---|---|---|---|
| 01 | Sep 19 | Preliminaries | 0 | — |
| 02 | Sep 26 | Regular languages | 1.1–1.3 | DFA · NFA · regex |
| 03 | Oct 03 | Pumping lemma for RL | 1.4 | the duel |
| 04 | Oct 10 | CFGs and PDAs | 2.1–2.2 | grammars · PDA |
| 05 | Oct 17 | Pumping lemma for CFL | 2.3 | the duel, CF mode |
| 06 | Oct 24 | Pumping lemma for CFL | 2.3 | the duel, CF mode |
| 07 | Oct 31 | Turing machines | 3 | TM lab |
| 08 | Nov 07 | Midterm week, no classes | — | — |
| 09 | Nov 14 | Decidability | 4 | TM lab |
| 10 | Nov 21 | Reducibility | 5, 6.3 | — |
| 11 | Nov 28 | Midterm | from Part 2 | — |
| 12 | Dec 05 | Complexity | 7.1 | search vs checking |
| 13 | Dec 12 | P, NP and P vs NP | 7.2–7.3 | search vs checking |
| 14 | Dec 19 | NP-completeness | 7.4 | the reduction |
Do not read them. Rebuild them. Close the page, draw the machine on paper, then come back and check it against the tool — the DFA page will tell you if your δ is not total, the PDA page will find an accepting computation you did not know was there, and the grammar page will show you the second parse tree you did not think existed.
Every builder takes the same kind of formal spec the exam asks you to write. That is deliberate: if you can type it here, you can write it in the room.
Nine plain .html files, no build step, no dependencies and no server-side anything. Drop the folder on any web server, open index.html from a USB stick, or attach a single page to a Teams message and it still works — every page carries its own CSS and JavaScript.
The only network request any page makes is to Google Fonts. Block it, or be offline, and the pages fall back to system fonts and behave identically.
Nothing is collected. The only thing written to the browser is your light/dark preference and, on the NFA page, a one-shot handoff of a generated machine to the DFA page.