Pumping lemma and non-regular language

Pumping Lemma and Non-Regular Languages

The Pumping Lemma is a fundamental tool in the theory of formal languages, particularly in proving that certain languages are non-regular. It provides a necessary property that all regular languages must satisfy. The Pumping Lemma for regular languages is often used to demonstrate that a given language is not regular by showing that it fails to satisfy this property.

Pumping Lemma for Regular Languages

The Pumping Lemma states that for any regular language $L$, there exists a constant $p$ (called the pumping length) such that any string $s$ in $L$ that has a length greater than or equal to $p$ can be split into three parts, $s = xyz$, satisfying the following conditions:

1. Length of y: $|y| > 0$, meaning $y$ is non-empty.
2. Length of x and y: $|xy| \leq p$, meaning the length of the combined string $xy$ is at most $p$, which ensures that $x$ and $y$ are within the first $p$ characters of $s$.
3. Pumping Condition: For all $i \geq 0$, the string $xy^i z$ is also in the language $L$. This means that repeating (pumping) the portion $y$ any number of times (including zero) results in a string that still belongs to the language $L$.

In other words, if $L$ is a regular language, for any sufficiently long string $s \in L$, we can decompose $s$ into three parts $x$, $y$, and $z$ such that the middle part $y$ can be "pumped" (repeated any number of times) and the resulting strings will still belong to the language.

Pumping Lemma Formal Statement

Let $L$ be a regular language. Then there exists a constant $p$ (the pumping length) such that for any string $s \in L$ with $|s| \geq p$, we can write $s$ as:

$$s = xyz$$

where:

• $|xy| \leq p$,
• $|y| > 0$,
• For all $i \geq 0$, $xy^i z \in L$.

Using the Pumping Lemma to Prove a Language is Non-Regular

To prove that a language $L$ is non-regular, we can use the pumping lemma to derive a contradiction. Here's how the process works:

1. Assume that $L$ is regular.
2. By the pumping lemma, there exists a pumping length $p$ for $L$.
3. Choose a string $s \in L$ such that $|s| \geq p$.
4. Decompose $s$ into three parts $s = xyz$, where:
   • $|xy| \leq p$,
   • $|y| > 0$,
   • For all $i \geq 0$, $xy^i z \in L$.
5. Analyze what happens when the string is pumped, particularly for different values of $i$. If for any $i$, the resulting string $xy^i z$ does not belong to $L$, then we have a contradiction.
6. Conclusion: Since we reached a contradiction, our original assumption that $L$ is regular must be false. Therefore, $L$ is non-regular.

Example: Using the Pumping Lemma to Prove a Language is Non-Regular

Consider the language $L = \{ a^n b^n | n \geq 0 \}$, which consists of strings of the form $a^n b^n$ where the number of $a$'s is equal to the number of $b$'s.

We want to prove that $L$ is non-regular using the pumping lemma.

Step 1: Assume $L$ is Regular

Assume that $L$ is regular. Then, by the pumping lemma, there exists a pumping length $p$ such that any string $s \in L$ of length at least $p$ can be split into three parts $s = xyz$ such that:

• $|xy| \leq p$,
• $|y| > 0$,
• For all $i \geq 0$, $xy^i z \in L$.

Step 2: Choose a String $s \in L$

Let’s choose the string $s = a^p b^p$. Clearly, $s \in L$ because it has $p$ $a$'s followed by $p$ $b$'s.

Step 3: Decompose the String $s = xyz$

According to the pumping lemma, we can decompose $s = a^p b^p$ into parts $x$, $y$, and $z$ such that:

• $|xy| \leq p$,
• $|y| > 0$,
• $xy^i z \in L$ for all $i \geq 0$.

Since $|xy| \leq p$, both $x$ and $y$ must consist only of $a$'s. So, $x = a^k$ and $y = a^m$ for some $k$ and $m$, where $m > 0$ (since $|y| > 0$).

Thus, the decomposition is:

$$s = a^k a^m b^p = a^{k+m} b^p.$$

Step 4: Pump the String

Now, pump the middle part $y$ (the part consisting of $a$'s):

• For $i = 2$, we get the string $xy^2 z = a^k a^{2m} b^p = a^{k+2m} b^p$.
• This string is not in $L$ because the number of $a$'s and $b$'s is no longer equal.

Thus, we have a contradiction, as the string $xy^2 z$ does not belong to $L$, which contradicts the pumping lemma.

Step 5: Conclusion

Since we have reached a contradiction, our assumption that $L$ is regular must be false. Therefore, the language $L = \{ a^n b^n | n \geq 0 \}$ is non-regular.

Non-Regular Languages

A non-regular language is a language that cannot be recognized by any finite automaton. These languages do not satisfy the pumping lemma for regular languages, and therefore, they cannot be described by regular expressions, finite automata, or DFAs. Some classic examples of non-regular languages include:

1. $L = \{ a^n b^n | n \geq 0 \}$: As shown above, this language is non-regular.
2. $L = \{ w \mid w \text{ contains the same number of a's as b's} \}$: This language involves counting, which is not possible with a finite state machine.
3. $L = \{ a^n b^n c^n | n \geq 0 \}$: This language requires counting three different symbols, which finite automata cannot handle.

Conclusion

The Pumping Lemma is a powerful tool for proving that certain languages are non-regular. It essentially shows that for regular languages, there is a property that all sufficiently long strings must have, which involves repeating parts of the string. If a language fails to meet this property, it cannot be regular. The pumping lemma is used to derive contradictions by showing that no matter how you decompose a string in a non-regular language, pumping it will lead to a string that is not in the language, thereby proving that the language is non-regular.