edited by
8,312 views
38 votes
38 votes

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$

edited by

4 Answers

Best answer
30 votes
30 votes

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.

edited by
20 votes
20 votes

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

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

13 votes
13 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.
0 votes
0 votes
Correct option: A

This is because every string accepted by this DFA has 1’s divisible by 3 and 0’s divisible by 2.

For Example:

1010101011 is accepted by DFA,

Number of 1’s: 6%3=0 (Divisible by 3)

Number of 0’s: 4%2=0 (Divisible by 2)
Answer:

Related questions

37 votes
37 votes
7 answers
1
Kathleen asked Sep 18, 2014
12,568 views
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is$2$$3$$4$$5$
27 votes
27 votes
5 answers
2
Kathleen asked Sep 18, 2014
18,986 views
Let $A = 1111 1010$ and $B = 0000 1010$ be two $8-bit$ $2’s$ complement numbers. Their product in $2’s$ complement is$1100 0100$$1001 1100$$1010 0101$$1101 0101$
42 votes
42 votes
4 answers
3
Kathleen asked Sep 18, 2014
11,956 views
Two matrices $M_1$ and $M_2$ are to be stored in arrays $A$ and $B$ respectively. Each array can be stored either in row-major or column-major order in contiguous memory ...
27 votes
27 votes
3 answers
4
Kathleen asked Sep 18, 2014
5,595 views
The elements $32, 15, 20, 30, 12, 25, 16,$ are inserted one by one in the given order into a maxHeap. The resultant maxHeap is