Mathematical Foundation of Computer Science

DHARM

REGULAR AND NONREGULAR LANGUAGES 261

Example 10.5. Two DFAs M 1 and M 2 are shown in Fig 10.6. Construct the machine that

A B

(^0) 0, 1
1
M 1
P Q
1
0
0
M 2
R
1, 0
1
Fig. 10.6
accepts intersection of Language of M 1 and language of M 2.
Sol. Machine M 1 accepts the language expressed by the regular expression 0. 1. (0 + 1) and
machine M 2 accepts the language expressed by the regular expression 1. 0. (0 + 0. 1.
(1 + 0)). Now we construct the machine M that accepts intersection of language of M 1 as well
M 2.
Let M = (Q, Σ, δ, {A, P}, F 1 × F 2 ), where
l Q = (A, B) × (P, Q, R)
⇒ ({A, P}, {A, Q}, {A, R}, {B, P}, (B, Q), {B, R});
l Σ = { 0, 1}
l Starting state is the pair of starting state of M 1 as well M 2 , so {A, P}
l F = {B} × {Q, R}
⇒ ({B, Q}, {B, R})
l Transition functions δ are given in the table shown in Fig. 10.7.
δ({A, P}, 0) = [δ(A, 0), δ(P, 0)] = {A, Q} and similarly we compute other transition func-
tions.
State Input symbol
01
{A, P} {A, Q} {B, P}
{A, Q} {A, Q} {B, R}
{A, R} {A, R} {B, R}
{B, P} {B, Q} {B, P}
{B, Q} {B, Q} {B, R}
{B, R} {B, R} {B, R}
Fig. 10.7
Hence, the transition diagram of DFA M is shown in Fig. 10.8