Midterm 1 study guide

Exam at a glance

Midterm 1 was written on Thursday, October 8: 29 five-option multiple-choice questions on Sipser Chapter 0, all of Chapter 1, and the start of Chapter 2, plus what the lectures covered. Bring HB pencils and an eraser, arrive early, and print your first and last names in capitals on both the bubble sheet and the question paper.

What the Oct 6 practice test tells us

The prof said the midterm questions would be similar to the practice test, and they were. It shows his format: five choices (a)–(e), shared setups (one NFA or DFA table used for two or three questions), automata given as transition tables, and minimization asked in terms of partitions. Option (e) is often “None of the above” or “Both (a) and (b)”, and Q8’s answer was (e).

Nothing on it covered regular expressions or the pumping lemma, but both are on the announcement, so don’t skip them. Take the practice test under exam timing, or quiz yourself on 70 questions in the same style.

Questions from the real midterm

Questions 8–29 of the Oct 8 midterm were captured in photos (1–7 were not). Themes it added beyond the practice test: reading functions from tables, naming the conversion methods, deciding FA equivalence, intersecting regex languages, and a large ε-NFA worked through subset construction, minimization and back to a regex. Retake them under exam timing or quiz yourself on them.

How the topics fit together

The arrows form a cycle (regex → NFA → DFA → regex), which is why all three describe exactly the regular languages. CFGs generate a strictly larger class; the pumping lemma shows a language is outside the regular box.

Topic 1: Mathematical preliminaries

Chapter 0 and the first lecture supply the vocabulary every later question uses. Expect quick definition, set-calculation and counting questions.

The three areas of the theory

Sets

• A set is unordered with no repeats: {7, 21, 57} = {57, 7, 21, 21}. A multiset counts repeats.
• A ⊆ B: every element of A is in B. A ⊊ B (proper subset) also needs A ≠ B. For every set A, ∅ ⊆ A and A ⊆ A.
• X = Y if and only if X ⊆ Y and Y ⊆ X.
• Union, intersection, difference X − Y, complement X̄ = U − X relative to a universe U.
• De Morgan: the complement of X ∪ Y is X̄ ∩ Ȳ; the complement of X ∩ Y is X̄ ∪ Ȳ.
• Power set P(X), also written 2^X in class: all subsets of X. |P(X)| = 2^|X|. P(∅) = {∅} has one element.
• Cardinality |S| counts top-level elements only: |{a, {a, b}, {a, {a, b, c}}}| = 3.

Tuples, functions and relations

• A sequence or tuple is ordered and may repeat: (7, 21, 57) ≠ (57, 7, 21).
• Cartesian product X × Y = {(x, y) | x ∈ X, y ∈ Y}; |X × Y| = |X|·|Y|. With X = {1, 2} and Y = {a, b, c}, X × Y has 6 pairs, each starting with 1 or 2.
• A function f: D → R maps each input to exactly one output. One-to-one: distinct inputs give distinct outputs. Onto: every element of R is hit. Correspondence: both. There are |B|^|A| functions from A to B.
• A function on X × Y can be shown as a table. The class example g: Z₄ × Z₄ → Z₄ is addition mod 4, so g(3, 2) = 1.
• A binary relation on X and Y is a subset of X × Y; an n-ary relation is a subset of X₁ × … × Xₙ. A predicate is a function to {TRUE, FALSE}.
• An equivalence relation is reflexive, symmetric and transitive.

Graphs

• Degree of a node = number of edges at it. The sum of all degrees = 2|E|.
• Path, simple path (no repeated nodes), connected, cycle, simple cycle (at least 3 nodes).
• A tree is connected with no simple cycles; n nodes ⇒ n − 1 edges.
• Directed graphs have indegree and outdegree; strongly connected means a directed path joins every ordered pair. A DFA’s state diagram is a labelled directed graph.

Strings and languages

• Alphabet Σ: a nonempty finite set of symbols. String: a finite sequence of symbols. Language: a set of strings.
• |w| is the length; the empty string ε has |ε| = 0.
• Concatenation xy; w^k = w repeated k times, w⁰ = ε; reversal w^R (abd^R = dba).
• Prefix x of w = xz, suffix z, substring: consecutive symbols. aaabc has 6 prefixes (ε through aaabc).
• Shortlex order: by length, then dictionary order: ε, 0, 1, 00, 01, 10, 11, 000, …
• A language is prefix-free if no member is a proper prefix of another member.

Boolean logic

• P → Q is false only when P is true and Q is false; it equals ¬P ∨ Q.
• Contrapositive ¬Q → ¬P is equivalent to P → Q. The converse Q → P is not.
• De Morgan: ¬(P ∧ Q) = ¬P ∨ ¬Q; ¬(P ∨ Q) = ¬P ∧ ¬Q.

Recursive definitions

Proofs and induction

• Definition, theorem, lemma, corollary. “P if and only if Q” needs both P ⇒ Q and Q ⇒ P.
• Construction: build the object (a 3-regular graph on every even n > 2 nodes).
• Contradiction: assume the statement is false and derive the impossible (√2 is irrational). Pumping-lemma proofs work this way.
• Induction: basis P(b); induction hypothesis P(k); inductive step P(k) ⇒ P(k + 1). Without a basis the proof is invalid.

Quiz Topic 1 or drill its flashcards.

Topic 2: Finite automata

A DFA reads its input once, left to right, with fixed finite memory (its current state), and accepts if it ends in an accept state. DFAs recognize exactly the regular languages.

Formal definition and computation

A DFA is a 5-tuple M = (Q, Σ, δ, q₀, F):

M accepts w = w₁…wₙ if there are states r₀, …, rₙ with r₀ = q₀, rᵢ₊₁ = δ(rᵢ, wᵢ₊₁), and rₙ ∈ F. L(M) is the language M recognizes; M accepts ε exactly when q₀ ∈ F. A missing arrow is not allowed in a DFA: add a dead state that loops on every symbol.

Designing DFAs

Ask what you must remember about the prefix read so far; each distinct thing to remember is one state.

Worked example, strings containing 001:

Regular operations and the product construction

• Union A ∪ B; concatenation A ∘ B = {xy | x ∈ A, y ∈ B}; star A* = {x₁…xₖ | k ≥ 0, xᵢ ∈ A}. A* always contains ε, so ∅* = {ε}.
• |A ∘ B| ≤ |A|·|B|: different pairs can give the same string. {ab, a} ∘ {b, bb} = {ab, abb, abbb}.

Theorem 1.25 (closure under union): run both DFAs in parallel. States Q₁ × Q₂; δ((r₁, r₂), a) = (δ₁(r₁, a), δ₂(r₂, a)); start (q₁, q₂). Change only the accept states for related operations:

DFA minimization From lecture

Not in the assigned Sipser pages, but covered in two lectures. Every regular language has a unique minimum-state DFA up to renaming states (isomorphism), so two DFAs are equivalent exactly when their minimized versions match.

1. Remove states that cannot be reached from the start state.
2. Merge equivalent states.

States p and q are equivalent if for every string w, reading w from p ends in an accept state exactly when reading w from q does. Otherwise they are distinguishable.

Method 1: partition refinement (the practice test’s method)

The practice test asks for the “initial partition”, so expect questions phrased this way.

1. Initial partition: two groups, the non-accepting states Q − F and the accepting states F.
2. Signatures: for each state, write which group each symbol sends it to.
3. Split any group whose members have different signatures.
4. Repeat until a round changes nothing. Each group is one state of the minimal DFA.

Practice test Q7–8. Start q₀, F = {q₂, q₃}:

Initial partition {{q₀, q₁}, {q₂, q₃}} (Q7, answer b). Signatures match within each group, so nothing splits: q₀ ≡ q₁ and q₂ ≡ q₃ (Q8, answer e, “Both (a) and (b)”). The minimal DFA has 2 states and accepts strings with an odd number of 1s.

Watch for a DFA that needs more than one round. With the counter q₀ → q₁ → q₂ → q₃ → q₀ on 1 (loops on 0) and F = {q₀}: round 0 gives {q₀}, {q₁, q₂, q₃}; round 1 splits off q₃ (it reaches q₀ on 1); round 2 splits q₁ from q₂. All 4 states survive. Same table with F = {q₀, q₂} gives 2 states.

Method 2: table filling

The lecture slides also show the table-filling (Myhill–Nerode) method. It finds the same answer by marking every distinguishable pair:

• Basis: mark {p, q} when exactly one of them is accepting.
• Inductive step: mark {p, q} when, for some symbol a, the pair {δ(p, a), δ(q, a)} is already marked.
• Repeat until nothing changes. Unmarked pairs are equivalent; merge them.

Worked example (class). Accept states A and C:

Basis marks every accepting/non-accepting pair: {A,B}, {A,D}, {B,C}, {C,D}. Check {A,C}: on 0 they go to {B,D}, on 1 to {C,A}; neither pair is marked. Check {B,D}: on 0 → {A,C}, on 1 → {D,B}; unmarked. Nothing new gets marked, so A ≡ C and B ≡ D. The minimal DFA has 2 states and accepts strings with an even number of 0s.

Larger class example. States a–h, start a, accept c:

Result: [a, e], [b, h], [d, f], [c], [g], five states. d is unreachable from a, so step 1 removes it anyway. a and b are distinguished by the string 1 (a → f rejects, b → c accepts).

Quiz Topic 2 or drill its flashcards.

Topic 3: NFAs and regular expressions

NFAs

An NFA may have zero, one or many moves on a symbol, plus ε-moves, and accepts if any branch ends in an accept state. Think of parallel threads, a tree of branches, or a machine that always guesses right.

Acceptance: w = y₁…yₘ with each yᵢ ∈ Σ_ε, and states r₀ = q₀, rᵢ₊₁ ∈ δ(rᵢ, yᵢ₊₁), rₘ ∈ F. Every DFA is already an NFA. NFAs can be much smaller: “third symbol from the end is 1” needs 4 NFA states but 8 DFA states (generally k + 1 versus 2^k).

NFA → DFA: subset construction

• ε-closure E(R): states reachable from R by zero or more ε-arrows.
• DFA states: subsets of Q (at most 2^k). Start: E({q₀}).
• δ′(R, a) = E(union of δ(r, a) over r ∈ R).
• Accept: every subset containing at least one NFA accept state. ∅ is the dead state.

Example: NFA for strings ending in 01 (p loops on 0, 1; p → q on 0; q → r on 1; accept r) gives reachable subsets {p}, {p, q}, {p, r}, with {p, r} accepting. Corollary 1.40: a language is regular if and only if some NFA recognizes it.

Regular expressions

R is a regular expression if it is a (for a ∈ Σ), ε, ∅, R₁ ∪ R₂, R₁R₂, or R₁*. R⁺ = RR*. Precedence: star, then concatenation, then union, so ab* ∪ c = (a(b*)) ∪ c.

Regex → NFA (Lemma 1.55, p. 67): a is two states with one a-arrow; ε is one accepting state; ∅ is one non-accepting state; then use the union, concatenation and star constructions. For (ab ∪ a)*, build a and b, concatenate, union with a, then star last.

DFA → regex via GNFAs

A GNFA labels arrows with regular expressions and is put in special form: the start state has only outgoing arrows; one accept state, different from the start, has only incoming arrows; every other pair has one arrow each way (∅ for “none”).

1. From a k-state DFA, add a new start (ε to the old start) and a new accept state (ε from old accept states): k + 2 states.
2. Rip out states one at a time; the last label is the answer.

new label(qᵢ → qⱼ) = (R₁)(R₂)*(R₃) ∪ (R₄)

R₁: qᵢ → q_rip, R₂: q_rip’s self-loop, R₃: q_rip → qⱼ, R₄: the direct arrow qᵢ → qⱼ. Example: state 1 (start) loops on a, goes to 2 on b; state 2 (accept) loops on a, b. Rip 2: b(a ∪ b)*. Rip 1: a*b(a ∪ b)*. A different rip order gives an equivalent regex that may look different.

Lexical analysis From lecture

The lexical analyzer is the first phase of a compiler: it reads characters and outputs tokens for the parser. Tools such as grep, lex, sed and awk turn a regex into a DFA to scan text.

• Lex notation writes union as |. Precedence: * highest, then concatenation, then |; all left associative. (a)|((b)*(c)) = a|b*c.
• Shorthand: r⁺ = rr*, r* = r⁺ | ε, r? = r | ε, [abc] = a | b | c, [a–z] = a | … | z.
• Identifier: [A–Za–z][A–Za–z0–9]*. So x1 is an identifier and 9abc is not.
• A regular definition d₁ → r₁, …, dₙ → rₙ lets each rᵢ use basic symbols and earlier names d₁ … dᵢ₋₁ only.
• Thompson’s construction turns a regex into an NFA (the same idea as Lemma 1.55).

Quiz Topic 3 or drill its flashcards.

Topic 4: Pumping lemma and CFGs

The pumping lemma

If A is regular, there is a number p (the pumping length) such that every s ∈ A with |s| ≥ p can be split s = xyz with:

1. xyⁱz ∈ A for every i ≥ 0;
2. |y| > 0;
3. |xy| ≤ p.

Why it is true. A DFA with p states reading at least p symbols visits at least p + 1 states, so by the pigeonhole principle some state repeats within the first p symbols. The loop between visits is y.

It is a necessary condition only: use it to prove a language is not regular, never to prove one is.

Also regular: any finite language (such as {0ⁿ1ⁿ | n ≤ 100}), 0*1*, and counting mod k. Common mistakes: choosing p or the split yourself, choosing s ∉ A or shorter than p, and forgetting i = 0.

Context-free grammars

A CFG is a 4-tuple. Sipser writes (V, Σ, R, S); the lectures write (V, T, P, S): variables, terminals, productions, start variable. Every rule is A → α with A a single variable and α ∈ (V ∪ T)*. A → α₁ | α₂ | … is shorthand for several rules.

• α ⇒ β: one rule applied once. α ⇒* β: zero or more steps.
• L(G) = {w ∈ T* | S ⇒* w}: strings of terminals only, derived from S. Such a language is context-free.
• CFGs began as a way to describe natural language: ⟨sentence⟩ → ⟨noun phrase⟩ ⟨verb phrase⟩.

aⁿbⁿ, n ≥ 1:            S → aSb | ab
0ᵏ1ᵏ, k ≥ 0 (G₁):       S → 0S1 | R      R → ε
0ᵃ1ᵃ0ᵇ1ᵇ (G₂):          S → RR           R → 0R1 | ε
Balanced parentheses:   S → SS | (S) | ε
Palindromes over {a,b}: S → aSa | bSb | a | b | ε
Equal a’s and b’s (≥1): S → aB | bA   A → a | aS | bAA   B → b | bS | aBB
aⁱbʲ with i ≥ j:        S → aS | T       T → aTb | ε
Arithmetic (class G₃):  E → E + E | E − E | (E) | V     V → x | y | z

In G₃ the variables are {E, V} and the terminals are {+, −, (, ), x, y, z}.

Derivations and parse trees From lecture

Deriving x + (y − z) in G₃:

Both derivations give the same parse tree. Its rules: the root is labelled S; every internal vertex is a variable; if a vertex A has children X₁…Xₖ then A → X₁…Xₖ is a production; a vertex labelled ε is a leaf with no siblings. Reading the leaves left to right gives the yield.

Designing grammars, ambiguity, CNF

• Union: S → S₁ | S₂. From a DFA: Rᵢ → aRⱼ when δ(qᵢ, a) = qⱼ, Rᵢ → ε for accept states, start R₀. So every regular language is context-free. Linked parts: R → uRv. Nesting: let a variable appear inside its own rules.
• Practice test Q9 showed these two trees for a + a × a and asked what they prove: the grammar is ambiguous, because one string has two distinct parse trees.
• A grammar is ambiguous if some string has two parse trees, equivalently two leftmost derivations. The class grammar E → E + E | E * E | (E) | id is ambiguous: id + id * id groups two ways. Two different derivations alone prove nothing.
• A language is inherently ambiguous if every grammar for it is ambiguous, e.g. {aⁱbʲcᵏ | i = j or j = k}.
• Chomsky normal form (A → BC or A → a, plus S → ε) starts around page 107 and is not in the lecture slides. Low priority.

Quiz Topic 4 or drill its flashcards.

Cheat sheet and traps

• Swapping accept states complements a DFA, never an NFA.
• Forgetting the ε-closure of the start state in the subset construction.
• A* always contains ε. Finite languages are always regular.
• In pumping proofs, the adversary picks p and the split; you pick s and i.
• Converse ≠ contrapositive. Induction needs a basis.

Take a timed practice exam when you’re ready.