Pumping Lemma version II

<< Pumping Lemma

Pseudo theorem >>

Theory of Automata

(CS402)

Theory of Automata

Lecture N0. 27

Reading Material

Introduction to Computer Theory

Chapter 10

Summary

Pumping lemma version II, proof, examples, Myhill Nerode theorem, examples

Pumping Lemma version II

Statement

Let L be an infinite language accepted by a finite automaton with N states, then for all words w in L that have

langth more than N, there are strings x,y and z (y being non-null string) and length(x) + length(y)  N s.t.

w = xyz and all strings of the form xynz are in L for n = 1,2,3, ...

Proof

The lemma can be proved, considering the following examples

Example

Consider the language PALINDROME which is obviously infinite language. It has already been shown that the

PALINDROME satisfies pumping lemma version I (previous version). To check whether the new version of

pumping lemma still holds in case of the PALINDROME, let the PALINDROME be a regular language and be

accepted by an FA of 78 states. Consider the word w = a85ba85.

Decompose w as xyz, where x,y and z are all strings belonging to Â* while y is non-null string, s.t.

length(x) + length(y)  78, which shows that the substring xy is consisting of a's and xyyz will become

amore than 85ba85 which is not in PALINDROME. Hence pumping lemma version II is not satisfied for the

language PALINDROME. Thus pumping lemma version II can't be satisfied by any non regular language.

Following is another example in this regard

Example

Consider the language PRIME, of strings defined over Σ = {a}, as {ap : p is prime}, i.e.

PRIME = {aa, aaa, aaaaa, aaaaaaa, ...}

To prove this language to be nonregular, suppose contrary, i.e. PRIME is a regular language, then there exists

an FA accepts the language PRIME. Let the number of states of this machine be 345 and choose a word w from

PRIME with length more than 345, say, 347 i.e. the word w = a347

Since this language is supposed to be regular, therefore according to pumping lemma xynz, for n = 1,2,3,... are

all in PRIME.

Consider n=348, then xynz = xy348z = xy347yz. Since x,y and z consist of a's, so the order of x, y, z does not

matter i.e. xy347yz = xyzy347 = a347 y347, y being non-null string and consisting of a's it can be written y = am,

m=1,2,3,...,345.

Thus xy348z = a347 (am)347 = a347(m+1)

Now the number 347(m+1) will not remain PRIME for m = 1,2,3, ..., 345. Which shows that the string xy348z is

not in PRIME. Hence pumping lemma version II is not satisfied by the language PRIME. Thus PRIME is not

regular.

Strings belonging to same class

Consider a regular language L, defined over an alphabet Â. If, two strings x and y, defined over Â, are run over

an FA accepting the language L, then x and y are said to belong to the same class if they end in the same state,

no matter that state is final or not.

Note: It is to be noted that this concept of strings x and y can be compared with indistinguishable strings w.r.t. L

(discussed earlier). Equivalently, the strings x and y are said to belong to same class if for all strings z, either xz

and yz belong to L or xz and yz don't belong to L.

Myhill Nerode theorem

Statement

For a language L, defined over an alphabetÂ,

L partitions Â* into distinct classes.

If L is regular then, L generates finite number of classes.

Theory of Automata

(CS402)

If L generates finite number of classes then L is regular.

The proof is obvious from the following examples

Example

Consider the language L of strings, defined over Â = {a,b}, ending in a.

It can be observed that L partitions Â* into the following two classes

C1 = set of all strings ending in a.

C2 = set of all strings not ending in a.

Since there are finite many classes generated by L, so L is regular and hence following is an FA, built with the

help of C1 and C2, accepting L.

C1+

C2-

Example

Consider the language L of strings, defined over Â = {a,b}, containing double a. It can be observed that L

partitions Â* into the following three classes

C1 = set of all strings without aa but ending in a.

C2 = set of L and all strings without aa but ending in b.

C3 = set of all strings containing aa.

Since there are finite many classes generated by L, so L is regular and hence following is an FA, built with the

help of C1, C2 and C3, accepting L.

a,b

C3+

C2-

Table of Contents: