theory of computation

Question

Construct minimal  DFA for L = {aⁿ: n is either a multiple of three or a multiple of 5 }

Comments

@Prateek Raghuvanshi i think empty string should not be accepted but your answer is accepting it 

Answer 1

In minimized dfa 15 states will be present, because lcm(3,5)=15 so loop should be of 15.

Comments

yes , it can be done in 15 states!!

---

This is incorrect, as the language is (a,b). The b transitions are missing.

---

This is incorrect, as the language is (a,b). The b transitions are missing.

where is it written that language has strings (a,b) ?

Answer 2

DFA with 16 states.

Note: I think it can be minimised. I have done by constructing NFA and then converting NFA to DFA.

Comments

By applying your logic then will the number of states in dfa for a^n such that n is a multiple of 3 or 7 be 22?

If that be the case then this kind of problems could be solved by a simple trick:

If L=a^n such that n is a multiple of x or y then number of states in dfa accepting L would be (x*y)+1 provided x doesn't divides y if x<y and vice-versa

Am I correct?

---

No , answer is wrong
9 state are required.

---

No you are wrong...a11,a13,a14....all will be accepted but these are neither multiple of 3 nor 5

Answer 3

Number of states =16