Proving Languages to be not Regular (Pumping Lemma)

Proving Languages to be not Regular (Pumping Lemma)

AU: May-04,06,07,12, Dec.-12,13,14,15, Marks 6

• Pumping lemma is a basic and important theorem used for checking whether given string is accepted by regular expression or not. In short, this lemma tells us whether given language is regular or not.

• One key them is that any language for which it is possible to design the finite automata is definitely the regular language.

Theorem: Let L be a regular set. Then there is a constant n such that if Z is any word in L and |Z| ≥ n we can write z = u v w such that |u v| ≤ n, |v| ≥ 1 for all i ≥ 0, u vⁱ w is in L. The n should not be greater than the number of states.

Proof: If the language L is regular it is accepted by a DFA. M = (Q, Σ, δ, q₀, F). With some particular number of states say, n. Consider the input can be a₁, a₂, a₃, .... a_m, m≥n. The mapping function δ could be written as δ(q₀, q₁, q₂, q₃ ... q_i) = q_i

The transition diagram is as shown in Fig. 2.6.1.

If q_m is in F i.e. q₁, q₂, q₃, … q_m is in L(M) then a₁, a₂,...a_j a_k+1 a_k+2 ......a_m is also in L(M)

. Since there is path from q₀ to q_m that goes through q_j but not around the loop labelled a_j+1 .... a_k. Thus

δ (q₀, a₁, a_j a_k+1 ...a_m) = δ (δ (q₀, q₁, ... q_j), a_k+1 .... a_m)

= δ (q_j, q_k+1 ...q_m)

= δ (q_k, q_k+1 ...q_m)

= q_m

That is what we have proved that given any long string can be accepted by FA, we should be able to find a substring near the beginning of the string that may be pumped i.e. repeated as many times as we like and resulting string may be accepted by FA.

• Advantage of Pumping Lemma

The pumping lemma is used to check whether given language is regular or not.

Example 2.6.1 Show that the set L = { bⁱ² |i>1} is not regular. AU: May-06, Marks 6

OR

ii) Prove that L = {0ⁱ² /i is an integer; i≥1 is not regular. AU: Dec.-14, 15, Marks 6

Solution: We have to prove that the language L= bⁱ² is not regular. This language is such that number of b's is always a perfect square.

For example, if we take i = 1

L = b1² = b       the length = 1²

= b2² = bbbb          length = 2²

and so on.

Now let us consider

L = bn² where        length = n²

it is denoted by z.

|z| = n²

By pumping lemma z = u v w

where 1 ≤ |v| ≤ n

As z = uvⁱ w where i = 1

Now we will pump v i.e. make i = 2.

As we made i = 2 we have added one n².

1≤ | v | ≤ n.

n² +1 ≤ uvw | ≤ n+n²

i.e. n² +1 ≤ | uvw | ≤ n² +n+n+1

i.e. n² +1 ≤ | uvw | ≤ (n+1)²

= n² ≤ | uvw | ≤ (n+1)²

Thus the string lies between two consequetive perfect squares. But the string is not a perfect square. Hence we can say the given language is not regular.

For example,

L = bi²

Let i = 2

L = bbbb

L = uvw

Assume  uvw = bbbb

Take

u = b

v = bb

w = b

By pumping lemma, even if we pump v i.e. increase v then language should show the length as perfect square.

= uvw

= uv. vw

= bbbbbb

= length of b is not a perfect square

Thus the behaviour of the language is not regular, as after pumping something onto it does not show the same property (being square for this example.)

Example 2.6.2 Is the following language regular ? Justify your answer

L = {0²ⁿ|n≥1}

AU: May-07, Marks 2, May-13, Marks 4

Solution: This is a language length of string is always even.

i.e.

n = 1;      L = 00

n =2        L = 00 00 and so on.

Let    L = uvw

L = 0²ⁿ

|z| = 2ⁿ = u vⁱ w

If we add 2n to this string length.

|z| = 4n = uv. vw

= even length of string.

Thus even after pumping 2n to the string we get the even length. So the language L is regular language.

Example 2.6.3 Show that L = {0ⁿ 1ⁿ⁺¹ | n>0} is not regular.

Solution: Let us assume that L is a regular language.

|z| = |uvw|

= 0ⁿ 1ⁿ⁺¹

Length of string [z] = n + n + 1 = 2n + 1.

That means length is always odd.

By pumping lemma

= |uv. vw|

That is if we add 2n + 1

2n + 1 < (2n + 1) + 2n + 1

2n+1 < 4n+ 2

But if n = 1 then we obtain 4n+ 2 = 6 which is no way odd. Hence the language becomes irregular.

Even if we add 1 to the length of |z|, then

|z| = 2n + 1 + 1

= 2n + 2

= even length of the string.

So this is not a regular language.

Example 2.6.4 Show that set L = (0ⁱ1ⁱ | i ≥ 1} is not regular. AU: May-04, Dec.-04,05, Marks 6

Solution: Assume that L = {0ⁱ 1ⁱ | i ≥ 1} is regular.

Let, w = 0 1 such that |w| = 2n. By pumping lemma we can write

w = xyz such that |xy| ≤ n and |y| ≠ 0.

Now if xy¹z ϵ L then the language L is said to be regular.

There are many cases - i) y has only 0's ii) y has only 1's iii) y has both 0's and 1's. i) If y has only O's then the string

w = 0^n-k|n = xz since y = 0^k and i = 0

Surely n-k ≠ n. Hence xz € L.

Hence our assumption of being L regular is wrong.

ii) If y has only 1's then, for i = 0 and y = 1^k

w = xz = 0ⁿ 1^n-k

As n ≠ n-k, xz = w € L

Again L is not regular.

iii) If y has 0's and 1's then

w = 0^n-k 0^k 1^j 1^n-j = xyⁱ z

If i = 2 then

w = 0^n-k 0^2k 1^2j 1^n-1 € L

Hence from all these 3 cases it is clear that language L is not regular.

Example 2.6.5 Which of the following languages is regular? Justify.

1) L = {aⁿ b^m | n, m ≥ 1}

2) L = {aⁿ bⁿ | n ≥ 1} AU: May-12, Marks 8

Solution : 1) Let, L = {an bm | n, m ≥ 1}

Here the number of a's and b's can be at least one. We can write the regular expression for given L as

r.e. = a⁺ b⁺

For this regular expression the FA can be

As we can draw the FA for representing given language, the given L is said to be regular.

2) Given L = {aⁿ bⁿ | n ≥ 1} is not regular. Refer similar example 2.6.4.

Example 2.6.6 Using pumping lemma for the regular sets, prove that the language L= {a^mbⁿ | m>n} is not regular.  AU: Dec.-12, Marks 10

Solution: Let us assume that L is a regular language. The string W ϵ L such that

|W| = | xyz | = a^m bⁿ

Length of string |W| = m + n, where m > n. By pumping lemma we can write

W = xyz such that |xy| ≤ n |y| ≠ 0.

Now if xyⁱz ϵ L then the language is said to be regular.

There are many cases: i) y has only a's

ii) y has only b's

iii) y has both a's and b's.

i) If y has only a's then assume W = a³ b².

If we map W = xyⁱz with i = 0. Then W in equation (1) becomes

W= a aa bb

x=a, y=aa, z=bb

W = xz             y¹ = y⁰ = 1

W = abb = a¹b² € {L = a^m bⁿ | m>n}

ii) y has only b's then assume W = a³ b²

If we map W = xyⁱz with i = 3 then W in equation (2) becomes

Regular Expressions and Languages

W= aaa bb

x = aaa

y = b

z = b

W = (aaa) (bbb) (b)

W = a³ b⁴ € {L = a^m bⁿ | m > n}

iii) y has both a's and b's. Then assume W = a³ b².

If we map W = xyⁱz with i = 2 then W in equation (3) becomes

W = aa ab b

x = aa

y = ab

z = b

W = (aa) (abab) (b)

= a³ bab² € a^mbⁿ

From above three cases it is clear that our assumption of L being regular is wrong. This proves that given L = a^mbⁿ is not regular.

The simple way to know whether given language is regular or not is that try to draw finite automata for it, if you can easily draw the FA for the given L then that language is surely the regular otherwise not.

Example 2.6.7 Using pumping lemma for regular sets, prove that the language L = {0^m1ⁿ 0^m+n | m ≥ 1 and n ≥ 1} is not regular.  AU: Dec.-13, Marks 10

Solution: Let us assume that L is a regular language. The input string w ϵ L such that

|w| = | xyz | = 0^m1ⁿ 0^m+n

By pumping lemma we can write

w = xyz such that |xy| ≤ n and |y| ≠ 0.

There are three cases: i) y has only 0's

ii) y has only 1's

iii) y has 0's and 1's.

Case i) y has only 0's

Consider w = 00010000

If we map w = xyz then

By pumping lemma,

w = xyⁱz

W = 0 00 10000

0 = x, 00 = y, 10000 = z

if i = 2 then

w = xyyz i.e.

= 0(00) (00) (10000)

W = 0⁵ 1¹ 0⁴ € 0^m 1ⁿ 0^m+n

Case ii) y has only 1's

Consider w = 00110000

If we map w = xyz then

By pumping lemma,

w = 00 11 0000

x = 00, y = 11, z = 0000

w = xyⁱz

if i = 2 then

w = xyyz i.e.

= 00(11) (11) (0000)

= 0² 1⁴ 0⁴ € 0^m 1ⁿ 0^m+n

Case iii) y has 0's and 1's

Consider w = 001000

w = 0 01 000

x = 0, y = 01, z = 000

If we map w = xyz then

By pumping lemma,

w = xyⁱz

If i = 2 then

w = xyyz i.e.

= 0 (01) (01) (000)

= 0²1 0¹1¹0³ € 0^m1ⁿ 0^m+n

From above three cases, it is clear that our assumption of L being regular is wrong. This proves that given L = 0^m1ⁿ 0^m+n is not regular.

Example 2.6.8 Prove that following languages are not regular:

i) { w ϵ {a,b}^* |w = w^R} ii) Set of strings of 0's and 1's beginning with 1, whose value treated as a binary number is prime. AU: Dec.-19, Marks 13

Solution: i) Let, the given language

• L = {w ϵ {a, b}* |w = w^R} is regular

• Suppose there is a DFA for L with p states. Let w be word in L. We will pump the strings, such that

w = xyz.

• We will choose w = 0^P10^P ϵ L

• By pumping Lemma,

w = xyz, y ≥ 1,|xy|≤ p and

w = xyⁱz is in L for every i

• The pumping part is at the beginning of string. Hence |xy|≤ p and xy consists of 0's only

• Since |y| ≥ 1, y contains at least one 0.

• If i = 2 then w = xyyz and it must ϵ L

if w = 00 0 1000

x = 00

y = 0

z = 1000

w = xyyz

w = 00001000 € L

• This shows that, our assumption of being L is regular is wrong.

• This proves that given language is not regular.

ii) L = Binary numbers of prime numbers

Let, w = xyz ϵ L we assume that L is a binary language of prime numbers.

• Assume | xyz |= n.

• Assume L is regular.

• By pumping lemma.

w = xyz, |y| ≥ 1, |xy| ≤  p and w = xyⁱz is in L for every i

• i = 2, then

w = xyyz

|w| = n+1 € L

This shows that our assumption of L being regular is wrong and L is non-regular.