Lab Session #4 #

Agenda #

Recap: Pumping lemma
Exercises

Pumping lemma #

In the theory of formal languages, the pumping lemma for regular languages is a lemma that describes an essential property of all regular languages. Informally, it says that all sufficiently long strings in a regular language may be pumped—that is, have a middle section of the string repeated an arbitrary number of times—to produce a new string that is also part of the language.

The pumping lemma is stated as follows:

Given a regular language \( \bf L \) there exists an integer (critical length) \( \bf m \) such that for any string \( \bf w \isin L \) with length \( \bf |w| \ge m \) we can find a split \( \bf w = x y z \) such that:

\( \bf |xy| \leq m \)
\( {\bf |y|} \ge 1 \)
\( \bf xy^iz \isin L \) for all \( i \ge 0 \)

The pumping lemma can be used to prove that a language is not regular by finding a string in the language that does not satisfy the pumping lemma. For example, the language of all strings that are balanced parentheses is not regular. The string “(()” can be pumped to produce the strings “()()” and “(())”, but the latter string is not balanced.

The pumping lemma is a powerful tool for proving that a language is not regular. However, it is important to note that the pumping lemma does not prove that a language is regular. A language that satisfies the pumping lemma may still be irregular.

Here are some examples of regular languages:

The language of all strings of 0s and 1s
The language of all strings of lowercase letters
The language of all strings of uppercase letters
The language of all strings of digits

Here are some examples of languages that are not regular:

The language of all strings that are balanced parentheses
The language of all strings that are palindromes
The language of all strings that are prime numbers

The pumping lemma is a useful tool for understanding the structure of regular languages. It can be used to prove that a language is not regular, and it can also be used to help design regular expressions.

Pumping lemma: contrapositive #

The contrapositive of a statement is the statement that reverses and negates both the hypothesis and the conclusion. In other words, the contrapositive of a statement is true if and only if the negation of the conclusion is true.

Given a language \( \bf L \) . If we show that
for any integer \( m \ge 1 \)
there exists a string \( w \isin L \) such that \( |w| \ge m \)
and for all possible splits \( x, y, z \isin \Sigma^* \) with

\( |x \ y| \leq m \)
\( |y| \ge 1 \)
\( x \ y^i \ z \isin L \) \

there exists: \( i \isin \natnums \) such that \( x \ y^i \ z \notin L \) .
Then, applying the Pumping lemma for regular languages, one can deduce that \( L \) is not regular.

Exercises #

Using Pumping lemma prove that \( L_1, \ L_2, \ L_3 \) and \( L_4 \) are not regular languages:

\( L_1 = \{vv^R | v \isin \Sigma_1^* \} \ \) where \( \ \Sigma_1 = \{a, \ b\} \)

Solution:

Let’s take an arbitrary integer \( m \ge 1 \) .
Let \( w = a^m b^m b^m a^m \)
\( |w| = 4m \ge m, \ w \isin L \) .
Split \( w \) in the form \( xyz \) : as \( |xy| \leq m \) and \( w = a^m b^m b^m a^m\) , \(y = a^k \) , \(\ k \ge 1 \) .
Let’s look at \( xy^2z \) . It will have the form \( a^{m+k} b^m b^m a^m \) .
As \( k \ge 1, xy^2z \notin L \) .
We have shown that for any \( m \) we can find \( w \isin L \) , such that \( |w| \ge m \) and for all \( x, \ y, \ z \isin \Sigma^*\) with \( |xy| \leq m \) and \( |y| \ge 1 \) and \( w = xyz \) there exists \( i \isin N \) such that \(xy^iz \notin L \) .
So, applying Pumping lemma we can deduce that \( L \) is not regular.

\( L_2 = \{ v| v \) has an equal number of \( a \) ’s and \( b \) ’s \( \} \ \) over \( \ \Sigma_2 = \{ a, \ b \} \)

Solution:

Let’s take an arbitrary integer \( m \ge 1 \) .
Let \( w = a^m b^m \)
\( |w| = 2m \ge m, \ w \isin L \) .
Split \( w \) in the form \( xyz \) : as \( |xy| \leq m \) and \( w = a^m b^m \) , \( y = a^k \) , \(k \ge 1 \) .
Let’s look at \( xy^2z \) . It will have the form \( a^{m+k}b^m \) . As \( k \ge 1 \) , \( xy^2z \notin L \) .
We have shown that for any \( m \) we can find \( w \isin L \) , such that \( |w| \ge m \) and for all \( x, y, z \isin \Sigma^* \) with \( |xy| \leq m \) and \( |y| \ge 1 \) and \( w = xyz \) there exists \( i \isin N \) such that \( xy^iz \notin L \) .
So, applying Pumping lemma we can deduce that \( L \) is not regular.

\( L_3 = \{ a^{n!} | n \ge 0 \} \ \) over \( \ \Sigma_3 = \{ a \} \)

Solution:

Let’s take an arbitrary integer \( m \ge 1 \) .
Let \( w = a^{m!}\)
\( |w| = m! \ge m,w \isin L \) .
Split \(w\) in the form \(xyz\) : as \(|xy| \leq m \) and \( \ w = a^{m!}\) , \(\ y = a^k\) , \(\ m \ge k \ge 1 \) .
Let’s look at \( xy^2z\) . It will have the form \( a^{m!+k} \) .
As \( k \ge 1, \ m! < m! + k \) .
As \( m \ge k, \ m! + k \leq m! + m \) .
By algebra, \( m! + m < (m + 1)!^1 \) , as \((m + 1)! = m! + m! ∗ m \)
So for \( m > 1 \) we get that \( m! < m! + k < (m + 1)! \) , which means that there is no such \( p \isin \natnums \) that \( (m! + k) = p!\) , so \( xy^2z \notin L \)
For \( m = 1,w = a, \) so \( y = a \) , and the string \( xy^3 z = aaa \notin L \) Applying Pumping lemma we can deduce that \(L_3\) is not regular.

\( ^1\) for \(m > 1\)

\( L_4 = \{ a^n b^l c^{n+l} | n, l \ge 0 \} \ \) over \( \ \Sigma_4 = \{ a, b, c \} \)

Solution:

Let’s take an arbitrary integer \(m \ge 1\) .
Let \( w = a^mb^mc^{2m} \)
\( |w| = 4m \ge m,w \isin L\) .
Split \(w\) in the form \(xyz\) : as \( |xy| \leq m \) and \( w = a^mb^mc^{2m}\) , \(\ y = a^k\) , \(\ k \ge 1 \) .
Let’s look at \( xy^2 z \) . It will have the form \( a^{m+k} b^mc^{2m}\) .
As \(k \ge 1, \ xy^2z \notin L\) , applying Pumping lemma we can deduce that \( L_4\) is not regular.