Notes
Final 15-question mixed warm-up before the pattern drill and full-length mock test.
Practice questions
- NAT · 2 marks
Over Σ = {0, 1}, what is the number of states in the minimal DFA that accepts binary strings (read MSB to LSB, empty string rejected or value 0 accepted) representing numbers divisible by 3, assuming ε is accepted as value 0?
Write your answer before opening the key.
- NAT · 2 marks
How many binary strings of length 5 over {0, 1} do NOT contain
11as a substring?Write your answer before opening the key.
- MCQ · 2 marks
For the language L = { w ∈ {a, b}* | |w|a ≡ 0 (mod 3) and |w|b ≡ 0 (mod 4) }, what is the index (number of equivalence classes) of the Myhill–Nerode relation ≡L?
- 7
- 12
- 81
- Infinite
- MSQ · 2 marks
Let N = (Q, Σ, δ, q₀, F) be an NFA. We form N′ = (Q, Σ, δ, q₀, Q − F) by swapping accepting and non-accepting states. Which statements are TRUE?
- L(N′) is always the complement of L(N)
- A string w can be accepted by both N and N′
- A string w can be rejected by both N and N′
- If N is already a complete DFA, then L(N′) = Σ* − L(N)
- MCQ · 1 mark
Using strict Thompson construction (2 states per symbol occurrence, +2 per union, +2 per star, 0 added for concatenation), how many states are in the ε-NFA for
(ab + c)*?- 8
- 10
- 6
- 12
- MCQ · 2 marks
After removing ε-productions from S → aAb | c, A → aA | ε, what are the resulting productions for S?
- S → aAb | c
- S → aAb | ab | c
- S → aAb | a | b | c
- S → ab | c
- NAT · 2 marks
In a CNF grammar, a parse tree has height 6 (measured as the maximum number of edges on a root-to-leaf path, where the last edge is A → a). What is the maximum possible length of the terminal string yielded by this tree?
Write your answer before opening the key.
- MCQ · 2 marks
A PDA has start state q₀, stack start symbol Z, state q₁, and transitions: (q₀, a, Z) → (q₀, AAZ), (q₀, a, A) → (q₀, AAA), (q₀, b, A) → (q₁, ε), (q₁, b, A) → (q₁, ε), (q₁, ε, Z) → (q₁, ε) with acceptance by empty stack. What is N(P)?
- { aⁿb²ⁿ | n ≥ 1 }
- { a²ⁿbⁿ | n ≥ 1 }
- { aⁿbⁿ | n ≥ 1 }
- { aⁿb²ⁿ | n ≥ 0 }
- MSQ · 2 marks
Which of the following languages are Context-Sensitive (CSL) but NOT Context-Free (CFL)?
- { aᵖ | p is prime }
- { aⁿbⁿcⁿ | n ≥ 1 }
- { wwᴿ | w ∈ {a,b}* }
- { w ∈ {a,b,c}* | |w|ₐ = |w|_b = |w|_c }
- MCQ · 2 marks
Why is the diagonal language Ld = { wi | Mi does not accept wi } NOT Recursively Enumerable?
- Because any TM M_k for L_d would give a contradiction on input w_k: w_k ∈ L(M_k) ⇔ w_k ∉ L_d
- Because L_d is finite
- Because every complement of an RE language is RE
- Because M_i always halts on w_i
- MSQ · 2 marks
For which of the following languages of TM descriptions does Rice’s theorem directly prove undecidability?
- { ⟨M⟩ | L(M) is finite }
- { ⟨M⟩ | L(M) contains at least two strings }
- { ⟨M⟩ | L(M) is a Context-Free Language }
- { ⟨M⟩ | M has fewer than 20 states }
- MCQ · 2 marks
Let L₁ = ATM and L₂ = { ⟨M⟩ | L(M) = ∅ } (the emptiness problem ETM). Which statement is TRUE?
- Both L₁ and L₂ are RE
- L₁ is RE (not REC), and L₂ is co-RE (not RE)
- Both L₁ and L₂ are neither RE nor co-RE
- L₁ ≤_m L₂ holds
- MCQ · 1 mark
For Deterministic Context-Free Languages (DCFLs) L₁ and L₂ given by DPDAs, which problem is UNDECIDABLE?
- Emptiness: L₁ = ∅?
- Universality: L₁ = Σ*?
- Equivalence: L₁ = L₂?
- Inclusion: L₁ ⊆ L₂?
- MSQ · 1 mark
Let L ⊆ {a}* be a unary language (over a 1-letter alphabet). Which statements are ALWAYS true?
- If L is a CFL, then L is regular
- L is regular iff the set { n | aⁿ ∈ L } is eventually periodic
- { a^{n²} | n ≥ 0 } is a CFL
- Lᴿ = L
- NAT · 1 mark
On a set S of 5 elements, an equivalence relation R partitions S into 3 equivalence classes of sizes 2, 2, and 1. How many ordered pairs (x, y) belong to R?
Write your answer before opening the key.
Answer key
Reveal answers when you’re ready
- 3 — Tracking value mod 3 uses 3 states: remainder 0 (start and accepting), remainder 1, remainder 2. All 3 have distinct futures (0 accepts ε, 1 accepts "1", 2 accepts "01"), so 3 is minimal.
- 13 — For length n = 0, 1, 2, 3, 4, 5, the count of binary strings without "11" follows the Fibonacci sequence 1, 2, 3, 5, 8, 13. For n = 5, the answer is 13.
- B — Two prefixes x and y have the same future iff they have the same (#a mod 3) and (#b mod 4). Every pair (i, j) ∈ {0,1,2} × {0,1,2,3} is separated from every other pair by a continuation a^(3−i) b^(4−j). Thus there are 3 × 4 = 12 equivalence classes.
- A: Remainders combine multiplicatively (grid), not additively.
- C: 3⁴ = 81 is not the remainder grid.
- D: L is regular, so the index is finite.
- BCD — Because an NFA can have multiple computation paths on w (some ending in F, some in Q − F) or zero paths (dying early), swapping F does NOT complement an NFA: w can have one path to F and one to Q − F (accepted by both), or all paths die before reading w (rejected by both). For a complete DFA, there is a unique path, so swapping F gives the exact complement.
- A: Fails whenever w has multiple paths with mixed verdicts or zero complete paths.
- B — a (2) + b (2) = 4 for ab; c (2); union ab + c adds 2 → 4 + 2 + 2 = 8; outer star adds 2 → 10 states.
- A: Forgets either the union or star states.
- C: Counts only symbols.
- D: Adds 2 for concatenation, which strict Thompson does not.
- B — Only A is nullable (A ⇒* ε). In S → aAb, we keep A (giving S → aAb) and drop A (giving S → ab), alongside S → c. Thus S → aAb | ab | c.
- A: Forgets to drop the nullable variable A from S → aAb.
- C: Terminals a and b are not nullable and cannot be dropped.
- D: A can also generate non-empty strings (like a), so S → aAb must be kept.
- 32 — Out of 6 edges on a root-to-leaf path, the bottom edge is a terminal rule A → a, leaving height 5 for the binary variable tree (A → BC). A binary tree of edge-height 5 has at most 2⁵ = 32 leaves.
- A — Each a pushes two A’s onto the stack, and each b pops one A. Since q₀ must read at least one b to move to q₁ (where Z can be popped), n ≥ 1. Thus N(P) = { aⁿb²ⁿ | n ≥ 1 }.
- B: Two A’s are pushed per a, so twice as many b’s are needed.
- C: Ratio is 1:2, not 1:1.
- D: ε is not accepted because Z can only be popped in q₁, which requires reading at least one b.
- ABD — Primes in unary, aⁿbⁿcⁿ, and equal counts of three symbols all fail the CFL pumping lemma (or unary CFL = regular) and can be decided by an LBA in linear space, so they are CSLs but not CFLs. {wwᴿ} is a CFL.
- C: {wwᴿ} is a Context-Free Language.
- A — If some TM M_k recognized L_d, asking whether M_k accepts w_k yields w_k ∈ L_d ⇔ M_k does not accept w_k ⇔ w_k ∉ L(M_k), contradicting L(M_k) = L_d.
- B: L_d is infinite.
- C: RE is not closed under complement.
- D: M_i need not halt on w_i.
- ABC — A, B, and C are non-trivial semantic properties (they depend only on the language L(M), and are true for some RE languages and false for others). D depends on the machine’s state count (syntax), not L(M), and is decidable.
- D: Number of states is a syntactic property of ⟨M⟩, decidable by inspecting the encoding.
- B — A_TM is RE-complete (hence RE and not REC). E_TM’s complement {⟨M⟩ | L(M) ≠ ∅} is RE (by dovetailing), and E_TM is undecidable, so E_TM is co-RE and NOT RE. Consequently A_TM ≤_m E_TM cannot hold (since B ∈ co-RE and A ≤_m B implies A ∈ co-RE, which fails for A_TM; instead A_TM ≤_m E̅_TM).
- A: E_TM is not RE.
- C: L₁ is RE and L₂ is co-RE.
- D: If A_TM ≤_m E_TM held, then A̅_TM ≤_m E̅_TM ∈ RE would make A̅_TM ∈ RE and A_TM decidable — impossible.
- D — For DCFLs, emptiness, universality (via complement + emptiness), and equivalence (Sénizergues’ theorem) are decidable. However, inclusion L₁ ⊆ L₂ is undecidable for DCFLs (since L₁ ∩ L̅₂ is an intersection of two DCFLs, which need not be a CFL).
- A: Decidable for all CFLs.
- B: Decidable for DCFLs because DCFL is closed under complement.
- C: Decidable by Sénizergues’ theorem.
- ABD — Parikh’s theorem implies every unary CFL is regular; unary regular languages have eventually periodic length sets; and reversing a unary string aⁿ gives aⁿ, so Lᴿ = L for every unary language.
- C: {a^{n²}} is unary and not eventually periodic, so it is neither regular nor a CFL.
- 9 — Each equivalence class of size k contributes k² ordered pairs to R: 2² + 2² + 1² = 4 + 4 + 1 = 9.