DHARM262 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE{A, P}
0
{A, Q} {A, R}0{B, P} {B, Q} {B, R}00, 10 1(^11)
1 0
1
Fig. 10.8
Regular languages are closed under Subtraction
Subtraction (Difference) of two regular languages is a regular language ‡.
Let r 1 and r 2 are regular expressions and there languages are L 1 and L 2 then there
difference is r 1 – r 2 , which denotes the language L(r 1 – r 2 ),
⇒ L(r 1 ) – L(r 2 )orL 1 – L 2 = L
It contains set of strings that are in L 1 but not in L 2. If it is L then L is called difference
set of L 1 with L 2.
So, language is closed under difference.
For example assume regular expressions r 1 = (0 + 1) and r 2 = 1 then difference of
regular expressions is r 1 – r 2 = (0 + 1) – 1, that can be simplify after knowing the language
expressed by both regular expressions.
Since, language expressed by r 1 is L(r 1 ) = {all strings formed over 0’and 1’s} and
Language expressed by r 2 is L(r 2 ) = {∈, all strings formed over 1’s}
If difference of languages L(r 1 ) and L(r 2 ) is L then L contains all the those strings that
doesn’t have all 1’s. So L contains all those strings that have at least a, 0.
Hence, regular expression of such language is 0. (1 + 0). 0 (which also generate ∈,
but in L ∈ will not be there). So, to exclude symbol ∈ from the language of regular expression,
the new regular expression is constructed without affecting the nature of language it gener-
ates i.e.,
[0. 0. (1 + 0). 0 + 0. (1 + 0). 0. 0].
Hence language L is
L([0. 0. (1 + 0). 0 + 0. (1 + 0). 0*. 0]) = {0, 00, 01, 10, 100,....}
That contains all strings formed over 0’s and 1’s that have at least a, 0.
Reversal of regular language is regular
Let w is any string abcd......xyz then reverse of w is a string zyx......dcba. If w is regular then
reverse of w is also regular. Now we discuss a lemma so the things are more clearer.
‡ We can’t say directly that difference of regular expression is regular expression, because sub-
traction operation is not a part of the definition of regular expression. After few steps of simplification
we may get the difference of regular expression.