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

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

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

Answer 3

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 4

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.