geeksforgeeks site

Question

Consider the Deterministic Finite Automaton for input alphabets Σ = {a, b}
L = 
The number of final state(s) will be
(A) 2
(B) 1
(C) 3
(D) 6

Comments

Is it 3?

n(a) mod 3> n(b) mod 3

possible values for mod 3 : 0,1,2

Therefore possible combinations : 

n(a)mod3 should be 1 or 2 
if  n(a)mod3 is 1 then b's can be 0.

if n(a)mod3 is 2 then b's can be 0 or 1.

case 1 :

if  n(a)mod3 is 1 then number of b's can be 0.

possible  L = {a,aaaa,aaaaaaa,aaaaaaaaaa, .... i.e. number of a's mod 3 =1 here)

case 2 :

if  n(a)mod3 is 2 then number of b's can be 0/1.

possible  L : 

b's 0 :{aa,aaaaa,aaaaaaaa,  .... i.e. number of a's mod 3 =2 and  number of b's mod 3 =0 here}

b's 1 :{aab, aaaaab, aaaaaaaab, .... i.e. number of a's mod 3 =2 and  number of b's mod 3 =1 here}

Therefore L will accept : 
{a,aa,aab,baa,aba,aaaa,aaaaa, aaaaab, .................... }

3*3 states from (0,0) (0,1) ...... to (2,2)

among which (1,0),(2,0),(2,1) will be final states.

---

yes, answer is 3. well explained.. thanks..

Answer 1

Final States should be 3. (1,0),(2,0),(2,1)