Test: Pumping Lemma for Context Free Language - Computer Science Engineering (CSE) MCQ

 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.

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ⁿwxⁿy ∈ L

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

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.

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

 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.

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

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.

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.

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