Test: Pumping Lemma For Context Free Language


10 Questions MCQ Test Theory of Computation | Test: Pumping Lemma For Context Free Language


Description
This mock test of Test: Pumping Lemma For Context Free Language for Computer Science Engineering (CSE) helps you for every Computer Science Engineering (CSE) entrance exam. This contains 10 Multiple Choice Questions for Computer Science Engineering (CSE) Test: Pumping Lemma For Context Free Language (mcq) to study with solutions a complete question bank. The solved questions answers in this Test: Pumping Lemma For Context Free Language quiz give you a good mix of easy questions and tough questions. Computer Science Engineering (CSE) students definitely take this Test: Pumping Lemma For Context Free Language exercise for a better result in the exam. You can find other Test: Pumping Lemma For Context Free Language extra questions, long questions & short questions for Computer Science Engineering (CSE) on EduRev as well by searching above.
QUESTION: 1

Which of the following is called Bar-Hillel lemma?

Solution:

 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.

QUESTION: 2

Which of the expressions correctly is an requirement of the pumping lemma for the context free languages?

Solution:

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

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

Solution:

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

QUESTION: 4

Which of the following gives a positive result to the pumping lemma restrictions and requirements?

Solution:

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.

QUESTION: 5

 Using pumping lemma, which of the following cannot be proved as ‘not a CFL’?

Solution:

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

QUESTION: 6

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

Solution:

 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.

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

Solution:

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

QUESTION: 8

The pumping lemma is often used to prove that a language is:

Solution:

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.

QUESTION: 9

 What is the pumping length of string of length x?

Solution:

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.

QUESTION: 10

Which of the following does not obey pumping lemma for context free languages ?

Solution:

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

Related tests