Theory of Computation and Compilers - Regular Language Models

1. Number of states of the FSM required to simulate behaviour of a computer with a memory capable of storing "m" words, each of length 'n'

  • Option : B
  • Explanation : 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 2mn
Cancel reply
Cancel reply

5. Which of the folowing pairs of regular expressions are equivalent?

  • Option : D
  • Explanation :
    Option (A) and option (B) are similar deriving expressions using rule :- (pq)*p = p(qp)*
    Option (C) will also be valid since:-
    (x+x*+) will be
    --->(xx*)(x*x**)
    --->(xx*)(x*x*)     (Using x** = x*)
    --->(xx*)(x*)     (Using x*x* = x*)
    --->(xx*)     (Using x*x* = x*)
    --->x+
    So, the answer will be all of these (Option D)
Cancel reply
Cancel reply