

Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 25
Reading
Material
Introduction
to Computer Theory
Chapter
9,10
Summary
Intersection of
two regular languages,
examples, non regular
language, example
Theorem
Statement
If L1 and L2
are
two regular languages, then
L1 Č L2 is also regular.
Proof
Using
DeMorgan's law for
sets
(L1c « L2c)c = (L1c)c Č (L2c)c = L1 Č L2
Since
L1 and L2 are regular languages, so
are L1c and L2c. L1c and L2c being regular provide
that L1c
« L2c is also
regular
language and so (L1c « L2c)c = L1 Č L2, being complement of regular
language is regular
language.
Following
is a remark
Remark
If L1 and L2
are
regular languages, then
these can be expressed by
the corresponding FAs. Finding
regular
expressions
defining the language L1 Č L2 is not so easy and building
corresponding FA is rather harder.
Following
are example of finding an FA
accepting the intersection of two
regular languages
Example
Consider
two regular languages L1 and L2,
defined over the alphabet Σ
= {a, b}, where
L1 = language of words with
double
a's.
L2 = language of words containing
even
number of a's.
FAs
accepting languages L1 and L2
may be as
follows
a,b
b
a
a
q
p
r+
FA1
b
b
b
a
FA2
1±
2
a
Their
corresponding REs may be
r1 = (a+b)*aa(a+b)*
r2 = (b+ab*a)*
Now
FAs accepting L1c and L2c , by
definition, may be
a,b
b
a
a
q+
p±
r
FA1c
b
b
a
b
FA2c
1
2+
a
Now FA
accepting L1c
« L2c , using the method described
earlier, may be as
follows
73
Theory of
Automata
(CS402)
New
States after reading
Old
States
a
b
z1±∫(p,1)
(q,2)∫z4
(p,1)∫z1
z2+∫(p,2)
(q,1)∫z3
(p,2)∫ z2
z3+∫(q,1)
(r,2)∫z6
(p,1)∫ z1
z4+∫(q,2)
(r,1)∫ z5
(p,2)∫ z2
z5∫(r,1)
(r,2)∫ z6
(r,1)∫ z5
z6+∫(r,2)
(r,1)∫ z5
(r,2)∫ z6
Here all
the possible combinations of states of
FA1c and FA2care considered
z1±
b
a
b
b
z2+
z3+
z4+
a
b
a
a
b
b
a
z5
z6+
a
An FA
that accepts the language
(L1c « L2c)c=L1Č L2may be
b
z1
b
b
a
z2
z3
z4
a
b
a
a
b
b
a
z6
z5+
a
Corresponding RE
can be determined as follows
The
regular expression defining
the language L1 Č L2 can be obtained, converting
and reducing the previous
FA
into a
GTG as after eliminating
states z2
and z6
b z1
a
b
bb*a
z4
z3
b+abb*ab
z1
a
a
ab*a
ab*a+b
z4
z5+
after
eliminating state z3
a+bb*aab*a
b+ab*a
z5+
74
Theory of
Automata
(CS402)
z4 can obviously be
b+abb*ab
b+ab*a
eliminated as
follows
a(a+bb*aab*a)
z5+
z1
eliminating
the loops at z1
and z5
(b+abb*ab)*a(a+bb*aab*a)(b+ab*a)*
z1
z5+
Thus the
required RE may be (b+abb*ab)*a(a+bb*aab*a)(b+ab*a)*
FA
corresponding to intersection of two
regular languages
(short
method)
Let
FA3 be an FA accepting
L1 Č L2, then the initial
state of FA3
must
correspond to the initial
state of FA1
and
the
initial state of FA2.
Since
the language corresponding to L1 Č L2 is the intersection of corresponding
languages L1
and L2, consists
of the
strings belonging to both L1and L2,
therefore a final state of FA3 must correspond to a final
state of FA1
and
FA2. Following is an
example regarding short
method of finding an FA corresponding to
the intersection of
two
regular languages.
Example
Let
r1 = (a+b)*aa(a+b)* and
FA1 be
a,b
b
a
a
q
p
r+
b
also
r2 = (b+ab*a)* and FA2 be
b
b
a
1±
2
a
An FA corresponding to
L1 Č
L2
can be determined as follows
New
States after reading
Old
States
a
b
z1∫(p,1)
(q,2)∫z4
(p,1)∫z1
z2∫(p,2)
(q,1)∫z3
(p,2)∫ z2
z3∫(q,1)
(r,2)∫z6
(p,1)∫ z1
z4∫(q,2)
(r,1)∫ z5
(p,2)∫ z2
z5+∫(r,1)
(r,2)∫ z6
(r,1)∫ z5
z6∫(r,2)
(r,1)∫ z5
(r,2)∫ z6
The
corresponding transition diagram may be as
follows
b
z1
a
b
b
z2
z3
z4
a
b
a
a
a
b
b
z6
z5+
a
75
Theory of
Automata
(CS402)
Nonregular
languages
The
language that cannot be
expressed by any regular
expression is called a Nonregular
language.
The
languages PALINDROME
and
PRIME
are
the examples of nonregular
languages.
Note: It is to be
noted that a nonregular
language, by Kleene's theorem,
can't be accepted by any FA or
TG.
Example
Consider
the language L = {Λ, ab,
aabb, aaabbb, ...} i.e.
{an bn :
n=0,1,2,3,...}
Suppose,
it is required to prove that
this language is nonregular. Let, contrary, L be a
regular language then
by
Kleene's
theorem it must be accepted by an
FA, say, F. Since every FA
has finite number of states
then the
language
L (being infinite) accepted by F
must have words of length more than
the number of states.
Which
shows
that, F must contain a circuit.
For
the sake of convenience suppose
that F has 10 states. Consider
the word a9 b9 from the language L
and let
the
path traced by this word be
shown as under
b
a
9
5
3
1
7
b
a
a
b
a
a
b
b
a
8
6
4
10
2
But,
looping the circuit
generated by the states
3,4,6,5,3 with aedges once
more, F also accepts the
word a9+4 b9,
while
a13b9 is
not a word in L. It may also
be observed that, because of the
circuit discussed above, F
also
accepts
the words a9(a4 )m b9, m =
1,2,3, ...
Moreover,
there is another circuit
generated by the states
9,10,9. Including the
possibility of looping this
circuit,
F accepts
the words a9(a4 )m b9(b2 )n where m,n=0,1,2,3,...(m
and n not being 0 simultaneously).Which
shows
that F
accepts words that are not
belonging to L.
76
Table of Contents:

