ISRO2014-2

Question

The number of states required by a Finite State Machine,to simulate the behavior of a computer with a memory capable of storing 'm' words, each of length 'n' bits is?

• A. $m \times 2^n$
• B. $2^{m+n}$
• C. $2^{mn}$
• D. $m+n$

Answer 1

It's always best to turn the variables into constants in such questions.

Let there be 2 words of 3 bits each.

Each word could be: 

• 000
• 001
• 010
• 011
• 100
• 101
• 110
• 111

There are 2 such words.

Now Option A would suggest there are $2*8=16$ states.

Option B would suggest there are $2^{5}=32$ states.

Option C would suggest there are $2^{6}=64$ states.

Option D would suggest there are $5$ states. This can be eliminated straight as Just 1 word alone has 8 states.

 

Total states could be: Word 1 is $000$ and Word 2 could be $000$ or $001$ or...or $111$

Hence, do a cross product.

Word 1	Word 2
000	000
001	001
010	010
011	011
100	100
101	101
110	110
111	111

You'll get $8*8=64$ which is Option C