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

This might help ...

1 Answer

+18 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.1k points)
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?


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

39,512 questions
46,664 answers
139,705 comments
57,481 users