Theory

1.Context free grammar

CFG stands for context-free grammar. It is is a formal grammar which is used to generate all possible patterns of strings in a given formal language. Context-free grammar G can be defined by four tuples as:

V - It is the collection of variables or nonterminal symbols. T - It is a set of terminals. P - It is the production rules that consist of both terminals and nonterminals. S - It is the Starting symbol.

Pumping lemma for context free Language

Pumping lemma for context free language (CFL) is used to prove that a language is not a Context free language

Theorem

If A is a context free language ,then ,A has a pumping length “p” such that any string “S’, where |S|>= p may be divided into 5 pieces S=uvxyz such that the following conditions must be true :

1. Uvⁱxyⁱz is in the A for every i≥0

2. |vy|>0

3. |vxy|≤p

Steps to apply pumping lemma

Assume that L is context-free.

The pumping length will be p.

All strings longer than the length(p) can be pumped |S|≥ p.

Now we have to find a string 'S' in L such that |S|≥ p.

We will divide string 'S' into uvxyz.

Now show that uvⁱxyⁱz ∉L for some constant i.

Then, we have to consider the ways that S can be divided into uvxyz.

Show that none of these can satisfy all the 3 pumping conditions simultaneously.

A string 'S' cannot be pumped (contradiction).

Detailed description of the steps mentioned above:

1. Assume the language L is context-free: This is our starting point for the proof.

2. Identify the pumping length (p): The lemma guarantees the existence of a pumping length p for any context-free language. This p applies to all strings in the language with a length greater than or equal to p (L ≥ p).

3 .Choose a string S ∈ L and |S| ≥ p: Select a string S from the language L that has a length greater than or equal to the pumping length (n).

4. Divide S into five substrings as follows:

u: The prefix before the "pumping section" (can be empty).

v: The substring to be "pumped" (must have at least one symbol).

x: A separator between v and y (can be empty).

y: A copy of v (can be empty).

z: The suffix after the "pumping section" (can be empty).

Therefore, the string w can be represented as S = uvxyz.

5. Apply pumping for different values of i: The lemma states that we can "pump" the substring v by inserting copies of it i times (where i is a non-negative integer) and obtain a new string.

6. Analyze the resulting strings: The key step is to analyze the resulting strings (uwxz, S, and uvⁱxyⁱz) and show that at least one of them does not belong to the language L. This contradicts the initial assumption that L is context-free.

If uwxz is not in L, the language is not context-free because it cannot generate this string even though it's derived from a valid string in L.

If uvⁱxyⁱz is not in L for any i ≥ 2, the language is not context-free because it cannot generate strings with more than one copy of the "pumping section" v, even though longer strings exist in the language.