

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 nonnull 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
nonnull 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 nonnull 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.
80
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.
a
b
a
C1+
C2
b
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
b
a
a
C1
C3+
C2
b
81
Table of Contents:

