Pumping Lemma Questions

MCQ bookmark_border

1.

Pumping lemma for context free grammar is used for

A

Proving certain languages are not context free

B

Proving language is infinite

C

Both (a) and (b)

D

None of these

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

2.

Which of the following statement is false?

A

If L is context free language then L* is also a context free language

B

If L1 and L2 are context free language then there intersection is not a context free language

C

If L1 and L2 are context free language then there union is also a context free language 

D

None of these

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

3.

Context free grammar is closed under

A

Union

B

Intersection

C

Both

D

 None of these

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

4.

CYK algorithm is named CYK because it was invented by

A

John Cocke, Tadao Kasami and Daniel H. Younger

B

Jass Carry, Tom Kosami and Daniel Richy

C

Cammy lenna, Yousaf, Kosami

D

None of these

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

5.

The CYK algorithm start with

A

Chomsky normal form grammar

B

Greibach normal form grammar

C

Both (a) and (b)

D

None of these

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

6.

Pumping lemma for context free language breaks the strings into

A

Two parts

B

Three parts

C

Five parts

D

Six parts

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

7.

In pumping lemma for context free language

A

We start by assuming the given language is context free and then we get contradict

B

We first convert the given language into regular language and then apply steps  on

C

Both (a) and (b)

D

 None of these

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

8.

The CYK algorithm constructs table from where we can conclude whether w is in L

A

O(n

B

O(n

C

O(n) time

D

None of these

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

9.

The CYK algorithm is also known as

A

Table filling algorithm

B

Pumping lemma

C

Both (a) and (b)

D

None of these

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

10.

Relate the following statement:
Statement: All sufficiently long words in a regular language can have a middle section of words repeated a number of times to produce a new word which also lies within the same language.

A

Turing Machine

B

Pumping Lemma

C

Arden

D

None of the mentioned

Correct Answer: B

Pumping lemma defines an essential property for every regular language in automata theory. It has certain rules which decide whether a language is regular or not.

Check Answer report_problem Report forum Discussion