Mathematical Foundation of Computer Science

DHARM

218 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

q p

All transitions

between states

that accepts the

language L( )r 1

NÎ 1

Or, q p

L( )r 1

A similar structure for automata N∈ 2 for the language L(r 2 ) can also be drawn.
Case 1 (Union operation) Construct the automaton N∈ for the language L(r), where
L(r) = L(r 1 + r 2 ) = L(r 1 ) ∪ L(r 2 )
i.e., L(N∈) = L(N∈ 1 ) ∪ L(N∈ 2 )
Let N∈ 1 and N∈ 2 are define as,
N∈ 1 = (Q 1 , Σ 1 , δ∈ 1 , q 1 , {p 1 }) and N∈ 2 = (Q 2 , Σ 2 , δ∈ 2 , q 2 , {p 2 }) then automata N∈
will be
N∈ = (Q 1 ∪ Q 2 ∪ q ∪ p, Σ 1 ∪ Σ 2 , δ∈, q, {p}) where,
l State q will be a new starting state, i.e., δ∈(q, ∈) = {q 1 , q 2 }.
l States will be a new final state, i.e., δ∈(p 1 , ∈) = δ∈(p 2 , ∈) = {p}.
l Definitions of transition function δ∈ will cover,
δ∈ = δ∈ 1 ∪ δ∈ 2 and δ∈(q, ∈) = {q 1 , q 2 } and δ∈(p 1 , ∈) = δ∈(p 2 , ∈) = {p}.
So, automaton N∈ accepts the language which is accepted by automaton N∈ 1 or the
language which is accepted by automaton N∈ 2. It follows that for automaton N∈ if there is a
path, labeled by some string x from state q to p if and only if, either there is a path labeled by
string x in N∈ 1 from q 1 to p 1 or there is a path labeled by string x in N∈ 2 from q 2 to p 2.
Therefore, L(N∈) = L(N∈ 1 ) ∪ L(N∈ 2 ).
(To implement this definition we precede from a new start state q. The initial states of
both automatons (q 1 and q 2 ) are connected through ∈ transitions from the new state q. Simi-
larly, old final states (p 1 and p 2 ) will converge to a new final state p through ∈-transitions
provided that the acceptance power of N∈ 1 and N∈ 2 remains unchanged. So, we get the au-
tomaton N∈ which is shown in Fig. 9.2.

q p

L( )r 1

L( )r 2

Î

Î Î

Î

new start state new final state

old start state old final state

NÎ 1

NÎ 2

q 1 p 1

q 2 p 2

Fig. 9.2. (N∈).