Mathematical Foundation of Computer Science

DHARM

REGULAR EXPRESSIONS 219

Case 2 (Concatenation 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 )
where automaton N∈ 1 and N∈ 2 were defined earlier, hence automaton N∈ will be i.e.,
N∈ = (Q 1 ∪ Q 2 , Σ 1 ∪ Σ 2 , δ∈, q 1 , {p 2 }) where,
Starting state will be the starting state of N∈ 1 i.e. {q 1 }.
Final state will be the final state of N∈ 2 i.e. {p 2 }.
Definitions of δ∈ will cover,
δ∈(p 1 , ∈) = {q 2 } and δ∈ = δ∈ 1. δ∈ 2
Hence, the automaton N∈ accepts the language which is accepted by automaton N∈ 1
followed by the language accepted by N∈ 2. It follows that, a path labeled by string x for automaton
N∈ will traverse from q 1 to p 2 which is equivalent to the path in N∈ 1 labeled by some string x′
from q 1 to p 1 followed by the path in N∈ 2 labeled by some other string x′′ from q 2 to p 2. Thus,
L(N∈) = {x′. x′′ / x′ ∈ L(N∈ 1 ) and x′ ∈ L(N∈ 2 )}
(To implement it, we assume that start state of automaton N∈ 1 will be the start state of
N∈ then it passes all the transitions of N∈ 1 labeled by L(r 1 ) and reaches to its final state p 1. The
operator. is implemented by connecting state p 1 to the start state of N∈ 2 which is q 2 through ∈-
transition, then pass all transitions of N∈ 2 labeled by L(r 2 ) and finally terminate on its final
state p 2. (Fig. 9.3)

q 1

L( )r 1

L( )r 2

Î

NÎ 1

NÎ 2

p 2

p 1

q 2

Fig. 9.3. (N∈).
Case 3 (kleeny Closure) Now construct the automaton N∈ for the language L(r) where,
L(r) = L(r 1 )
i.e., L(N∈) = L(N∈ 1 )
Let N∈ 1 be defined as,
N∈ 1 = (Q 1 , Σ 1 , δ∈ 1 , q 1 , {p 1 })
then automaton N∈ will be given as,
N∈ = (Q′, Σ 1 , δ∈, q, {p}) where,
l Q′ = Q 1 ∪ {q} ∪ {p}
l Where, q will be a new starting state and p will be a new final state,