Reqular Expressions Questions

MCQ bookmark_border

41.

Which of the following pair of regular expression are not equivalent?

A

1(01)* and (10)*1

B

x(xx)* and (xx)*x

C

(ab)* and a*b*

D

x+ and x*x+

Correct Answer: C

(ab)*=(a*b*)*.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

42.

Consider following regular expressioni) (a/b)* ii) (a*/b*)* iii) ((?/a)b*)*
Which of the following statements is correct

A

i,ii are equal and ii,iii are not

B

i,ii are equal and i,iii are not

C

ii,iii are equal and i,ii are not

D

all are equal

Correct Answer: D

All are equivalent to (a+b)*.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

43.

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

44.

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

45.

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

46.

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 languageWhich 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

47.

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

48.

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

49.

Let L denotes the language generated by the grammar S

A

 L = O

B

 L is regular but not O

C

L is context free but not regular

D

L is not context free

Correct Answer: B

The grammar itself is not regular but language L is regular as L can be represented using a regular grammar, for example S -> S00/00.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

50.

Which of the following are not regular?

A

String of )

B

Palindromes Consisting of 0

C

String of 0

D

All of the mentioned

Correct Answer: D

Strings of odd number of zeroes can be generated by the regular expression (00) *0.Pumping lemma can be used to prove the non-regularity of the other options.

Check Answer report_problem Report forum Discussion