Lecture 13: Properties of regular languages

(1)

CS310 : Automata Theory 2020

Lecture 13: Properties of regular languages

Instructor: S. Akshay

IIT Bombay, India

10-02-2020

(2)

Recap

I Automata models: DFA, NFA,-NFA I Algebraic model: Regular expressions

I Regular languages: All these models accept the same class of languages.

I Conversions: from NFA to DFA (Subset construction),-NFA to DFA, Regular expressions to -NFA, DFA to regular expressions

I Applications: text search using automata, regular expressions in GREP, emacs, python etc.

I Properties of regular languages

I Closure - under union, intersection, complementation, reversal I Pumping lemma.

I Limitations of regular languages: Examples of non-regular languages and how to show non-regularity using pumping lemma.

(3)

Recap

(4)

Recap

(5)

Recap

(6)

Pumping lemma

Theorem (Pumping lemma): Let L be a regular language. Then I there exists a constant n such that

I for every word w ∈Lsuch that|w| ≥n,

I we can breakw into three wordsw =xyz, such that 1. y 6=,

2. |xy| ≤n, and

3. for allk ≥0,xy^kz ∈L.

Contrapositive of Pumping lemma: If I for all n,

I there is a word w ∈Lsuch that |w| ≥n,

I for each breakup of w into three words w =xyz such that 1. y 6=and

2. |xy| ≤n,

there is a k ≥0 such thatxy^kz 6∈L,thenL is not regular.

(7)

Pumping lemma

Theorem (Pumping lemma): Let L be a regular language. Then I there exists a constant n such that

I for every word w ∈Lsuch that|w| ≥n,

I we can breakw into three wordsw =xyz, such that 1. y 6=,

2. |xy| ≤n, and

3. for allk ≥0,xy^kz ∈L.

Contrapositive of Pumping lemma: If I for all n,

I there is a word w ∈Lsuch that |w| ≥n,

I for each breakup of w into three words w =xyz such that 1. y 6=and

2. |xy| ≤n,

(8)

Proving a language non regular

Consider language L

I For eachn, wepropose a word w ∈L of length at leastn

I We define parameterized word x and non-empty word y such that I xyz =w for some z and

I the parameter space coversall x andy such that |xy| ≤n. I For each split x andy, we choose ak such that xy^kz 6∈L. We have proven thatLis not regular.

(9)

Proving a language non regular

Consider language L

I For eachn, wepropose a wordw ∈L of length at leastn

I the parameter space coversall x andy such that |xy| ≤n. I For each split x andy, we choose ak such that xy^kz 6∈L. We have proven thatLis not regular.

(10)

Proving a language non regular

Consider language L

I the parameter space coversall x andy such that |xy| ≤n.

I For each split x andy, we choose ak such that xy^kz 6∈L. We have proven thatLis not regular.

(11)

Proving a language non regular

Consider language L

I For each split x andy, we choose ak such that xy^kz 6∈L.

We have proven thatLis not regular.

(12)

Proving a language non regular

Consider language L

I For each split x andy, we choose ak such that xy^kz 6∈L.

We have proven that Lis not regular.

(13)

Some more examples using pumping lemma-I

Consider L_prime ={1^p|p is a prime number.}.

I For eachn, letw = 1^p such thatp >n+ 2 I The first n characters ofw are 1ⁿ.

I Let x= 1ⁱ andy = 1^j, wherei+j ≤n andj 6= 0. w = 1ⁱ

|{z}x

1^j

|{z}y

1^p−j−i

| {z }

z

I So, for any k ≥0, we have|xy^kz|= (p−j) +kj. I Choose k =p−j. Therefore,|xy^kz|= (p−j)(1 +j). I Now (p−k)>1 and 1 +j >1, which impliesxy^kz 6∈L_prime.

(14)

Some more examples using pumping lemma-I

I For eachn, letw = 1^p such thatp >n+ 2

I The first n characters ofw are 1ⁿ.

|{z}x

1^j

|{z}y

1^p−j−i

| {z }

z

(15)

Some more examples using pumping lemma-I

|{z}x

1^j

|{z}y

1^p−j−i

| {z }

z

(16)

Some more examples using pumping lemma-I

I Let x= 1ⁱ andy = 1^j, wherei+j ≤n andj 6= 0.

w = 1ⁱ

|{z}x

1^j

|{z}y

1^p−j−i

| {z }

z

(17)

Some more examples using pumping lemma-I

w = 1ⁱ

|{z}x

1^j

|{z}y

1^p−j−i

| {z }

z

I So, for any k≥0, we have|xy^kz|= (p−j) +kj.

I Choose k =p−j. Therefore,|xy^kz|= (p−j)(1 +j). I Now (p−k)>1 and 1 +j >1, which impliesxy^kz 6∈L_prime.

(18)

Some more examples using pumping lemma-I

w = 1ⁱ

|{z}x

1^j

|{z}y

1^p−j−i

| {z }

z

I So, for any k≥0, we have|xy^kz|= (p−j) +kj. I Choose k =p−j. Therefore,|xy^kz|= (p−j)(1 +j).

I Now (p−k)>1 and 1 +j >1, which impliesxy^kz 6∈L_prime.

(19)

Some more examples using pumping lemma-I

w = 1ⁱ

|{z}x

1^j

|{z}y

1^p−j−i

| {z }

z

I So, for any k≥0, we have|xy^kz|= (p−j) +kj. I Choose k =p−j. Therefore,|xy^kz|= (p−j)(1 +j).

I Now (p−k)>1 and 1 +j >1, which impliesxy^kz 6∈L_prime.

(20)

Some more examples using pumping lemma-II

Exercise

Consider L={1^m²|m≥0}.

I For eachn, letw = 1ⁿ²

|{z}x

1^j

|{z}y

1ⁿ²^−j−i

| {z }

z

I So, |xy^kz|= (n²−j) +kj.

I Let k = 2. Therefore,|xy^kz|=n²+j. I Since 0<j ≤n,n² <n²+j <n²+ 2n+ 1.

Therefore, xy²z 6∈L.

(21)

Some more examples using pumping lemma-II

Exercise

|{z}x

1^j

|{z}y

1ⁿ²^−j−i

| {z }

z

(22)

Some more examples using pumping lemma-II

Exercise

|{z}x

1^j

|{z}y

1ⁿ²^−j−i

| {z }

z

(23)

Some more examples using pumping lemma-II

Exercise

w = 1ⁱ

|{z}x

1^j

|{z}y

1ⁿ²^−j−i

| {z }

z

(24)

Some more examples using pumping lemma-II

Exercise

w = 1ⁱ

|{z}x

1^j

|{z}y

1ⁿ²^−j−i

| {z }

z

I So,|xy^kz|= (n²−j) +kj.

(25)

Some more examples using pumping lemma-II

Exercise

w = 1ⁱ

|{z}x

1^j

|{z}y

1ⁿ²^−j−i

| {z }

z

I Let k = 2. Therefore,|xy^kz|=n²+j.

I Since 0<j ≤n,n² <n²+j <n²+ 2n+ 1. Therefore, xy²z 6∈L.

(26)

Some more examples using pumping lemma-II

Exercise

w = 1ⁱ

|{z}x

1^j

|{z}y

1ⁿ²^−j−i

| {z }

z

I Let k = 2. Therefore,|xy^kz|=n²+j. I Since 0<j ≤n,n²<n²+j <n²+ 2n+ 1.

(27)

Some more examples using pumping lemma-II

Exercise

w = 1ⁱ

|{z}x

1^j

|{z}y

1ⁿ²^−j−i

| {z }

z

I Let k = 2. Therefore,|xy^kz|=n²+j. I Since 0<j ≤n,n²<n²+j <n²+ 2n+ 1.

(28)

Some more examples using pumping lemma-III

Example of pumping down!

Is this regular: L={0^`1^m|` >m}?

I For eachn, letw = 0ⁿ1ⁿ

I Any breakup ofw hasx= 0ⁱ andy = 0^j, wherei+j ≤n andj 6= 0. w = 0ⁱ

|{z}x

0^j

|{z}y

0^n−j−i1ⁿ

| {z }

z

I if k >2, we getxy^kz = 0ⁱ0^j+20^n−j−i1ⁿ∈L, so NOT enough! I However, let k= 0 (pumping down). Then,xy^kz = 0ⁱ0^n−j−i1ⁿ6∈L. I This completes the proof.

(29)

Some more examples using pumping lemma-III

I Any breakup ofw hasx= 0ⁱ andy = 0^j, wherei+j ≤n andj 6= 0. w = 0ⁱ

|{z}x

0^j

|{z}y

0^n−j−i1ⁿ

| {z }

z

(30)

Some more examples using pumping lemma-III

I Any breakup ofw hasx= 0ⁱ andy = 0^j, wherei+j ≤n andj 6= 0.

w = 0ⁱ

|{z}x

0^j

|{z}y

0^n−j−i1ⁿ

| {z }

z

(31)

Some more examples using pumping lemma-III

w = 0ⁱ

|{z}x

0^j

|{z}y

0^n−j−i1ⁿ

| {z }

z

I if k>2, we getxy^kz = 0ⁱ0^j+20^n−j−i1ⁿ ∈L, so NOT enough!

I However, let k= 0 (pumping down). Then,xy^kz = 0ⁱ0^n−j−i1ⁿ6∈L. I This completes the proof.

(32)

Some more examples using pumping lemma-III

w = 0ⁱ

|{z}x

0^j

|{z}y

0^n−j−i1ⁿ

| {z }

z

I However, letk = 0 (pumping down). Then,xy^kz = 0ⁱ0^n−j⁻ⁱ1ⁿ6∈L.

I This completes the proof.

(33)

Some more examples using pumping lemma-III

w = 0ⁱ

|{z}x

0^j

|{z}y

0^n−j−i1ⁿ

| {z }

z

I However, letk = 0 (pumping down). Then,xy^kz = 0ⁱ0^n−j⁻ⁱ1ⁿ6∈L.

I This completes the proof.

(34)

Some more examples using pumping lemma-IV

Using regularity properties Is this regular: L={0^`1^m|`6=m}?

I SupposeL is regular. Note that Σ ={0,1}.

I Consider the language L⁰ =L∩0^∗1^∗, where Lis the complement of L. I This must be regular by closure properties.

I But L⁰ ={0ⁿ1ⁿ|n∈N}, which we know is not regular. I Hence we have a contradiction and Lis not regular.

(35)

Some more examples using pumping lemma-IV

I Consider the language L⁰ =L∩0^∗1^∗, where Lis the complement of L. I This must be regular by closure properties.

(36)

Some more examples using pumping lemma-IV

I Consider the language L⁰ =L∩0^∗1^∗, where Lis the complement of L.

I This must be regular by closure properties.

(37)

Some more examples using pumping lemma-IV

(38)

Some more examples using pumping lemma-IV

I But L⁰ ={0ⁿ1ⁿ|n∈N}, which we know is not regular.

I Hence we have a contradiction and Lis not regular.

(39)

Need for infinite memory

Feels like all non-regular languages needed to remember infinite memory.

In{0ⁿ1ⁿ|n≥0}we need to remember the numberof seen 0s and count the 1s to match.

Finite number of statescannot count unboundedlyincreasing number.

(40)

Need for infinite memory

In {0ⁿ1ⁿ|n≥0}we need to remember the numberof seen 0s and count the 1s to match.

(41)

Need for infinite memory

In {0ⁿ1ⁿ|n≥0}we need to remember the numberof seen 0s and count the 1s to match.

(42)

Converse does not hold!

Pumping lemma holds for the following non-regular language.

L={caⁿbⁿ|n≥0}

| {z }

L1

∪ {c^kw|k 6= 1 andw ∈ {a,b}^∗}

| {z }

L2

Applying contrapositive of pumping lemma: I For L₁, the long enough word has to be caⁿ.

I But then, consider the partition of w =xyz wherex =,y =c I Then if you pump up , i.e., c^kaⁿbⁿ∈L₂ ⊆L

I And if you pump down, i.e., c⁰aⁿbⁿ=aⁿbⁿ∈L2 ⊆L I And of course, i.e.,c¹aⁿbⁿ∈L1 ⊆L.

In other words,

I This language satisfies pumping lemma! I But it is non-regular(Show this!)

(43)

Converse does not hold!

L={caⁿbⁿ|n≥0}

| {z }

L1

∪ {c^kw|k 6= 1 andw ∈ {a,b}^∗}

| {z }

L2

Applying contrapositive of pumping lemma:

I For L₁, the long enough word has to be caⁿ.

I But then, consider the partition of w =xyz wherex =,y =c I Then if you pump up , i.e., c^kaⁿbⁿ∈L₂ ⊆L

In other words,

(44)

Converse does not hold!

L={caⁿbⁿ|n≥0}

| {z }

L1

∪ {c^kw|k 6= 1 andw ∈ {a,b}^∗}

| {z }

L2

I But then, consider the partition of w =xyz wherex=,y =c

I Then if you pump up , i.e., c^kaⁿbⁿ∈L₂ ⊆L

In other words,

(45)

Converse does not hold!

L={caⁿbⁿ|n≥0}

| {z }

L1

∪ {c^kw|k 6= 1 andw ∈ {a,b}^∗}

| {z }

L2

I But then, consider the partition of w =xyz wherex=,y =c I Then if you pump up , i.e., c^kaⁿbⁿ∈L₂ ⊆L

In other words,

(46)

Converse does not hold!

L={caⁿbⁿ|n≥0}

| {z }

L1

∪ {c^kw|k 6= 1 andw ∈ {a,b}^∗}

| {z }

L2

I And if you pump down, i.e., c⁰aⁿbⁿ=aⁿbⁿ∈L2 ⊆L

I And of course, i.e.,c¹aⁿbⁿ∈L1 ⊆L. In other words,

(47)

Converse does not hold!

L={caⁿbⁿ|n≥0}

| {z }

L1

∪ {c^kw|k 6= 1 andw ∈ {a,b}^∗}

| {z }

L2

In other words,

(48)

Converse does not hold!

L={caⁿbⁿ|n≥0}

| {z }

L1

∪ {c^kw|k 6= 1 andw ∈ {a,b}^∗}

| {z }

L2

In other words,

(49)

More generalized pumping lemma

We have been looking for evidence of bad pumping in prefixes of words.

We can look for such evidence for any subword of length greater thann.

Theorem

Lis not regular if, I for eachn,

I there are words u,w, andv such thatuwv ∈Land|w| ≥n

I for each breakup of w into three words xyz =w such that y 6=and

|xy| ≤n then

I there is a k ≥0 such thatuxy^kzv 6∈L.

I In our earlier version of pumping lemma, u=. I Can we use this version for the previous example? I Is this an iff condition?

(50)

More generalized pumping lemma

We have been looking for evidence of bad pumping in prefixes of words. We can look for such evidence for any subword of length greater than n.

Theorem

Lis not regular if, I for eachn,

|xy| ≤n then

(51)

More generalized pumping lemma

Theorem

L is not regular if, I for eachn,

|xy| ≤n then

(52)

More generalized pumping lemma

Theorem

|xy| ≤n then

(53)

More generalized pumping lemma

Theorem

|xy| ≤n then

(54)

More generalized pumping lemma

Theorem

|xy| ≤n then

(55)

More generalized pumping lemma

Theorem

|xy| ≤n then

I In our earlier version of pumping lemma,u =.

I Can we use this version for the previous example? I Is this an iff condition?

(56)

More generalized pumping lemma

Theorem

|xy| ≤n then

I In our earlier version of pumping lemma,u =. I Can we use this version for the previous example?

I Is this an iff condition?

(57)

More generalized pumping lemma

Theorem

|xy| ≤n then

I In our earlier version of pumping lemma,u =. I Can we use this version for the previous example?

I Is this an iff condition?

(58)

Properties of regular languages

Let L be a regular language recognized by A= (Q,Σ, δ,q₀,F) I For all x,y ∈Σ^∗, we define

I x ≡_Ay iff ˆδ(q0,x) = ˆδ(q0,y)

I That is, the state reached after x andy are the same. What are the properties of ≡_A

I reflexive, symmetric and transitive. I It is an equivalence relation.

I What are other properties of this relation?

(59)

Properties of regular languages

I That is, the state reached after x andy are the same.

What are the properties of ≡_A I reflexive, symmetric and transitive. I It is an equivalence relation.

(60)

Properties of regular languages

What are the properties of ≡_A

I reflexive, symmetric and transitive. I It is an equivalence relation.

(61)

Properties of regular languages

What are the properties of ≡_A I reflexive, symmetric and transitive.

I It is an equivalence relation.

(62)

Properties of regular languages

(63)

Properties of regular languages

(64)

Properties of ≡

_A

I For all x,y ∈Σ^∗ anda∈Σ if x≡_A y thenx·a≡_A y·a (right congruence)

I if x≡_A y then x ∈L(A) iff y ∈L(A) refinement

I The number of equivalence classes of ≡_A is finite. Why? finite index Myhill Nerode relation

Equivalence relation on Σ^∗ satisfying the above three properties. Theorem

For any regular language, there is a Myhill-Nerode relation What about the converse?

(65)

Properties of ≡

_A

(66)

Properties of ≡

_A

(67)

Properties of ≡

_A

I The number of equivalence classes of ≡_A is finite. Why? finite index

Myhill Nerode relation

(68)

Properties of ≡

_A

Equivalence relation on Σ^∗ satisfying the above three properties.

Theorem

(69)

Properties of ≡

_A

Theorem

For any regular language, there is a Myhill-Nerode relation

What about the converse?

(70)

Properties of ≡

_A

Theorem