The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
1.2k views

The following finite state machine accepts all those binary strings in which the number of $1$’s and $0$’s are respectively:

     

  1. divisible by $3$ and $2$

  2. odd and even

  3. even and odd

  4. divisible by $2$ and $3$

asked in Theory of Computation by Veteran (59.7k points)
edited by | 1.2k views

3 Answers

+17 votes
Best answer

Option (C) and option (D) are cancelled out clearly because with $3$ $1$s we can reach the final state. There is an string where we can reach the final state by $6$ $1$'s now $6$ is nt odd but it is divisivble by $3$. Hence, option (A) is correct.

answered by Boss (14.4k points)
edited by
0
why not D?
0

@Pranav Madhani

option d is 1 divisible by 2 and 0 is divisible  3 which is wrong. 

because 

No. of 0's % 2 = 0 

no. of 1's % 3 =0

 



 

+12 votes

ε (Empty string) is accepted here. So option (B) & (C) are canclelled out !

No of 0's % 2 = 0 . So answer => A

answered by Boss (43.2k points)
+6 votes
No. of 1s is represented horizontally and 0s vertically.

There are 3 states each for number of 1s. So, it is understood that states are for 0, 1 and 2 as remainders when no. of 1s is divided by 3.

Similarly, there are 2 states each for number of 0s. So, it is understood that states are for 0 and 1 as remainders when no. of 0s is divided by 2.

Hence option A is correct.
answered by (309 points)
0
What is difference between option A and D?
+3
in option (A) number of 1's divisible by 3 and number of 0's divisible  by 2 and

option (D) number of 1's divisible by 2 and number of 0's divisible  by 3
Answer:

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

44,200 questions
49,671 answers
163,564 comments
65,819 users