# Automata Theory Questions and Answers – Pumping Lemma for Context Free Language

«
»

This set of Automata Theory Questions and Answers for Campus interviews focuses 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

Explanation: 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) uvnwxny
b) uvnwnxny
c) uv2nwx2ny
d) All of the mentioned

Explanation: 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|<=n For any m>=0, uvnwxny ∈ 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 is
a) 2p
b) 2p
c) 2p+1
d) p2

Explanation: This inequation has been derived from derivation tree for t which must have height at least p+2(It has more than 2p 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) {aibici|i>=0}
b) {0i1i|i>=0}
c) {ss|s∈{a,b}*}
d) None of the mentioned

Explanation: 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) {aibici|i>=0}
b) {ss|s∈{a,b}*}
c) The set legal C programs
d) None of the mentioned

Explanation: 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

Explanation: 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: {apbqcrds|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

Explanation: 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

Explanation: 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

Explanation: 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

Explanation: 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.

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory for Campus Interviews, here is complete set of 1000+ Multiple Choice Questions and Answers. 