Reqular Expressions
1.

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

An FSM with
A.  

M can be transformed to Numeral relabeling its states

 B.  

M can be transformed to N, merely relabeling its edges

 C.  

Both of the mentioned

 D.  

None of the mentioned
3.

Which of the following is right?
A.  

A Context free language can be accepted by a deterministic PDA

 B.  

union of 2 CFLs is context free

 C.  

The intersection of two CFLs is context free

 D.  

The complement of CFLs is context free
4.

Consider the following two statements:
S1: { 0^2n |n >= l} is a regu1ar language
S2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar language
Which of the following is true?
A.  

Only S1 is correct

 B.  

Only S2 is correct

 C.  

Both S1 and S2 are correct

 D.  

None of S1 and S2 is correct
5.

Which of the following 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 the mentioned
6.

Which of the following 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 the mentioned
7.

Which of the following 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 the mentioned
8.

Given a NFA with N states, the maximum number of states in an equivalent minimized DFA is at least.
A.  

N^2

 B.  

2^N

 C.  

2N

 D.  

N!
9.

Regular expression (x/y)(x/y) denotes the set
A.  

{xy,xy}

 B.  

{xx,xy,yx,yy}

 C.  

{x,y}

 D.  

{x,y,xy}
10.

Regular expression x/y denotes the set
A.  

{x,y}

 B.  

{xy}

 C.  

{x}

 D.  

{y}