Consider the following language.
L = { x ∈ {a,b}* | number of a's in x divisible by 2 but not divisible by 3 }
The minimum number of states in DFA that accepts L is _______.
Correct Answer:
6
Solution:
L = { x ∈ {a,b}* | number of a's in x divisible by 2 but not divisible by 3 }
Step 1: Draw DFA where no. of a’s divisible by 2
Step 2: Draw DFA where no. of a's not divisible by 3
Use the concept of Product Automata we will get, states as AD, AE, AF, BD, BE, BF where AE and AF are final states.
Now, just draw a new DFA:
We cannot minimize it further. So, min DFA will Contain 6 states in DFA.
