Finite automata

15 questions across Phase 1, weighted like GATE: many minimal-DFA counting questions.

1. NAT · 1 mark

   Minimal DFA states over {a,b} for strings that start and end with the same symbol (ε excluded, single symbols included)?

   Write your answer before opening the key.

2. NAT · 2 marks

   Minimal DFA states for binary numbers divisible by 10?

   Write your answer before opening the key.

3. MCQ · 1 mark

   How many DFAs with states {p, q}, start p, over Σ = {0} exist?

   1. 8
   2. 16
   3. 4
   4. 32
4. NAT · 1 mark

   Minimal DFA states over {a,b}: #a ≡ 1 (mod 3) and #b ≡ 0 (mod 2)?

   Write your answer before opening the key.

5. MCQ · 2 marks

   M accepts strings over {a,b} containing aa (3 states, dead state not needed). Swap its accepting and non-accepting states. The new language is:

   1. strings containing bb
   2. strings not containing aa
   3. strings ending in a
   4. Σ*
6. MSQ · 2 marks

   L₁, L₂ regular. Which are guaranteed regular?

   1. L₁ ∪ L₂
   2. L₁ ∩ L₂
   3. L₁ − L₂
   4. Σ* − L₁
7. NAT · 1 mark

   Minimal DFA states over {0,1}: 5th symbol from the end is 0?

   Write your answer before opening the key.

8. MCQ · 1 mark

   An NFA rejects w iff:

   1. some path ends in a non-accepting state
   2. every path dies or ends in a non-accepting state
   3. the first path rejects
   4. w is not empty
9. NAT · 2 marks

   NFA over {a,b}: q0 ─a→ {q0,q1}, q0 ─b→ {q0}, q1 ─a→ {q2}, q1 ─b→ {q2}, F = {q2}. Reachable subset-construction states?

   Write your answer before opening the key.

10. MSQ · 1 mark

    ε-NFA: s ─ε→ p, s ─ε→ r, p ─a→ p (p accepting), r ─b→ r (r accepting). Which are accepted?

    1. ε
    2. aaa
    3. ab
    4. bb
11. NAT · 2 marks

    Unary DFA: cycle 0→1→…→5→0, start 0, F = {1, 3, 5}. Minimal states?

    Write your answer before opening the key.

12. NAT · 2 marks

    Minimal DFA states over {a,b} for strings of length at least 2 whose second symbol is b?

    Write your answer before opening the key.

13. MCQ · 2 marks

    Index of ≡_L for L = { aⁿ : n ≡ 0 (mod 2) or n ≡ 0 (mod 3) }:

    1. 5
    2. 6
    3. 3
    4. infinite
14. MSQ · 2 marks

    Which languages have infinite Myhill–Nerode index?

    1. { aⁿbⁿ }
    2. { w : |w|ₐ = |w|_b }
    3. { aⁿbᵐ : n, m ≥ 1 }
    4. { w : |w|ₐ ≡ |w|_b (mod 2) }
15. NAT · 1 mark

    Output length of a Moore machine on an input of length 9?

    Write your answer before opening the key.