Theory of Computation and Compilers MCQ - 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'

A
m x 2ⁿ
B
2^mn
C
2^{m + n}
D
all of these

View Explanation
Comment

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

2 An FSM with

A
1 stack is more powerful than an FSM with no stack
B
2 stacks is more powerful than a FSM with 1 stack
C
both (A) and (B)
D
None of these

View Explanation
Comment

3 If two finite states machine M and N are isomorphic, then

A
M can be transformed to N, merely re-labelling its states
B
M can be transformed to N, merely re-labelling its edges
C
Both (A) and (B)
D
None of these

View Explanation
Comment

4 Power of

A
DFSM and NDFSM are same
B
DFSM and NDFSM are different
C
DPDM and NDPDM are diferent
D
Both (A) and (C)

View Explanation
Comment

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

A
1 (01)* and (10)* 1
B
x (xx) * and (xx) * x
C
x⁺ and x⁺x*⁺
D
All of these

View Explanation
Comment

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)