Reqular Expressions Questions

MCQ bookmark_border

11.

The regular expressions denote zero or more instances of an x or y is

A

(x+y)

B

(x+y)*

C

(x* + y)

D

(xy)*

Correct Answer: B

For instances of x or y the exp is x+y and both can zero or more times than (x+y)*.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

12.

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

A

m x 2ⁿ

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

13.

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

14.

Which of the following statement is correct?

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

15.

Which of the following statement is correct?

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

16.

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

17.

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

18.

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

A

N²

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

19.

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

20.

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

Check Answer report_problem Report forum Discussion