Question

Number of states of FSM required to simulate behaviour of a computer with a memory capable of storing “m” words, each of length ‘n’.

(a) m x 2^n

(b) 2^mn

(c) 2^(m+n)

(d) all of the mentioned

The question was asked in a job interview.

My question is taken from Finite Automata and Regular Expressions in section Compiler Introduction of Compiler

Answer 1

Correct option is (b) 2^mn

Easiest explanation: For every Data here length is n and memory’s state is defined in terms of power of 2, Here the total memory capability for all the words = mn Hence the number of states is2^mn.