GATE 2007
April 5, 2025GATE 2008-IT
April 5, 2025GATE 2007
| Question 29 |
A minimum state deterministic finite automaton accepting the language L = {w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} has
| 15 states | |
| 11 states | |
| 10 states | |
| 9 states |
Question 29 Explanation:
Given that number of 0’s and 1’s are divisible by 3 and 5, it means that the number of 0’s and 1’s must be divisible by 15. As the LCM of 3 and 5 is 15, so number of 0’s and 1’s are divisible by 3 and 5 is only possible if of 0’s and 1’s are divisible by 15. Also modulo 3 will leave a remainder of 0,1,2 (3 states required) and modulo 5 will leave remainder of 0,1,2,3,4 (5 states required), so product automata will require (3 × 5=15 states).
Correct Answer: A
Question 29 Explanation:
Given that number of 0’s and 1’s are divisible by 3 and 5, it means that the number of 0’s and 1’s must be divisible by 15. As the LCM of 3 and 5 is 15, so number of 0’s and 1’s are divisible by 3 and 5 is only possible if of 0’s and 1’s are divisible by 15. Also modulo 3 will leave a remainder of 0,1,2 (3 states required) and modulo 5 will leave remainder of 0,1,2,3,4 (5 states required), so product automata will require (3 × 5=15 states).