Explain the concept of pumping lemma for regular sets. Show that following expression is regular or not regular using pumping lemma. ( L = {a^n b^m : n <= m}

 

Pumping lemma for regular languages

The pumping lemma is a property of a regular language. It is used to prove the non-regularity of certain languages.

Regular languages always satisfy the pumping lemma. However, if the pumping lemma is satisfied, the language does not need to be regular.

Note: This is only useful for infinite languages since all finite languages are regular.

Theorem

In simple terms, this theorem states that if $L$ is a regular language ∃ (there exists), a FA of $p$ states holds string $s ∈ L$. Then, for all strings $s ∈ L$, with $|s| ≥ p$, there exists a division of $s$ in three parts, i.e., $S= x.y.z$, such that the following three conditions are held:

• $|x.y| ≤ p$ (length of $x$ + length of $y$ is $≤ p$)
• $|y| != 0$ ( $x$,$z$ can be null, but $y$ cannot be null, and the length of $y ≥ 1$)
• $xy^iz ∈ L \ ∀ \ i ≥ 0$

Let's look at an example where the pumping lemma does not hold.

To prove that a language is regular using the pumping lemma, we need to show that there exists a constant "p" such that for every string "s" in the language, "s" can be broken down into three substrings "s1", "s2", and "s3" such that "s1s2s3" is a valid representation of "s", and the following conditions hold:

1. |s1s2| <= p
2. |s2| > 0
3. For all "i" >= 0, "s1s2^is3" is in the language

To prove that a language is not regular using the pumping lemma, we need to show that for every "p", there exists a string "s" in the language such that the three substrings "s1", "s2", and "s3" cannot be chosen such that the conditions of the pumping lemma are satisfied.

In this case, the language L is defined as the set of all strings of the form (a^n)*( b^m), where n <= m.

To prove that L is not regular using the pumping lemma, we can take "p" to be any positive integer. Then, we can choose the string s to be the string "a^pb^(p)". This string is in the language L, because it has the form (a^n)( b^m) with n = p <= m = p.

Now, we need to show that there do not exist three substrings "s1", "s2", and "s3" such that "s1s2s3" is a valid representation of s and the conditions of the pumping lemma are satisfied.

Suppose we try to break down the string s into three substrings s1, s2, and s3 such that |s1s2| <= p and |s2| > 0. Then, s2 must contain at least one "a" and at least one "b". But this means that the string s1s2s3 will contain more "b"s than "a"s, which is not possible because s1s2s3 is a valid representation of s, which must contain the same number of "a"s and "b"s.

Therefore, we have shown that there do not exist three substrings "s1", "s2", and "s3" such that "s1s2s3" is a valid representation of s and the conditions of the pumping lemma are satisfied. This means that the language L is not regular.