Regular Language

Question

Ans. 48

Comments

Please Explain the approach

---

every string of a must be divisible by 3 and 4 that means ${0,12,24,36,....}$

every string of b must be divisible by 4 or 8 that means $0,4,8,12,16,....$

to make this DFA we need 12 states for a's and 4 states for b

total states = $12 \times 4 = 48$

---

Nicely said. Sir in solution there is some concept of LCM and GCD what's that ?.

---

The best way to solve such problem is to follow the approach of compound DFA which is lengthy at first sight but too easy & correct that you will like.

Now compound DFA approach .

1.Try to make dfa which accepts no of a's divisible by 3 a's which will have 3 states

2.Again make a dfa which accepts no of a's divisible by 4 which will have 4 states

3.Now make a compound dfa which will have 3*4=12 states

Now try to make other dfa which will divisible by 4 or 8 will have 4 states & pls make only one dfa bcs divisible of 4 will include 8 also..

Now in the final step again do compounding which will have 12*4 states=48

Pls see once the concept of compound dfa & try to make the actual dfa you will get actual point & more clearity & in future u will handle such problems very easily

Answer 1

In language L,

the strings of a will have 3*4=12 states

and the strings of b will have L.C.M of 4 ,8 coz they are either divisible by 4 or 8 =4

therefore the resultant no. of states consist of both the strings a and b=12*4=48 states.

Comments

what is the approach of product of 12*4?

how you could do that?

---

@Prathap Ñsvr

those are different mod machines ( one for a and another for b ) ==> required product for final mod machine.

---

thank you!