250+ TOP MCQs on Pumping Lemma for Context Free Language

Automata Theory Questions and Answers for Campus interviews on “Pumping Lemma for Context Free Language”.

1. Which of the following is called Bar-Hillel lemma?
a) Pumping lemma for regular language
b) Pumping lemma for context free languages
c) Pumping lemma for context sensitive languages
d) None of the mentioned

Answer: b
Clarification: In automata theory, the pumping lemma for context free languages, also kmown as the Bar-Hillel lemma, represents a property of all context free languages.

2. Which of the expressions correctly is an requirement of the pumping lemma for the context free languages?
a) uvⁿwxⁿy
b) uvⁿwⁿxⁿy
c) uv²ⁿwx²ⁿy
d) All of the mentioned

Answer: b
Clarification: Let L be a CFL. Then there is an integer n so that for any u that belong to language L satisfying |t| >=n, there are strings u, v, w, x, y and z satisfying
t=uvwxy
|vx|>0
|vwx|=0, uvⁿwxⁿy ∈ L

3.Let L be a CFL. Then there is an integer n so that for any u that belong to language L satisfying
|t|>=n, there are strings u, v, w, x, y and z satisfying
t=uvwxy.
Let p be the number of variables in CNF form of the context free grammar. The value of n in terms of p :
a) 2p
b) 2p
c) 2p+1
d) p²

Answer: c
Clarification: This inequation has been derived from derivation tree for t which must have height at least p+2(It has more than 2^p leaf nodes, and therefore its height is >p+1).

4. Which of the following gives a positive result to the pumping lemma restrictions and requirements?
a) {aⁱbⁱcⁱ|i>=0}
b) {0ⁱ1ⁱ|i>=0}
c) {ss|s∈{a,b}*}
d) None of the mentioned

Answer: b
Clarification: A positive result to the pumping lemma shows that the language is a CFL and ist contradiction or negative result shows that the given language is not a Context Free language.

5. Using pumping lemma, which of the following cannot be proved as ‘not a CFL’?
a) {aⁱbⁱcⁱ|i>=0}
b) {ss|s∈{a,b}*}
c) The set legal C programs
d) None of the mentioned

Answer: d
Clarification: There are few rules in C that are context dependent. For example, declaration of a variable before it can be used.

6. State true or false:
Statement: We cannot use Ogden’s lemma when pumping lemma fails.
a) true
b) false

Answer: b
Clarification: Although the pumping lemma provides some information about v and x that are pumped, it says little about the location of these substrings in the string t. It can be used whenever the pumping lemma fails. Example: {a^pb^qc^rd^s|p=0 or q=r=s}, etc.

7. Which of the following cannot be filled in the blank below?
Statement: There are CFLs L1 nad L2 so that ___________is not a CFL.
a) L1∩L2
b) L1′
c) L1*
d) None of the mentioned

Answer: c
Clarification: A set of context free language is closed under the following operations:
a) Union
b) Concatenation
c) Kleene

8. The pumping lemma is often used to prove that a language is:
a) Context free
b) Not context free
c) Regular
d) None of the mentioned

Answer: b
Clarification: The pumping lemma is often used to prove that a given language L is non-context-free, by showing that arbitrarily long strings s are in L that cannot be “pumped” without producing strings outside L.

9. What is the pumping length of string of length x?
a) x+1
b) x
c) x-1
d) x2

Answer: a
Clarification: There exists a property of all strings in the language that are of length p, where p is the constant-called the pumping length .For a finite language L, p is equal to the maximum string length in L plus 1.

10. Which of the following does not obey pumping lemma for context free languages ?
a) Finite languages
b) Context free languages
c) Unrestricted languages
d) None of the mentioned

Answer: c
Clarification: Finite languages (which are regular hence context free ) obey pumping lemma where as unrestricted languages like recursive languages do not obey pumping lemma for context free languages.