1.1k views
Construct a finite state machine with minimum number of states, accepting all strings over $(a,b)$ such that the number of $a$'s is divisible by two and the number of $b$'s is divisible by three.
edited | 1.1k views
+1

This might help ...

A state $q_{xy}$ means  $n_a \ mod \ 2 =x$ ,  $n_b \ mod \ 3=y$

$q_{00}$ means $n_a \ mod \ 2 =0$  ,$n_b \ mod \ 3=0$   [no of $a$'s is divisible of $2$ and no of $b$'s are divisible of $3$]

$q_{00} \ x \ a \rightarrow q_{10}$

$q_{00} \ x \ b \rightarrow q_{01}$  and so on

edited by
0
any reference of how to draw these plzzzzzzzz
0

first draw DFA for a's is divisible by two and the b's is divisible by three.

then u can easily get final DFA

0

@Praveen Saini, sir can you give a hint for NFA designing for the same Language?

0
Hi NFA is much more easier than DFA.
0
yes,  as question is asking about minimum number of states in FSM then number of states should be equal to states in NFA.

I know NFA is easier but here we have to keep track of a's and b's both. Can you please share your NFA design?
0

any reference of how to draw these plzzzzzzzz

Step 1: draw DFA for number of a divisible by 2

Step 2 : draw DFA for number of bs divisible by 3.

Step 3: Take cross product of two DFAs

1
2