Reqular Expressions Questions

MCQ bookmark_border

1.

Number of states of FSM required to simulate behaviour of a computer with a memory capable of storing

A

m x 2^n

B

2^mn

C

2^(m+n)

D

All of the mentioned

Correct Answer: B

For every Data here length is n and memory

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

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

Correct Answer: C

The Definition of FSM states that M can be transformed to N by relabeling its states or its edges.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

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

Correct Answer: B

Context-free languages are closed under the following operations. The Kleene star, the concatenation, the union and the intersection.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

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

Correct Answer: C

S1 can be written as (00) ^n where n >= 1. And S2 can be written as (00) ^ (m+n) where m >=2 and n >= 1. S2 can be further reduced to (00) ^x where x >= 3. SO we can write regular grammars for both G1 -> G100/00 (For S1) G2 -> G200/000000 (For S2).

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

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

Correct Answer: D

Rule (pq)*p=p (qp)* Therefore

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

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

Correct Answer: D

Rule (pq)*p=p (qp)* Therefore

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

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

Correct Answer: D

Rule (pq)*p=p (qp)* Therefore

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

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!

Correct Answer: B

The initial state of the DFA constructed from this NFA is the set of all NFA states that are reachable from state 1 by ?-moves; that is, it is the set {1, 2, and 3}. A transition from states1, 2, and 3 by input symbol 0 must follow either the arrow from state 1 to 2, or from state 3 to 4. Also, neither state 2 nor 4 have outgoing ?-moves.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

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}

Correct Answer: B

From first part if we take x then from the latter part x then it forms xx From first part if we take x then from the latter part y then it forms xy From first part if we take y then from the latter part x then it forms yx From first part if we take y then from the latter part y then it forms yy.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

10.

Regular expression x/y denotes the set

A

{x,y}

B

{xy}

C

{x}

D

{y}

Correct Answer: A

Because either x or y can be selected.

Check Answer report_problem Report forum Discussion