Theory of computation

Question

Suppose L is a regular language of all a's and b's where the number of a's is divisible by 4 and 8 and number of b's is divisible by 10. If M is the minimal DFA accepts L then M contains __________________ number of states

for a considering 8 states

for b considering 10 states

concatenating both (i.e) join the end state of first with the start state of next

therefore 8 + 9 = 17 states

BUT THE SOLUTION GIVEN multiplies 8 * 10 =80

why?

in some places its added and that too considering that two states are merged to one, 10 is aken as 9

when is it performed like this and when is it multiplied

Answer 1

U can't use concatenation over there...  If a string starts with b?

Comments

got it, thank you :)

Answer 2

The product Automation is used for taking intersection,union or set difference of two DFA's M1 and M2.
We make the product automation and circle only those states as final state which are final in M1 and M2.

Concatenation DFA of M1 and M2 is different than product dfa.

Comments

why not perform concatenate here?

can u explain concatenation DFA and product DFA

Answer 3

a's are div by 4 and 8 so it requires 8 states and b's div by 10 req 10 states...  Cross product gives 80