Question

no of state in minimal finite automata that accept the string from alphabet {a,b,c} where no of a is divisible by 2 or 3 and no of c is divisible by 6?? plzz explain!!!

Answer 1

It should be 6. Becz remainder of 2 will be 2 and remainder of 3 will be 3. So total no of combination will be 2*3=6. And c divisible by 6 means it should be divisible by both 2 and 3. So this can be incorporated in above 6 states

Comments

Please post an automata for the same, We cannot conclude on number of states in automata just be the theorm of divisibility.

---

total 36 states would be there 6 states would be in (mod2 or mod 3) dfa and 6 states would be for mod 6 c's

6*6 = 36

Answer 2

In any automata no of states for minimal is given by the modulus on it For ex  |a| mod n will have n states .
In This question there will be combination of |a| mod 2 and |a| mod 3 so therefore a common dead state.

Total states in a= 4.

Total states in c =6 (given).

Total states =4*6 =24.

Answer 3

if X is the set of States which count na(No of as) then possible states for counting a will be X={ (naMod20, naMod30),(naMod20,naMod31),(naMod20,naMod32), (naMod21,naMod30)} Here (Mod20,Mod30) means the state where naMod2=0 and naMod3=0, Similarly interpret  the others. Now Y is the set of states which count nc(No ofcs) then possible states will be. Y={ncMod60, ncMod61, .........,ncMod65} : ncMod60 means the state where ncMod6=0 similarly interpret the others.

Now the possible states for the machine will be : Z={X*Y} ={(namod20,namod30,ncMod60), ......(naMod21,naMod30,ncMod65).  so no of State will be |Z|=24.You can get some idea from the below image how the state could be look like. for X Set,

Comments

if there are 5 a's which state it will be?

---

Opps i missed that. i should have consider that also. The extra new State will be (naMod21,naMod32).The answer will be 30. Am i rt now?or anything i am missing?

---

one more for mod2 = 1, mod3 =1 as for 7 a's. So, should be 6*6 = 36.

---

mod21,mod31 already there..