
Theory of Computation
By downloading or studying this deck you agree to the deck directory terms, including the deck's licence.
Theory of computation flashcards for a bachelor's course: finite automata, context-free languages, Turing machines, computability and complexity, with typeset maths and 17 exam-style exercises.
What's inside
- Finite Automata — DFAs and NFAs, the subset construction, regular expressions, minimisation and Myhill–Nerode, closure, the pumping lemma and regular grammars.
- Context-Free Languages — grammars and ambiguity, normal forms and CYK, pushdown automata, the pumping lemma for context-free languages, closure and decision problems.
- Turing Machines — machines and their variants, enumerators, LBAs and the Chomsky hierarchy, the Church–Turing thesis, recursive functions and the λ-calculus.
- Computability — decidable and recognisable languages, the universal machine, diagonalisation and halting, reductions, Rice's theorem, PCP and the recursion theorem.
- Complexity — time on Turing machines, P and NP, Cook–Levin and NP-completeness, coNP, space and Savitch, L and NL, the hierarchy theorems and coping with hardness.
- Practice — 17 exam-style exercises: constructions, traces, full proofs, reductions and classifications.
Every card is written in our own words with our own examples, and every worked example, trace and model answer is checked by script. The Practice deck is an exam: it draws three exercises at random, and you grade your answers against each marking scheme. Scope and checks draw on two open textbooks: Jim Hefferon, Theory of Computation: Making Connections (CC BY-SA), and the Open Logic Project's Open Logic Text (CC BY 4.0).
1,797 cards in total.
What's inside
- 1 Finite Automata 459 cards
- 2 Context-Free Languages 307 cards
- 3 Turing Machines 314 cards
- 4 Computability 259 cards
- 5 Complexity 441 cards
- Practice Exam 17 cards
A few cards
1 Finite Automata
459 cards
Front
Alphabet: definition
Back
A finite, nonempty set of symbols, usually called , such as , or all Unicode characters. Symbols are atomic: a lexer reads single characters, while the symbols of a parser are whole tokens such as while.
core · A second alphabet, for a stack or a tape, is usually called .
Front
Word over an alphabet: definition
Back
A finite sequence of symbols of , written without commas: abba is a word over . Its length counts its symbols, the empty word is the one word of length 0, and counts the occurrences of the symbol in .
core · Also called a string. Some books write for .
Front
Words of length 4 over : how many there are
Back
81, which is : each of the four positions takes one of the three symbols, independently of the others. An alphabet of symbols has words of length , so each extra position multiplies their number by .
core · Exactly one word, , has length 0, which matches .
2 Context-Free Languages
307 cards
Front
Context-free grammar: definition
Back
A context-free grammar is a 4-tuple : a finite set of variables, an alphabet of terminals disjoint from , a finite set of rules with and , and a start variable .
core · Variables are also called nonterminals, rules productions; is the rule's head, its body. Chomsky 1956.
Front
Grammar , : its variables, terminals, rules and start variable
Back
Variables and , terminals a, b and c, start variable , and four rules: , , and . The bar only lists several bodies for one head.
core · Unless stated otherwise, the head of the first rule is the start variable; capitals are variables, small letters terminals.
Front
Context-free grammar: why "context-free"
Back
Every head is a single variable, so a variable may be rewritten by any of its rules wherever it stands, whatever symbols surround it. Grammars whose rules may look at neighbours, such as , are context-sensitive and describe more languages.
core · Context-sensitive grammars: → Turing machines.
3 Turing Machines
314 cards
Front
Turing machine: definition
Back
A Turing machine is a 7-tuple : finite sets of states , input symbols and tape symbols with the blank ; a transition function ; a start state; and an accept and a reject state, .
core · Turing 1936. Symbols of outside serve as marks and separators. Books vary: halting state sets, a partial , four-tuples.
Front
Turing machine: how a run starts
Back
The input fills the leftmost cells of a tape that is infinite to the right and blank everywhere else; the head scans cell 1 and the state is . Since , the first blank marks where the input ends.
core
Front
Transition : what the step does
Back
Reading a in state , the machine replaces that a by x, steps one cell right and continues in . Every step does all three at once; writing the symbol that is already there leaves the cell unchanged.
core
4 Computability
259 cards
Front
Co-recognisable language: definition
Back
is co-recognisable if its complement is recognisable: some machine accepts exactly the words that are not in .
core · Also called co-r.e. Every decidable language is recognisable and co-recognisable.
Front
Finite language: whether it is decidable
Back
Always: a decider can store its finitely many words in its states, compare the input with each, and halt. This holds even when nobody knows which words the language contains.
core
Front
A language is decidable exactly when both and are recognisable.
Back
A language is decidable exactly when both and are recognisable.
core · So if is recognisable but undecidable, is not recognisable, as for .
5 Complexity
441 cards
Front
Running time of a deterministic Turing machine: definition
Back
For a decider , the function where is the largest number of steps takes on any input of length . One says runs in time , or is a -time machine.
core · Defined for deciders only: a machine that loops on some input has no running time. Hartmanis & Stearns 1965.
Front
Running time: why the largest number of steps over all inputs of length
Back
It is a guarantee that holds for every input of that length, the worst case. Averages depend on a distribution of inputs that the problem does not give, and a bound that fails on some inputs can't support statements about every instance.
core · Average-case complexity is a separate theory; the classes of this deck all use the worst case.
Front
Decider that takes steps on inputs starting with 0 and steps on inputs starting with 1: its running time
Back
for : the running time is the maximum over all inputs of length , and half of them take steps. Fast typical inputs don't lower it.
core
Practice
17 cards
Front
Exercise 1: An error alarm on a server log
A monitoring tool reads a server's status codes as a word over : e for an error, s for a success. It raises an alarm when two errors occur with at most one success between them, so the alarm language is the set of words that contain ee or ese. The team drew the NFA with states 0 to 3, start state 0 and accepting state 3:
- and : wait, or guess that this error starts the alarm;
- and : an error has just been read;
- and : an error and one success have been read;
- : the alarm has been raised.
The subset construction runs the deck's worklist procedure, with e before s; the sets are named , , , … in the order they are found. For a stricter rule, "two errors with at most successes between them", the analogous NFA has states 0 to and an accepting state : 0 loops on both letters and guesses an error into 1, state moves to on s for , and each of the states 1 to moves to on e, which loops.
1.1 Run the subset construction on the alarm NFA : the reachable sets, their transitions, and the accepting sets. (3 points)
1.2 Minimise the subset DFA of the alarm NFA by table filling: the pairs marked at the start and in each pass, and the minimal DFA. (3 points)
1.3 Show with the Myhill–Nerode theorem that no DFA for the alarm language , the words containing ee or ese, has fewer than 4 states. (2 points)
1.4 Give a regular expression for the logs that raise no alarm, the complement of the alarm language , and say why it is right. (2 points)
1.5 For the stricter alarm rule with at most successes between two errors, how many sets does the subset construction build from the NFA , and how many states does the minimal DFA have? (2 points)
Back
1.1 Run the subset construction on the alarm NFA : the reachable sets, their transitions, and the accepting sets. (3 points)
3 points: in the order found, A = {0}, B = {0, 1}, C = {0, 1, 3}, D = {0, 2}, E = {0, 2, 3}, F = {0, 3}; other names count (1) · transitions, on e then s: A to B and A; B to C and D; C to C and E; D to C and A; E to C and F; F to C and F (1) · C, E and F accept, as they contain 3; only 6 of the 16 subsets are reachable (1)
Model answer: Start with . On e it goes to , new as ; on s it stays at . From , e gives , new as , and s gives , new as . From , e gives again and s gives , new as . From , e gives and s gives , since 2 has no move on s. From , e gives and s gives , new as ; from , e gives and s gives . Nothing new appears: the DFA has 6 states, and , and accept. The other 10 subsets, such as or , never occur, because 0 is in every set: the NFA can always keep waiting.
1.2 Minimise the subset DFA of the alarm NFA by table filling: the pairs marked at the start and in each pass, and the minimal DFA. (3 points)
3 points: at the start the 9 pairs of an accepting and a non-accepting set: AC, AE, AF, BC, BE, BF, CD, DE, DF (1) · pass 1 marks AB and AD, as e leads both to the marked pair {B, C}; pass 2 marks BD, as s leads to the newly marked {D, A}; pass 3 marks nothing, and CE, CF and EF stay unmarked; the witnesses e and se needn't be given (1) · four classes {A}, {B}, {D} and {C, E, F}: A has e to B and s to A; B has e to the alarm state and s to D; D has e to the alarm state and s to A; the alarm state loops on both letters (1)
Model answer:
- Start: each of the 3 accepting sets paired with each of the 3 others, 9 pairs, distinguished by .
- Pass 1:
esends to but and to , so and lead to the marked pair ; their witness ise. goes to and oneand to the unmarked ons. - Pass 2: is now marked, so is marked with witness
se:efollowed bysegivesese, an alarm, andesfollowed bysegivesesse, none. - Pass 3 marks nothing. Every letter takes , and to , or again, so their pairs are never marked.
The minimal DFA has 4 states: (no error pending), (an error just read), (an error and then one success) and the merged alarm state , which loops on both letters. goes to on e and stays on s; goes to the alarm state on e and to on s; goes to the alarm state on e and back to on s. Once the alarm is raised, nothing more needs remembering.
1.3 Show with the Myhill–Nerode theorem that no DFA for the alarm language , the words containing ee or ese, has fewer than 4 states. (2 points)
2 points: four pairwise distinguishable words, such as ε, e, es and ee (1) · a separating suffix for each of the six pairs: e for ε and e, e for ε and es, se for e and es, and ε for ee against each of the others, as only ee is in L; any four words from the four classes count, with their suffixes (1)
Model answer: Take , e, es and ee. ee is in and the others are not, so the empty suffix separates ee from each of them. The suffix e separates from e (e against ee) and from es (e against ese). The suffix se separates e from es: ese is in , esse is not. So has at least four classes, and every DFA for needs at least 4 states; the minimal DFA from table filling has exactly 4.
1.4 Give a regular expression for the logs that raise no alarm, the complement of the alarm language , and say why it is right. (2 points)
2 points: an expression such as s∗(ε ∪ e(sss∗e)∗s∗), s∗(esss∗)∗(ε ∪ es∗) or (s ∪ esss∗)∗(ε ∪ es∗); any expression with exactly these words counts, and a check helps: ε, e and esse must match, ese and eses must not (1) · the reason: a log raises no alarm exactly when every two consecutive errors are separated by at least two successes, with any successes before the first error and after the last (1)
Model answer: . A log without an alarm consists only of successes, or it has errors separated by blocks of at least two successes, , with any number of successes before the first error and after the last; the expression lists exactly these words. Equivalent forms are and . A quick test: e, esse and ssess match, while ese and seess don't.
1.5 For the stricter alarm rule with at most successes between two errors, how many sets does the subset construction build from the NFA , and how many states does the minimal DFA have? (2 points)
2 points: 2k + 4 sets: the waiting sets {0}, {0, 1}, …, {0, k + 1}, which record how far the last error lies back, and as many accepting sets, which also hold k + 2; no exponential blow-up, since only the most recent error matters (1) · k + 3 states: the k + 2 waiting sets stay apart, separated by suffixes of the form sʲe, while all accepting sets merge into one alarm state; for k = 1 that is 6 sets and 4 states (1)
Model answer: sets, states. Every reachable set contains 0. Without an alarm it holds at most one other state , the position reached since the last error: , , …, , which is sets. After an alarm, joins, beside and possibly one : another sets. A suffix raises the alarm from exactly when , so the waiting sets are pairwise distinguishable, while every accepting set accepts every continuation. So the minimal DFA has the waiting states and one alarm state.
Front
Exercise 2: The back button of a browser
A browser logs each tab as a word over : v when the user visits a new page, k when they press back. Back is allowed only while there is a page to go back to, so the valid logs arevvkvk is valid; vkk is not, as the second back press has nowhere to go. Let be the set of logs that contain kk.
A kiosk version keeps at most three pages of back history: a back press with an empty history does nothing, and a visit with three pages stored drops the oldest. Its analyser asks which logs end with an empty back history; call that language .
2.1 Prove with the pumping lemma that the valid browser logs are not regular. (4 points)
2.2 A classmate's proof that the valid browser logs are not regular starts from the word . Why can't it succeed, whatever it pumps with? (1 point)
2.3 Build the Thompson NFA for , the logs that contain kk, from the expression with the deck's fragments: how many states, moves on letters and -moves does it have, and which states make up the -closure of its start state? (2 points)
2.4 Give the minimal DFA for the kiosk language , the logs that end with an empty back history when at most three pages are kept, and say why is regular although is not. (2 points)
2.5 Is regular, where is the set of valid browser logs and the set of logs that contain kk? Prove your answer. (2 points)
Back
2.1 Prove with the pumping lemma that the valid browser logs are not regular. (4 points)
4 points: assume H regular with pumping length p, and take a word of H of length at least p that depends on p, such as vᵖkᵖ (1) · every split xyz with |xy| ≤ p and |y| ≥ 1 has y = vʲ with j ≥ 1, as the first p letters are v's (1) · pumping down, i = 0, gives v^(p−j)kᵖ, which as a whole has more k's than v's and is not in H; pumping up stays in H and proves nothing (1) · every split fails, contradicting the lemma, so H is not regular; other words, such as vᵖkᵖv with i = 0, count (1)
Model answer: Suppose were regular, with pumping length . The word is in , since no prefix has more ks than vs, and . Take any split with and . The first letters are vs, so with . Pumping down gives , whose whole word is a prefix with back presses after only visits, so . This holds for every allowed split, contradicting the pumping lemma; is not regular.
2.2 A classmate's proof that the valid browser logs are not regular starts from the word . Why can't it succeed, whatever it pumps with? (1 point)
1 point: for p ≥ 2 the opponent may split (vk)ᵖ as x = ε, y = vk, z = (vk)^(p−1), with |xy| ≤ p and |y| ≥ 1, and every xyⁱz = (vk)^(p−1+i) is a valid log, so this split pumps for every i; a proof needs a word that no allowed split can pump, such as vᵖkᵖ
Model answer: The proof has to defeat every allowed split, and has one it can't defeat: for , take , and . Then , and alternates visits and back presses, so it is a valid log for every , pumped down or up. The word has to be chosen so that its first letters can only be visits, as in .
2.3 Build the Thompson NFA for , the logs that contain kk, from the expression with the deck's fragments: how many states, moves on letters and -moves does it have, and which states make up the -closure of its start state? (2 points)
2 points: 20 states, 6 moves on letters and 19 ε-moves: two states and one move for each of the six letters, 2 states and 4 ε-moves for each of the two unions and each of the two stars, and one ε-move for each of the three concatenations (1) · 6 states: the first star's start and accepting state, the first union's start, the states before its v and its k, and the state before the first k of kk; the final accepting state is not among them, so ε ∉ K, and a log may begin with either letter (1)
Model answer: 20 states, 6 moves on letters and 19 -moves. The six letters v, k, k, k, v, k give 12 states with one move each; each of the two unions and each of the two stars adds 2 states and 4 -moves, 8 states and 16 -moves in all; and each of the three concatenations adds one -move. The -closure of the start state, the first star's start, holds 6 states: that start, the first star's accepting state, the first union's start, the states before its v and its k, and, through the concatenation, the state before the first k of kk. The final accepting state is not among them, so , and a log may begin with either letter.
2.4 Give the minimal DFA for the kiosk language , the logs that end with an empty back history when at most three pages are kept, and say why is regular although is not. (2 points)
2 points: states 0, 1, 2 and 3 for the number of pages stored, with start and accepting state 0; v leads from 0 to 1, 1 to 2, 2 to 3 and 3 to 3, and k from 3 to 2, 2 to 1, 1 to 0 and 0 to 0 (1) · the four states are pairwise distinguishable, d and a larger d′ by the suffix kᵈ, so no DFA has fewer; E is regular because the kiosk itself keeps a bounded history, while H needs an unbounded count (1)
Model answer: The state is the number of pages in the back history, 0 to 3. v adds one, staying at 3 when the history is full; k removes one, staying at 0 when it is empty. State 0 is the start and the only accepting state. For depths , the suffix empties the history from but not from , so all four states are needed. is regular because the kiosk forgets everything beyond three pages: its memory is bounded by design, while deciding needs an unbounded count of the pages to return to.
2.5 Is regular, where is the set of valid browser logs and the set of logs that contain kk? Prove your answer. (2 points)
2 points: yes: H ∪ K = {ε} ∪ v(v ∪ k)∗ ∪ (v ∪ k)∗kk(v ∪ k)∗, since the logs outside it are exactly those that start with k and contain no kk (1) · the argument: a log that starts with k is invalid at once; in a log that starts with v and has no kk, every k comes right after its own v, so every prefix has at least as many v's as k's; so a non-regular language united with a regular one can be regular (1)
Model answer: Yes. Take a log that contains no kk. If it starts with k, its first letter already breaks . If it starts with v, every k in it comes right after a v, and different ks come after different vs, so every prefix has at least as many visits as back presses and . So the logs outside are exactly those that start with k and contain no kk, and
a regular language. Adding the regular covers exactly the part of that needed counting.
Front
Exercise 3: A microwave oven's event log
A microwave oven reports events as a word over : s for the start button, o for opening the door, t for the timer running out. Its controller is a DFA with the states (idle, the start state), (running) and (paused), and is the only accepting state, so the language is the set of logs that leave the oven idle:
- and ;
- (another 30 seconds), and ;
- (resume, once the door is shut) and .
State elimination follows the deck: a new start state with and a new accepting state with , parallel moves joined by , and, when is eliminated, the label for every pair , of remaining states.
3.1 Turn the microwave DFA into a regular expression by state elimination, removing , then , then : the labels created at each step and the final expression. (4 points)
3.2 Eliminate the microwave DFA's states in the order , , instead. Which expression results? (2 points)
3.3 A technician summarises the microwave's idle-ending logs as . Find the shortest log on which this expression and the DFA disagree, and say which of the two languages contains the other. (2 points)
3.4 The oven's service log also needs the door to have been opened an even number of times. Build the product of the microwave DFA with the two-state DFA that tracks the parity of door openings, states (even, the start) and (odd), and give its accepting pairs for "idle and even" and for "idle or even". (2 points)
Back
3.1 Turn the microwave DFA into a regular expression by state elimination, removing , then , then : the labels created at each step and the final expression. (4 points)
4 points: the GNFA: new start S with S to I labelled ε, new accepting F with I to F labelled ε, and loops o ∪ t on I and on P (1) · removing P creates the loop s ∪ o(o ∪ t)∗s on R, the only path through P being R to P to R (1) · removing R creates the loop o ∪ t ∪ s(s ∪ o(o ∪ t)∗s)∗t on I (1) · removing I labels S to F with (o ∪ t ∪ s(s ∪ o(o ∪ t)∗s)∗t)∗; equivalent simplifications count (1)
Model answer:
- Preparation: add and , and join parallel moves, so and each carry a loop . Every state can reach .
- Remove : its only neighbour is , with and , so 's loop becomes : a pause, any events while paused, then a restart.
- Remove : the path , with 's loop in between, adds to 's loop, which becomes .
- Remove : with that loop gives
Each pass through the outer star goes from idle back to idle: an event that leaves the oven idle, or a cooking session that may be paused and resumed and ends when the timer runs out.
3.2 Eliminate the microwave DFA's states in the order , , instead. Which expression results? (2 points)
2 points: removing R first creates the loop o ∪ t ∪ ss∗t on I, the move ss∗o from I to P, the move ss∗t from P to I, and the loop o ∪ t ∪ ss∗o on P (1) · removing P and then I gives (o ∪ t ∪ ss∗t ∪ ss∗o(o ∪ t ∪ ss∗o)∗ss∗t)∗: longer, but with the same words; equivalent forms count (1)
Model answer: has the loop , two entries, and , and two exits, and . Removing it touches four pairs: 's loop gains , becomes , becomes , and 's loop gains . Removing then adds to 's loop, and removing gives
It describes the same logs. Removing first, the state with fewer moves, gives the shorter expression.
3.3 A technician summarises the microwave's idle-ending logs as . Find the shortest log on which this expression and the DFA disagree, and say which of the two languages contains the other. (2 points)
2 points: sost, of length 4: the oven pauses, resumes and finishes, back in I, but the expression allows no o between an s and the t that ends a session; no shorter log separates them, since leaving I through a pause and returning takes s, o, s and t; that sost is the only such log of length 4 needn't be shown (1) · the technician's language is a proper subset of the oven's: each of its blocks o, t and ss∗t leads from I back to I, but it misses every session with a pause (1)
Model answer: The DFA accepts sost: . The expression does not: after an s it allows only more ss and then a t. A shorter log can't separate them: every log the DFA accepts without entering is a sequence of the blocks , and , and a log that enters and returns to needs s, o, s and t at least. Every word of the expression is accepted by the DFA, because each of the blocks , and leads from back to ; so the technician's language is a proper subset of the oven's. It forgets the door.
3.4 The oven's service log also needs the door to have been opened an even number of times. Build the product of the microwave DFA with the two-state DFA that tracks the parity of door openings, states (even, the start) and (odd), and give its accepting pairs for "idle and even" and for "idle or even". (2 points)
2 points: all six pairs are reachable from (I, E): s leads to (R, same parity); o flips the parity and leads from I to I, from R to P and from P to P; t keeps the parity and leads from I to I, from R to I and from P to P (1) · "idle and even" accepts only (I, E); "idle or even" accepts (I, E), (I, O), (R, E) and (P, E); examples such as oo, accepted by both, o, accepted only by the union, and so, accepted by neither, needn't be given (1)
Model answer: The product's states are the pairs (oven state, parity), with start ; on each letter both components move at once. s takes to ; o takes to , to and to and flips the parity; t takes to , to and to and keeps it. From , s reaches , o reaches , and from those o gives , s gives , and o from gives : all six pairs are reachable. For the intersection the only accepting pair is ; for the union, every pair with or with : , , and . So oo is accepted by both, o only by the union, and so by neither, as the oven is paused after one opening.
Licence: Personal use Report this deck
New Computer science decks by email
Hear when they arrive, or tell us which deck you need.
Comments
Loading comments…