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

View Answer

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) uv^{n}wx^{n}y

b) uv^{n}w^{n}x^{n}y

c) uv^{2n}wx^{2n}y

d) All of the mentioned

View Answer

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, uv

^{n}wx

^{n}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^{2}

View Answer

Explanation: 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^{i}b^{i}c^{i}|i>=0}

b) {0^{i}1^{i}|i>=0}

c) {ss|s∈{a,b}*}

d) None of the mentioned

View Answer

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) {a^{i}b^{i}c^{i}|i>=0}

b) {ss|s∈{a,b}*}

c) The set legal C programs

d) None of the mentioned

View Answer

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

View Answer

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: {a

^{p}b

^{q}c

^{r}d

^{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

View Answer

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

View Answer

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

View Answer

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

View Answer

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__.