Computing EN Exam

Theory of Computation

1,797 cards 0 Version 1, updated November 19, 2026

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 Σ\Sigma, such as {0,1}\{0, 1\}, {a,b}\{a, b\} 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 Γ\Gamma.

Front

Word over an alphabet: definition

Back

A finite sequence of symbols of Σ\Sigma, written without commas: abba is a word over {a,b}\{a, b\}. Its length ∣w∣|w| counts its symbols, the empty word ε\varepsilon is the one word of length 0, and ∣w∣a|w|_a counts the occurrences of the symbol aa in ww.

core · Also called a string. Some books write λ\lambda for ε\varepsilon.

Front

Words of length 4 over {a,b,c}\{a, b, c\}: how many there are

Back

81, which is 343^4: each of the four positions takes one of the three symbols, independently of the others. An alphabet of kk symbols has knk^n words of length nn, so each extra position multiplies their number by kk.

core · Exactly one word, ε\varepsilon, has length 0, which matches k0=1k^0 = 1.

2 Context-Free Languages

307 cards

Front

Context-free grammar: definition

Back

A context-free grammar is a 4-tuple (V,Σ,R,S)(V, \Sigma, R, S): a finite set VV of variables, an alphabet Σ\Sigma of terminals disjoint from VV, a finite set RR of rules A→αA \to \alpha with A∈VA \in V and α∈(V∪Σ)∗\alpha \in (V \cup \Sigma)^*, and a start variable S∈VS \in V.

core · Variables are also called nonterminals, rules productions; AA is the rule's head, α\alpha its body. Chomsky 1956.

Front

Grammar S→aSc∣BS \to aSc \mid B, B→bB∣εB \to bB \mid \varepsilon: its variables, terminals, rules and start variable

Back

Variables SS and BB, terminals a, b and c, start variable SS, and four rules: S→aScS \to aSc, S→BS \to B, B→bBB \to bB and B→εB \to \varepsilon. The bar ∣\mid 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 aB→abaB \to ab, 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 (Q,Σ,Γ,δ,q0,qacc,qrej)(Q, \Sigma, \Gamma, \delta, q_0, q_{\mathrm{acc}}, q_{\mathrm{rej}}): finite sets of states QQ, input symbols Σ\Sigma and tape symbols Γ⊇Σ∪{⊔}\Gamma \supseteq \Sigma \cup \{\sqcup\} with the blank ⊔∉Σ\sqcup \notin \Sigma; a transition function δ:Q×Γ→Q×Γ×{L,R}\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}; a start state; and an accept and a reject state, qacc≠qrejq_{\mathrm{acc}} \ne q_{\mathrm{rej}}.

core · Turing 1936. Symbols of Γ\Gamma outside Σ\Sigma serve as marks and separators. Books vary: halting state sets, a partial δ\delta, four-tuples.

Front

Turing machine: how a run starts

Back

The input ww fills the leftmost ∣w∣|w| cells of a tape that is infinite to the right and blank everywhere else; the head scans cell 1 and the state is q0q_0. Since ⊔∉Σ\sqcup \notin \Sigma, the first blank marks where the input ends.

core

Front

Transition δ(q1,a)=(q2,x,R)\delta(q_1, a) = (q_2, x, R): what the step does

Back

Reading a in state q1q_1, the machine replaces that a by x, steps one cell right and continues in q2q_2. 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

LL is co-recognisable if its complement L‾\overline{L} is recognisable: some machine accepts exactly the words that are not in LL.

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 LL is decidable exactly when both LL and   are recognisable.

Back

A language LL is decidable exactly when both LL and L‾\overline{L} are recognisable.

core · So if LL is recognisable but undecidable, L‾\overline{L} is not recognisable, as for ATMA_{\mathrm{TM}}.

5 Complexity

441 cards

Front

Running time of a deterministic Turing machine: definition

Back

For a decider MM, the function t:N→Nt : \mathbb{N} \to \mathbb{N} where t(n)t(n) is the largest number of steps MM takes on any input of length nn. One says MM runs in time t(n)t(n), or is a t(n)t(n)-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 nn

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 nn steps on inputs starting with 0 and 2n2^n steps on inputs starting with 1: its running time

Back

t(n)=2nt(n) = 2^n for n≥1n \ge 1: the running time is the maximum over all inputs of length nn, and half of them take 2n2^n 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,s}\{e, s\}: 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 LL is the set of words that contain ee or ese. The team drew the NFA NN with states 0 to 3, start state 0 and accepting state 3:

  • δ(0,e)={0,1}\delta(0, e) = \{0, 1\} and δ(0,s)={0}\delta(0, s) = \{0\}: wait, or guess that this error starts the alarm;
  • δ(1,e)={3}\delta(1, e) = \{3\} and δ(1,s)={2}\delta(1, s) = \{2\}: an error has just been read;
  • δ(2,e)={3}\delta(2, e) = \{3\} and δ(2,s)=∅\delta(2, s) = \emptyset: an error and one success have been read;
  • δ(3,e)=δ(3,s)={3}\delta(3, e) = \delta(3, s) = \{3\}: the alarm has been raised.

The subset construction runs the deck's worklist procedure, with e before s; the sets are named AA, BB, CC, … in the order they are found. For a stricter rule, "two errors with at most kk successes between them", the analogous NFA NkN_k has states 0 to k+1k + 1 and an accepting state k+2k + 2: 0 loops on both letters and guesses an error into 1, state ii moves to i+1i + 1 on s for i≤ki \le k, and each of the states 1 to k+1k + 1 moves to k+2k + 2 on e, which loops.

1.

1.1 Run the subset construction on the alarm NFA NN: the reachable sets, their transitions, and the accepting sets. (3 points)

2.

1.2 Minimise the subset DFA of the alarm NFA NN by table filling: the pairs marked at the start and in each pass, and the minimal DFA. (3 points)

3.

1.3 Show with the Myhill–Nerode theorem that no DFA for the alarm language LL, the words containing ee or ese, has fewer than 4 states. (2 points)

4.

1.4 Give a regular expression for the logs that raise no alarm, the complement of the alarm language LL, and say why it is right. (2 points)

5.

1.5 For the stricter alarm rule with at most kk successes between two errors, how many sets does the subset construction build from the NFA NkN_k, and how many states does the minimal DFA have? (2 points)

Back

1.

1.1 Run the subset construction on the alarm NFA NN: 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 A={0}A = \{0\}. On e it goes to {0,1}\{0, 1\}, new as BB; on s it stays at AA. From BB, e gives δ(0,e)∪δ(1,e)={0,1,3}\delta(0, e) \cup \delta(1, e) = \{0, 1, 3\}, new as CC, and s gives {0,2}\{0, 2\}, new as DD. From CC, e gives CC again and s gives {0,2,3}\{0, 2, 3\}, new as EE. From DD, e gives {0,1}∪{3}=C\{0, 1\} \cup \{3\} = C and s gives {0}=A\{0\} = A, since 2 has no move on s. From EE, e gives CC and s gives {0,3}\{0, 3\}, new as FF; from FF, e gives CC and s gives FF. Nothing new appears: the DFA has 6 states, and CC, EE and FF accept. The other 10 subsets, such as {1,2}\{1, 2\} or ∅\emptyset, never occur, because 0 is in every set: the NFA can always keep waiting.

2.

1.2 Minimise the subset DFA of the alarm NFA NN 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 ε\varepsilon.
  • Pass 1: e sends AA to BB but BB and DD to CC, so {A,B}\{A, B\} and {A,D}\{A, D\} lead to the marked pair {B,C}\{B, C\}; their witness is e. {B,D}\{B, D\} goes to CC and CC on e and to the unmarked {D,A}\{D, A\} on s.
  • Pass 2: {D,A}\{D, A\} is now marked, so {B,D}\{B, D\} is marked with witness se: e followed by se gives ese, an alarm, and es followed by se gives esse, none.
  • Pass 3 marks nothing. Every letter takes CC, EE and FF to CC, EE or FF again, so their pairs are never marked.

The minimal DFA has 4 states: AA (no error pending), BB (an error just read), DD (an error and then one success) and the merged alarm state {C,E,F}\{C, E, F\}, which loops on both letters. AA goes to BB on e and stays on s; BB goes to the alarm state on e and to DD on s; DD goes to the alarm state on e and back to AA on s. Once the alarm is raised, nothing more needs remembering.

3.

1.3 Show with the Myhill–Nerode theorem that no DFA for the alarm language LL, 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 ε\varepsilon, e, es and ee. ee is in LL and the others are not, so the empty suffix separates ee from each of them. The suffix e separates ε\varepsilon from e (e against ee) and from es (e against ese). The suffix se separates e from es: ese is in LL, esse is not. So ≡L\equiv_L has at least four classes, and every DFA for LL needs at least 4 states; the minimal DFA from table filling has exactly 4.

4.

1.4 Give a regular expression for the logs that raise no alarm, the complement of the alarm language LL, 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: s∗(ε∪e(sss∗e)∗s∗)s^*(\varepsilon \cup e(sss^*e)^*s^*). A log without an alarm consists only of successes, or it has errors separated by blocks of at least two successes, sss∗sss^*, with any number of successes before the first error and after the last; the expression lists exactly these words. Equivalent forms are s∗(esss∗)∗(ε∪es∗)s^*(esss^*)^*(\varepsilon \cup es^*) and (s∪esss∗)∗(ε∪es∗)(s \cup esss^*)^*(\varepsilon \cup es^*). A quick test: e, esse and ssess match, while ese and seess don't.

5.

1.5 For the stricter alarm rule with at most kk successes between two errors, how many sets does the subset construction build from the NFA NkN_k, 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: 2k+42k + 4 sets, k+3k + 3 states. Every reachable set contains 0. Without an alarm it holds at most one other state ii, the position reached since the last error: {0}\{0\}, {0,1}\{0, 1\}, …, {0,k+1}\{0, k + 1\}, which is k+2k + 2 sets. After an alarm, k+2k + 2 joins, beside 00 and possibly one ii: another k+2k + 2 sets. A suffix sjes^j e raises the alarm from {0,i}\{0, i\} exactly when i+j≤k+1i + j \le k + 1, so the waiting sets are pairwise distinguishable, while every accepting set accepts every continuation. So the minimal DFA has the k+2k + 2 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,k}\{v, k\}: 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 are
H={w∈{v,k}∗∣∣u∣v≥∣u∣k for every prefix u of w}.H = \{w \in \{v, k\}^* \mid |u|_v \ge |u|_k \text{ for every prefix } u \text{ of } w\}.
vvkvk is valid; vkk is not, as the second back press has nowhere to go. Let KK 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 EE.

1.

2.1 Prove with the pumping lemma that the valid browser logs HH are not regular. (4 points)

2.

2.2 A classmate's proof that the valid browser logs HH are not regular starts from the word (vk)p(vk)^p. Why can't it succeed, whatever ii it pumps with? (1 point)

3.

2.3 Build the Thompson NFA for KK, the logs that contain kk, from the expression (v∪k)∗kk(v∪k)∗(v \cup k)^*kk(v \cup k)^* with the deck's fragments: how many states, moves on letters and ε\varepsilon-moves does it have, and which states make up the ε\varepsilon-closure of its start state? (2 points)

4.

2.4 Give the minimal DFA for the kiosk language EE, the logs that end with an empty back history when at most three pages are kept, and say why EE is regular although HH is not. (2 points)

5.

2.5 Is H∪KH \cup K regular, where HH is the set of valid browser logs and KK the set of logs that contain kk? Prove your answer. (2 points)

Back

1.

2.1 Prove with the pumping lemma that the valid browser logs HH 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 HH were regular, with pumping length pp. The word s=vpkps = v^p k^p is in HH, since no prefix has more ks than vs, and ∣s∣=2p≥p|s| = 2p \ge p. Take any split s=xyzs = xyz with ∣xy∣≤p|xy| \le p and ∣y∣≥1|y| \ge 1. The first pp letters are vs, so y=vjy = v^j with 1≤j≤p1 \le j \le p. Pumping down gives xz=vp−jkpxz = v^{p-j} k^p, whose whole word is a prefix with pp back presses after only p−jp - j visits, so xz∉Hxz \notin H. This holds for every allowed split, contradicting the pumping lemma; HH is not regular.

2.

2.2 A classmate's proof that the valid browser logs HH are not regular starts from the word (vk)p(vk)^p. Why can't it succeed, whatever ii 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 (vk)p(vk)^p has one it can't defeat: for p≥2p \ge 2, take x=εx = \varepsilon, y=vky = vk and z=(vk)p−1z = (vk)^{p-1}. Then ∣xy∣=2≤p|xy| = 2 \le p, and xyiz=(vk)p−1+ixy^iz = (vk)^{p-1+i} alternates visits and back presses, so it is a valid log for every ii, pumped down or up. The word has to be chosen so that its first pp letters can only be visits, as in vpkpv^p k^p.

3.

2.3 Build the Thompson NFA for KK, the logs that contain kk, from the expression (v∪k)∗kk(v∪k)∗(v \cup k)^*kk(v \cup k)^* with the deck's fragments: how many states, moves on letters and ε\varepsilon-moves does it have, and which states make up the ε\varepsilon-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 ε\varepsilon-moves. The six letters v, k, k, k, v, k give 12 states with one move each; each of the two unions v∪kv \cup k and each of the two stars adds 2 states and 4 ε\varepsilon-moves, 8 states and 16 ε\varepsilon-moves in all; and each of the three concatenations adds one ε\varepsilon-move. The ε\varepsilon-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 ε∉K\varepsilon \notin K, and a log may begin with either letter.

4.

2.4 Give the minimal DFA for the kiosk language EE, the logs that end with an empty back history when at most three pages are kept, and say why EE is regular although HH 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 d<d′d < d', the suffix kdk^d empties the history from dd but not from d′d', so all four states are needed. EE is regular because the kiosk forgets everything beyond three pages: its memory is bounded by design, while deciding HH needs an unbounded count of the pages to return to.

5.

2.5 Is H∪KH \cup K regular, where HH is the set of valid browser logs and KK 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 ww that contains no kk. If it starts with k, its first letter already breaks HH. 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 w∈Hw \in H. So the logs outside H∪KH \cup K are exactly those that start with k and contain no kk, and
H∪K=ε∪v(v∪k)∗∪(v∪k)∗kk(v∪k)∗,H \cup K = \varepsilon \cup v(v \cup k)^* \cup (v \cup k)^*kk(v \cup k)^*,
a regular language. Adding the regular KK covers exactly the part of HH that needed counting.

Front

Exercise 3: A microwave oven's event log

A microwave oven reports events as a word over {s,o,t}\{s, o, t\}: s for the start button, o for opening the door, t for the timer running out. Its controller is a DFA with the states II (idle, the start state), RR (running) and PP (paused), and II is the only accepting state, so the language is the set of logs that leave the oven idle:

  • δ(I,s)=R\delta(I, s) = R and δ(I,o)=δ(I,t)=I\delta(I, o) = \delta(I, t) = I;
  • δ(R,s)=R\delta(R, s) = R (another 30 seconds), δ(R,o)=P\delta(R, o) = P and δ(R,t)=I\delta(R, t) = I;
  • δ(P,s)=R\delta(P, s) = R (resume, once the door is shut) and δ(P,o)=δ(P,t)=P\delta(P, o) = \delta(P, t) = P.

State elimination follows the deck: a new start state SS with S→εIS \xrightarrow{\varepsilon} I and a new accepting state FF with I→εFI \xrightarrow{\varepsilon} F, parallel moves joined by ∪\cup, and, when qq is eliminated, the label Rpr∪Rpq(Rqq)∗RqrR_{pr} \cup R_{pq}(R_{qq})^*R_{qr} for every pair pp, rr of remaining states.

1.

3.1 Turn the microwave DFA into a regular expression by state elimination, removing PP, then RR, then II: the labels created at each step and the final expression. (4 points)

2.

3.2 Eliminate the microwave DFA's states in the order RR, PP, II instead. Which expression results? (2 points)

3.

3.3 A technician summarises the microwave's idle-ending logs as (o∪t∪ss∗t)∗(o \cup t \cup ss^*t)^*. Find the shortest log on which this expression and the DFA disagree, and say which of the two languages contains the other. (2 points)

4.

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 EE (even, the start) and OO (odd), and give its accepting pairs for "idle and even" and for "idle or even". (2 points)

Back

1.

3.1 Turn the microwave DFA into a regular expression by state elimination, removing PP, then RR, then II: 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 S→εIS \xrightarrow{\varepsilon} I and I→εFI \xrightarrow{\varepsilon} F, and join parallel moves, so II and PP each carry a loop o∪to \cup t. Every state can reach FF.
  • Remove PP: its only neighbour is RR, with R→oPR \xrightarrow{o} P and P→sRP \xrightarrow{s} R, so RR's loop becomes s∪o(o∪t)∗ss \cup o(o \cup t)^*s: a pause, any events while paused, then a restart.
  • Remove RR: the path I→sR→tII \xrightarrow{s} R \xrightarrow{t} I, with RR's loop in between, adds s(s∪o(o∪t)∗s)∗ts(s \cup o(o \cup t)^*s)^*t to II's loop, which becomes o∪t∪s(s∪o(o∪t)∗s)∗to \cup t \cup s(s \cup o(o \cup t)^*s)^*t.
  • Remove II: S→εI→εFS \xrightarrow{\varepsilon} I \xrightarrow{\varepsilon} F with that loop gives
    (o∪t∪s(s∪o(o∪t)∗s)∗t)∗.(o \cup t \cup s(s \cup o(o \cup t)^*s)^*t)^*.

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.

2.

3.2 Eliminate the microwave DFA's states in the order RR, PP, II 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: RR has the loop ss, two entries, I→sRI \xrightarrow{s} R and P→sRP \xrightarrow{s} R, and two exits, R→oPR \xrightarrow{o} P and R→tIR \xrightarrow{t} I. Removing it touches four pairs: II's loop gains ss∗tss^*t, I→PI \to P becomes ss∗oss^*o, P→IP \to I becomes ss∗tss^*t, and PP's loop gains ss∗oss^*o. Removing PP then adds ss∗o(o∪t∪ss∗o)∗ss∗tss^*o(o \cup t \cup ss^*o)^*ss^*t to II's loop, and removing II gives
(o∪t∪ss∗t∪ss∗o(o∪t∪ss∗o)∗ss∗t)∗.(o \cup t \cup ss^*t \cup ss^*o(o \cup t \cup ss^*o)^*ss^*t)^*.
It describes the same logs. Removing PP first, the state with fewer moves, gives the shorter expression.

3.

3.3 A technician summarises the microwave's idle-ending logs as (o∪t∪ss∗t)∗(o \cup t \cup ss^*t)^*. 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: I→sR→oP→sR→tII \xrightarrow{s} R \xrightarrow{o} P \xrightarrow{s} R \xrightarrow{t} I. 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 PP is a sequence of the blocks oo, tt and ss∗tss^*t, and a log that enters PP and returns to II needs s, o, s and t at least. Every word of the expression is accepted by the DFA, because each of the blocks oo, tt and ss∗tss^*t leads from II back to II; so the technician's language is a proper subset of the oven's. It forgets the door.

4.

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 EE (even, the start) and OO (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 (I,E)(I, E); on each letter both components move at once. s takes (q,x)(q, x) to (R,x)(R, x); o takes II to II, RR to PP and PP to PP and flips the parity; t takes II to II, RR to II and PP to PP and keeps it. From (I,E)(I, E), s reaches (R,E)(R, E), o reaches (I,O)(I, O), and from those o gives (P,O)(P, O), s gives (R,O)(R, O), and o from (P,O)(P, O) gives (P,E)(P, E): all six pairs are reachable. For the intersection the only accepting pair is (I,E)(I, E); for the union, every pair with II or with EE: (I,E)(I, E), (I,O)(I, O), (R,E)(R, E) and (P,E)(P, E). 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…