Fig. 5.29
166 ~ Theory of Computer Science
- - ' - - - - - - - - - - - -
In Section 5.1. \ve have seen that the class of regular sets is closed under
union. concatenation and closure.
Theorem 5.6 If L is regular then [} is also regular.
Proof As L is regular by (vii), given at the end of Section 5.2.7. we can
construct a finite automaton M = (Q, L, 8, qo, F) such that T(M) = L.
We construct a transition system M' by starting with the state diagram of
M, and reversing the direction of the directed edges. The set of initial states
of AI' is defined as the set F, and qo is defined as the (only) final state of LH~
i.e. M' = (Q, L 8'. F. {qo}).
If 11' E T(lvi), we have a path from qo, to some final state in F with path
value w. By 'reversing the edges', \ve get a path in M' from some final state
in F to qo' Its path value is w
T . So wI" E T(Jvl'). In a similar way. we can
see that if 11'1 E T(M!), then 111 E T(Iv!). Thus from the state diagram it is
easy to see that T(M') = T(M/. We can prove rigorously that \V E T(M) iff
w
T E T(M') by induction on
. So T(l\,,fyT = T(M'). By (viii) of Section
5.2.7. T(M') is regular. i.e. T(M)T is regular. I
. EXAMPLE 5.23
ConSIder the FA AI given by Fig. 5.29. What is TCAi)? Show that T(Ml is
regular.
--01---------·e~1
U
/
o
/
I
/0
~
0,1eJ:i)
Finite automaton of Example 5.23.
Solution
As the elements of TUv1) are given by path values of paths from qo to itself
or from CJo to CJl (note that we have two final states qo and qt), we can
construct T(A!) by inspection.
As arrows do not come into qo, the paths from qo to itself are self-loops
repeated any number of times. The corresponding path values are ai, i 2: l.
As no arrow comes from q: to qo or (Ji, the paths from qo to qI are of the
fom1 qo ... ---+ qo· .. ql ... ---+ ql' The corresponding path values are O'li,
where i 2: 0 and j 2: 1. As the initial state qo is also a final state, A E T(lvI).
Thus.
Hence.
166 ~ Theory of Computer Science
- - ' - - - - - - - - - - - -
In Section 5.1. \ve have seen that the class of regular sets is closed under
union. concatenation and closure.
Theorem 5.6 If L is regular then [} is also regular.
Proof As L is regular by (vii), given at the end of Section 5.2.7. we can
construct a finite automaton M = (Q, L, 8, qo, F) such that T(M) = L.
We construct a transition system M' by starting with the state diagram of
M, and reversing the direction of the directed edges. The set of initial states
of AI' is defined as the set F, and qo is defined as the (only) final state of LH~
i.e. M' = (Q, L 8'. F. {qo}).
If 11' E T(lvi), we have a path from qo, to some final state in F with path
value w. By 'reversing the edges', \ve get a path in M' from some final state
in F to qo' Its path value is w
T . So wI" E T(Jvl'). In a similar way. we can
see that if 11'1 E T(M!), then 111 E T(Iv!). Thus from the state diagram it is
easy to see that T(M') = T(M/. We can prove rigorously that \V E T(M) iff
w
T E T(M') by induction on
. So T(l\,,fyT = T(M'). By (viii) of Section
5.2.7. T(M') is regular. i.e. T(M)T is regular. I
. EXAMPLE 5.23
ConSIder the FA AI given by Fig. 5.29. What is TCAi)? Show that T(Ml is
regular.
--01---------·e~1
U
/
o
/
I
/0
~
0,1eJ:i)
Finite automaton of Example 5.23.
Solution
As the elements of TUv1) are given by path values of paths from qo to itself
or from CJo to CJl (note that we have two final states qo and qt), we can
construct T(A!) by inspection.
As arrows do not come into qo, the paths from qo to itself are self-loops
repeated any number of times. The corresponding path values are ai, i 2: l.
As no arrow comes from q: to qo or (Ji, the paths from qo to qI are of the
fom1 qo ... ---+ qo· .. ql ... ---+ ql' The corresponding path values are O'li,
where i 2: 0 and j 2: 1. As the initial state qo is also a final state, A E T(lvI).
Thus.
Hence.