Introduction
15 questions across Phase 2: regex reading and equivalence, conversions, grammars, closure, algorithms and classification.
Practice questions
- MCQ · 1 mark
Which string is in L((0 + 10)*1*)?
- 0110
- 1101
- 0011
- 110
- MSQ · 2 marks
Which are equivalent to (a + b)*a(a + b)*?
- b*a(a + b)*
- (a + b)*ab*
- (a + b)*a
- b*a b*
- NAT · 1 mark
Number of strings of length 6 over {0,1} with no two consecutive 0s?
Write your answer before opening the key.
- NAT · 1 mark
Strict Thompson states for a + b + c (as (a + b) + c)?
Write your answer before opening the key.
- MCQ · 2 marks
Solve: A = ε + Aa + Bb, B = Aa (A start, B accepting). B = ?
- (a + ab)*a
- a(a + ba)*
- (a + ab)*
- Both A and B are correct
- MCQ · 1 mark
S → aS | aB, B → bB | b generates:
- a*b*
- a⁺b⁺
- (ab)⁺
- a⁺b*
- MSQ · 2 marks
Which grammars generate non-regular languages?
- S → aSb | ε
- S → aA, A → Sb | b
- S → aS | Sb | ε
- S → abS | ε
- MSQ · 2 marks
L regular, N not regular. Which are always regular?
- L ∩ Σ*
- L / N
- L ∪ N
- Lᴿ
- MCQ · 1 mark
For a DFA with n states, L is infinite iff it accepts some string of length:
- < n
- between n and 2n − 1
- exactly 2n
- > 2ⁿ
- MCQ · 2 marks
To show { aⁿbⁿ } non-regular, a valid winning choice is:
- w = aᵖbᵖ, i = 2
- w = ab, i = 0
- w = aᵖbᵖ, i = 1
- w = (ab)ᵖ, i = 2
- MSQ · 2 marks
Which are regular?
- { aⁱbʲcᵏ : i + j + k ≡ 0 mod 2 }
- { aⁿbⁿcⁿ }
- { w x w : w, x ∈ {a,b}⁺ }
- { a^{n²} }
- MCQ · 1 mark
{ w ∈ {0,1}* : value of w in binary is a power of 2 } is:
- regular: 0*10*
- not regular
- finite
- regular: 1*0*
- NAT · 2 marks
Minimal DFA states for L((a + b)*b(a + b)) over {a,b}?
Write your answer before opening the key.
- MCQ · 2 marks
Regex for strings over {a,b} with an odd number of b’s:
- a*b(a*ba*b)*a*
- (a*ba*ba*)*b
- a*(ba*b)*a*
- (ab)*b
- MSQ · 1 mark
Which operations can turn a regular language into a non-regular one?
- taking a subset
- infinite union of regular languages
- complement
- reversal
Answer key
Reveal answers when you’re ready
- C — Blocks 0, 0, then 11 from 1*.
- A: After 0, “11” must come from 1*, and then the final 0 cannot follow.
- B: A leading 1 must be the block 10, but the next symbol is 1.
- D: 11 from 1* cannot be followed by 0.
- AB — Both say “at least one a” (first a or last a).
- C: Ends with a.
- D: Exactly one a.
- 21 — Fibonacci: 2,3,5,8,13,21 for n = 1..6.
- 10 — a,b,c: 6; first union +2; second union +2 = 10.
- D — A = ε + A(a + ab) ⇒ A = (a + ab)*; B = (a + ab)*a. By shifting, (a + ab)*a = a(a + ba)*.
- A: Correct but not the only correct option.
- B: Correct but not the only correct option.
- C: That is A.
- B — At least one a, then at least one b.
- A: ε, a, b missing.
- C: Not alternating.
- D: Needs a b.
- AB — Both generate aⁿbⁿ.
- C: a*b*: regular.
- D: (ab)*.
- ABD — Quotient by anything; reversal; trivially L.
- C: L = ∅ gives N.
- B — Pumping window.
- A: Those decide emptiness.
- C: Not the standard bound.
- D: Too large; not the criterion.
- A — i = 1 changes nothing; ab may be shorter than p; (ab)ᵖ ∉ L.
- B: |w| may be < p.
- C: i = 1 gives w back.
- D: Not in L.
- AC — Parity; free middle.
- B: Not even context-free (Phase 3).
- D: Not eventually periodic.
- A — Binary powers of 2 are a single 1 followed by 0s (with optional leading zeros).
- B: In binary it is easy.
- C: Infinite.
- D: Allows 11.
- 4 — Second-from-end is b: 2² = 4.
- A — One b, then pairs of b’s, a’s anywhere.
- B: Forces a final b.
- C: Even number of b’s.
- D: Too restrictive.
- AB — Only non-closure operations.
- C: Closed.
- D: Closed.