Theory of Automata
Pumping-Lemma
Q.

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’s theorem

 D.  

None of the mentioned
Similar Questions
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
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
3.

Context free grammar is closed under
A.  

Union

 B.  

Intersection

 C.  

Both

 D.  

 None of these
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
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
6.

Pumping lemma for context free language breaks the strings into
A.  

Two parts

 B.  

Three parts

 C.  

Five parts

 D.  

Six parts
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
8.

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

O(n³) time

 B.  

O(n²) time

 C.  

O(n) time

 D.  

None of these
9.

The CYK algorithm is also known as
A.  

Table filling algorithm

 B.  

Pumping lemma

 C.  

Both (a) and (b)

 D.  

None of these
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’s theorem

 D.  

None of the mentioned
THEORY OF AUTOMATA TOPICS