GATE CSE 1997 | Question: 20

Question

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.

Answer 1

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\text{’}$s is divisible by $2$ and no of $b\text{’}$s is divisible by $3$]

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

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

Comments

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

---

@reena_kandari

Here NFA and DFA will be same.

---

For those looking for a way other than cross product, use state labeling. First make a table of number of a’s and b’s.

Number of a’s	Number of b’s
0	0
0	1
0	2
1	0
1	1
1	2

The number of rows gives us the number of states in the DFA, and this is the minimum (you can verify using Myhill-Nerode). The first state, 0a’s 0b’s is the initial as well as the final state (since we want the input to have number of a’s divisible by 2 and number of b’s divisible by 3).

Draw the states and then figuring out the transitions is easy. For example, from 0a0b, use an a to go to 1a0b, and then one more a to go back to 0a0b. Let’s say you are at 0a1b. If you add an a here, where do you go? 1a1b. If you add another a, then where? Back to 0a1b (because number of a’s follows the mod2 cycle and technically you have only read 1mod3 b’s so far, so no change in b’s).

If you can follow this first-principles DFA logic, it is faster than writing two DFAs and making their cross product. With practice you can draw the DFA directly without having to make any tables.