Pumping Lemma
Theory of Computation
Theory of computation, quite often referred to as the Automata Theory, is a branch of Computer Science as well as Mathematics that is concerned with the computational logic in basic machines. This computational logic is referred to as Automata.
Automata helps science professionals to understand the computational functioning characteristics of machines and their problem solving characteristics. The idea behind this development was to invent methods and analyze their dynamic behavior of discrete systems.
Now, let us have a look at some of its important basic terminologies.
● Symbol: A figure, alphabet or a number.
● Alphabets (Σ): A finite set of symbols.
● String: A finite set of symbols derived from some alphabet which is often denoted as w and it’s length is denoted by |w|.
● Language: A Finite or Infinite subset of Σ*.
Pumping Lemma in Theory of Computation
There are two Pumping Lemmas defined for:
- Regular Languages, and
- Context — Free Languages
Pumping Lemma for Regular Languages
Let us consider a regular language L and and integer n existing for any L in a way that for all x ∈ L with |x| ≥ n, there exists u, v, w ∈ Σ∗, such that x = uvw, and
1) |uv| ≤ n
2) |v| ≥ 1
3) For all i ≥ 0: uv^iw ∈ L
In a much easier understanding one must state that no matter how many times a string v is ‘pumped’ or is inserted, the resultant string will always remain the same in L.
Pumping Lemma in a regular language is used as a proof for its irregularity. Therefore, every regular language should always satisfy pumping conditions. Even if there is just one string which is derived from pumping and is not present in L then we can conclude that L is surely not a regular language.
The converse might not always be true which means that if string is present in L then L being a regular language is not mandatory.
Pumping Lemma for Context- Free Languages
The CFL Pumping Lemma states that for any Context Free Language L, two substrings can be ‘pumped’ any number of times while remaining in the same language. We split the strings of any language L into five parts and pump the second and fourth substrings.
Pumping lemma is used to prove that a language is not context-free in Context-Free Languages, which means that if there is just one string derived from pumping that does not meet the pumping requirements, we may infer that L is not a context-free language.
Therefore, if L is a CFL, there exists an integer n, such that for all x ∈ L with |x| ≥ n, there exists u, v, w, x, y ∈ Σ∗, such that x = uvwxy, and
1) |vwx| ≤ n
2) |vx| ≥ 1
3) For all i ≥ 0: uv^iwx^iy ∈ L
Conclusion
In this blog, we covered all the important constituents of Pumping Lemma which included the introduction of the Automata Theory and it’s basic terminologies. Later, we dived into the Pumping Lemma for the Theory of Computation defined for both Regular and Context- Free Languages explained with the help of suitable examples.
If we combine all the discussed information then we can conclude that the Pumping Lemma depicts a crucial characteristic for all regular languages in the theory of formal languages. In an easier language, it states that preferably all long strings present in a regular language may have a central part of the string which is repeated for an erratic number of times which further leads to a new string which is also the constituent of the language which means that they may be pumped.
References:
- Introduction of Theory of Computation — GeeksforGeeks
- Pumping Lemma in Theory of Computation — GeeksforGeeks
- Pumping lemma for regular languages — Wikipedia
Co Authors: Shresthi Yadav, Mohit Lalwani, Anushka Wankhade, Nitesh Sonawane.
