Lab 4 - PL

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 L \bf L there exists an integer (critical length) m \bf m such that for any string w∈L \bf w \isin L with length ∣w∣≥m \bf |w| \ge m we can find a split w=xyz \bf w = x y z such that:

  • ∣xy∣≤m \bf |xy| \leq m
  • ∣y∣≥1 {\bf |y|} \ge 1
  • xyiz∈L \bf xy^iz \isin L for all i≥0 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 L \bf L . If we show that
for any integer m≥1 m \ge 1
there exists a string w∈L w \isin L such that ∣w∣≥m |w| \ge m
and for all possible splits x,y,z∈Σ∗ x, y, z \isin \Sigma^* with

  • ∣x y∣≤m |x \ y| \leq m
  • ∣y∣≥1 |y| \ge 1
  • x yi z∈L x \ y^i \ z \isin L \

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

Exercises #

Using Pumping lemma prove that L1, L2, L3 L_1, \ L_2, \ L_3 and L4 L_4 are not regular languages:

  1. L1={vvR∣v∈Σ1∗}  L_1 = \{vv^R | v \isin \Sigma_1^* \} \ where  Σ1={a, b} \ \Sigma_1 = \{a, \ b\}
Solution:
Let’s take an arbitrary integer m≥1 m \ge 1 .
Let w=ambmbmam w = a^m b^m b^m a^m
∣w∣=4m≥m, w∈L |w| = 4m \ge m, \ w \isin L .
Split w w in the form xyz xyz : as ∣xy∣≤m |xy| \leq m and w=ambmbmam w = a^m b^m b^m a^m , y=aky = a^k ,  k≥1\ k \ge 1 .
Let’s look at xy2z xy^2z . It will have the form am+kbmbmam a^{m+k} b^m b^m a^m .
As k≥1,xy2z∉L k \ge 1, xy^2z \notin L .
We have shown that for any m m we can find w∈L w \isin L , such that ∣w∣≥m |w| \ge m and for all x, y, z∈Σ∗ x, \ y, \ z \isin \Sigma^* with ∣xy∣≤m |xy| \leq m and ∣y∣≥1 |y| \ge 1 and w=xyz w = xyz there exists i∈N i \isin N such that xyiz∉Lxy^iz \notin L .
So, applying Pumping lemma we can deduce that L L is not regular.
  1. L2={v∣v L_2 = \{ v| v has an equal number of a a ’s and b b ’s }  \} \ over  Σ2={a, b} \ \Sigma_2 = \{ a, \ b \}
Solution:
Let’s take an arbitrary integer m≥1 m \ge 1 .
Let w=ambm w = a^m b^m
∣w∣=2m≥m, w∈L |w| = 2m \ge m, \ w \isin L .
Split w w in the form xyz xyz : as ∣xy∣≤m |xy| \leq m and w=ambm w = a^m b^m , y=ak y = a^k , k≥1k \ge 1 .
Let’s look at xy2z xy^2z . It will have the form am+kbm a^{m+k}b^m . As k≥1 k \ge 1 , xy2z∉L xy^2z \notin L .
We have shown that for any m m we can find w∈L w \isin L , such that ∣w∣≥m |w| \ge m and for all x,y,z∈Σ∗ x, y, z \isin \Sigma^* with ∣xy∣≤m |xy| \leq m and ∣y∣≥1 |y| \ge 1 and w=xyz w = xyz there exists i∈N i \isin N such that xyiz∉L xy^iz \notin L .
So, applying Pumping lemma we can deduce that L L is not regular.
  1. L3={an!∣n≥0}  L_3 = \{ a^{n!} | n \ge 0 \} \ over  Σ3={a} \ \Sigma_3 = \{ a \}
Solution:
Let’s take an arbitrary integer m≥1 m \ge 1 .
Let w=am! w = a^{m!}
∣w∣=m!≥m,w∈L |w| = m! \ge m,w \isin L .
Split ww in the form xyzxyz : as ∣xy∣≤m|xy| \leq m and  w=am! \ w = a^{m!} ,  y=ak\ y = a^k ,  m≥k≥1\ m \ge k \ge 1 .
Let’s look at xy2z xy^2z . It will have the form am!+k a^{m!+k} .
As k≥1, m!<m!+k k \ge 1, \ m! < m! + k .
As m≥k, m!+k≤m!+m m \ge k, \ m! + k \leq m! + m .
By algebra, m!+m<(m+1)!1 m! + m < (m + 1)!^1 , as (m+1)!=m!+m!∗m(m + 1)! = m! + m! ∗ m
So for m>1 m > 1 we get that m!<m!+k<(m+1)! m! < m! + k < (m + 1)! , which means that there is no such p∈N p \isin \natnums that (m!+k)=p! (m! + k) = p! , so xy2z∉L xy^2z \notin L
For m=1,w=a, m = 1,w = a, so y=a y = a , and the string xy3z=aaa∉L xy^3 z = aaa \notin L Applying Pumping lemma we can deduce that L3L_3 is not regular.

1 ^1 for m>1m > 1
  1. L4={anblcn+l∣n,l≥0}  L_4 = \{ a^n b^l c^{n+l} | n, l \ge 0 \} \ over  Σ4={a,b,c} \ \Sigma_4 = \{ a, b, c \}
Solution:
Let’s take an arbitrary integer m≥1m \ge 1 .
Let w=ambmc2m w = a^mb^mc^{2m}
∣w∣=4m≥m,w∈L |w| = 4m \ge m,w \isin L .
Split ww in the form xyzxyz : as ∣xy∣≤m |xy| \leq m and w=ambmc2m w = a^mb^mc^{2m} ,  y=ak\ y = a^k ,  k≥1\ k \ge 1 .
Let’s look at xy2z xy^2 z . It will have the form am+kbmc2m a^{m+k} b^mc^{2m} .
As k≥1, xy2z∉Lk \ge 1, \ xy^2z \notin L , applying Pumping lemma we can deduce that L4 L_4 is not regular.