Q. Let L={ w ∣ na(w) mod 13 = 1 or na(w) mod 15 = 5 }, where na(w) is the…
Q. Let L={ w ∣ na(w) mod 13 = 1 or na(w) mod 15 = 5 }, where na(w) is the number of letter a in string w.
What is the number of accepting states in a minimal DFA that keeps track of na(w) modulo the necessary value(s)? (MCQ)
Answer: C. 27 — We must track the number of a's modulo both 13 and 15. The natural way is to track residues modulo lcm(13,15) = 195 so we can test both congruences…
- A.
13
- B.
26
- C.
27
- D.
195
Attempted by 88 students.
Show answer & explanation
Correct answer: C
We must track the number of a's modulo both 13 and 15. The natural way is to track residues modulo lcm(13,15) = 195 so we can test both congruences simultaneously.
Residues satisfying na(w) ≡ 1 (mod 13): there are 195/13 = 15 such residues modulo 195.
Residues satisfying na(w) ≡ 5 (mod 15): there are 195/15 = 13 such residues modulo 195.
Intersection (both congruences): by the Chinese Remainder Theorem there is exactly 1 residue modulo 195 satisfying both na(w) ≡ 1 (mod 13) and na(w) ≡ 5 (mod 15).
Using inclusion–exclusion, the number of accepting residues is 15 + 13 − 1 = 27.
Answer: 27 accepting states.
A video solution is available for this question — log in and enroll to watch it.