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

i don't think that is correct. I think it should be 2^mn.

since a particular word can be in 2ⁿ states and since there are m such words.

Let's take an example. say we have 3 words of 2 bits each then :

word1         word2        word3    

00                  00              00

01                  01              01

10                  10              10

11                  11               11

so states of the machine can be represented as triplets :

{(0,0),(0,0),(0,0)} {(0,0),(0,0),(0,1)} {(0,0),(0,0),(1,0)} {(0,0),(0,0),(1,1)}

{(0,0),(0,1),(0,0)} {(0,0),(0,1),(0,1)} {(0,0),(0,1),(1,0)} {(0,0),(0,1),(1,1)}

 

{(0,0),(1,0),(0,0)} {(0,0),(1,0),(0,1)} {(0,0),(1,0),(1,0)} {(0,0),(1,0),(1,1)}

{(0,0),(1,1),(0,0)} {(0,0),(1,1),(0,1)} {(0,0),(1,1),(1,0)} {(0,0),(1,1),(1,1)}

these are different words combinations, even if one can be reached by rearranging the other. But since the registers are different so they are different combinations.

 

so there are 2²⁺² states for the first state of the first word.

so there are 2²*(2²⁺²) = 2²⁺²⁺² = 2⁶

so for general case this should be 2^m*n

^{@arjun sir please verify if i am correct if wrong state the reason.}

---

You are correct. I hadn't considered words separately- corrected now. Thanks :)

---

@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.