ISRO CSE 2014 | Question: 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

We need to find the number of different configurations possible for memory and each of these will be a state in FSM. (At any time memory will be in one configuration and in next instance it either remains same or goes to a different configuration)

A word is of n bits. And we have m such words. So, total number of bits = m*n.

We need a separate state for each bit combination. So, no. of states = 2^mn.

Comments

@timojit does 0,0 in the configuartion represents that nothing is stored in that word

---

I dont understand why there are 2²⁺² states for the first state of the first word?

---

because first state of the first word (0,0) only contains 16 different states , i.e. 2^2*2, where 1st 2^2*2 contains all combination of (0,0),(0,0),(0,0) and 2^2*2 contains all combination of (0,0),(0,0),(0,0)

Answer 2

Total m words. Each of size n bit.

Total m*n bits .

Number of states in FSM  are 2^m*n
 

[ 1 bit need 1 flip-flop , represent 2 states, 0 or 1.]

Comments

Is it possible to simulate the behavior of computer using FSM?

---

Is FSM is DFA or NFA ??

If it is DFA,

If we have a word with n bits long, then we require (n+2) states to recoginese that.

Ex: to accept aa over alphabet, we need to 4 states.

So if we have one word of length n, we need (n+2) states DFA.

For other words also we require same number of states, then it would become (n+2) states.

Even after minimising the above DFA, we will have (n+2) states only,

please correct me if  iam wrong.

Answer 3

https://gateoverflow.in/3411/states-required-simulate-behavior-computer-capable-storing

Answer 4

For every data here length is ‘n’ and memory's states are defined in terms of power of 2, 
Here the total memory capability for all the words = mn
Hence number of states are 2^mn

Answer 5

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