ZeePedia buy college essays online


Theory of Automata

<<< Previous Nonregular languages Next >>>
 
img
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 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.
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
img
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
img
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
img
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 a-edges 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