

Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 24
Reading
Material
Introduction
to Computer Theory
Chapter
9
Summary
Regular
languages, complement of a language,
theorem, proof, example,
intersection of two regular
languages
Regular
languages
As already
been discussed earlier that
any language that can be
expressed by a RE is said to be regular
language,
so if L1 and L2
are
regular languages then L1 + L2 , L1L2 and L1* are
also regular languages. This
fact can be
proved by
the following two
methods
By Regular
Expressions
As
discussed earlier that if r1, r2 are regular
expressions, corresponding to the
languages L1
and L2 then the
languages
L1 + L2 , L1L2 and L1* generated by r1+ r2, r1r2 and
r1*, are also
regular languages.
By
TGs
If L1 and L2
are
regular languages then L1 and L2
can
also be expressed by some
REs as well and hence
using
Kleene's
theorem, L1
and L2 can also be expressed by
some TGs. Following are the
methods showing that
there
exist TGs
corresponding to L1 + L2, L1L2 and L1*
If L1 and L2
are
expressed by TG1
and
TG2 then following
may be a TG accepting L1 + L2
L
L
p
1

TG1
TG2
n+
m+
If L1 and L2
are
expressed by the following TG1 and TG2
n+
m+
p
1
TG2
TG1
then
following may be a TG accepting
L1L2
L
n
m+
p
1
TG2
TG1
also a TG
accepting L1*
may be as under
L
n+
1
TG1
L
Example
aa,bb
aa,bb
Consider
the following TGs
ab,ba
2
TG1
1±
ab,ba
a,b
a,b
aaa,bbb
p
q+
TG2
70
Theory of
Automata
(CS402)
Following
may be a TG accepting L1+L2

L
L
a,b
a,b
aa,bb
aa,bb
ab,ba
aaa,bbb
p
2
q+
TG1
1±
TG2
ab,ba
also a TG
accepting L1L2 may be
L
a,b
a,b
aa,bb
aa,bb
ab,ba
aaa,bbb
p
q+
2
1
TG1
TG2
ab,ba
and a TG
accepting L2*
L
a,b
a,b
aaa,bbb
p
q+
TG2
L
Complement
of a language
Let L be
a language defined over an
alphabet Σ, then the
language of strings, defined
over Σ, not
belonging to
L, is called Complement
of the language L, denoted
by Lc or L'.
Note
To
describe the complement of a
language, it is very important to
describe the alphabet of
that language over
which
the language is defined.
For a
certain language L, the
complement of Lc
is the
given language L i.e.
(Lc)c = L
Theorem
If L is a
regular language then, Lc is also a regular
language.
Proof
Since L
is a regular language, so by Kleene's
theorem, there exists an FA,
say F, accepting the
language L.
Converting
each of the final states of
F to nonfinal states and
old nonfinal states of F to
final states, FA thus
obtained
will reject every string
belonging to L and will
accept every string, defined
over Σ, not belonging to
L.
Which
shows that the new FA
accepts the language Lc. Hence using Kleene's
theorem Lc
can be
expressed by
some
RE. Thus Lc
is
regular.
Example
Let L be
the language over the
alphabet Σ = {a, b},
consisting of only two words
aba and abb, then
the FA
accepting
L may be
a
a,b
b
n
o
p
q+
a
b
a,b
a,b
r
71
Theory of
Automata
(CS402)
Converting
final states to nonfinal
states and old nonfinal
states to final states, then
FA accepting Lc
may
be
a
a,b
b
n±
p+
o+
q
a
b
a,b
a,b
r+
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.
72
Table of Contents:

