Mathematical Foundation of Computer Science

DHARM

260 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

L(M′) = L (∈∈∈∈∈ + 0. 1) = {∈∈∈∈∈, 0, 01, 011, .....}
and, L(M) = L [(1 + 0.1. 0) (0 + 1)*] = {(1, 00, 010, 0110,.....), (1, 00, 010, 0110,.....) 0,
(1, 00, 010, 0110,.....)1, (1, 00, 010, 0110,.....) 00,....}
we see L( M′) excluded all the strings of the set of L(M) formed over {0,1}.

So, L(M′) = Σ* – L( M) = L

Regular expressions are closed under ∩ operation

This property says that if intersection operation is performed over regular expressions we

again get the regular expression, in other words, intersection of two regular languages is a

regular language.

Assume r 1 and r 2 are regular expressions and there languages are L 1 and L 2. Then

there intersection will be, L 1 ∩ L 2.

Applying the De Morgan Law that complement of complement is effectless. So,

L 1 ∩ L 2 = [(L 12 ∩L )]

= [L 12 ∪L] [using De Morgan Law]
⇒ a Regular language
Because, complement of a regular language is regular; union of regular languages is
regular and subsequently complement of a regular language is regular. So, L 1 ∩ L 2 returns
regular.
Hence, Regular expressions (languages) are closed under intersection.

Theorem 10.1. If M 1 , M 2 are two DFAs that accept the language L 1 and L 2 then there exist a
DFA M that accept L 1 ∩ L 2.
Proof. Let DFA M 1 and M 2 are defined as,
M 1 = (Q 1 , Σ, δ 1 , q 1 , F 1 ) and L 1 = L(M 1 ); and
M 2 = (Q 2 , Σ, δ 2 , q 2 , F 2 ) and L 2 = L(M 2 )
Assume DFA M = (Q, Σ, δ, q 0 , F) accepts the language L(M) = L 1 ∪ L 2 , where M has
following characteristics:
l Q = Q 1 × Q 2 ; Set Q contains all possible set of states formed over Q 1 with Q 2.
l Same set of input symbols Σ
l Transition function δ†
l Starting state is a state that contains pair of starting states i.e., q 0 = (q 1 , q 2 ).
l F = F 1 × F 2 ; Set of Final state F contains all pairs of final states formed over F 1 with
F 2.

† Transition function δ is the mapping of a pair of states (∈ Q) with input symbol (∈ Σ) and
return a pair of states.
Let pair of states is (p, q) and Σ = {a} then transition function δ will be:
δ((p, q), a) = (δ 1 (p, a), δ 2 (q, a))

= ( r , s ) [where r and s are there respective next states of M 1 and M 2 .]

If a is the language of DFA M, certainly state r ∈ F 1 as well as state s ∈ F 2.

So, finally we get the machine M = (Q 1 × Q 2 , Σ, δ, (q 1 , q 2 ), F 1 × F 2 ).