ZeePedia buy college essays online


Theory of Automata

<<< Previous Regular languages, Complement of a language Next >>>
 
img
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
img
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 non-final states and old non-final 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
img
Theory of Automata
(CS402)
Converting final states to non-final states and old non-final 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 De-Morgan'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