The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+12 votes
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.
asked in Theory of Computation by Veteran (59.8k points)
edited by | 1.4k views

This might help ...

1 Answer

+19 votes
Best answer

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 

answered by Veteran (55.9k points)
edited by
any reference of how to draw these plzzzzzzzz

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


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

Hi NFA is much more easier than DFA.
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?

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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,126 questions
53,251 answers
70,502 users