148 ~ Theory of Computer Science
a
a
b
Fig. 5.12 Deterministic transition system for Example 5.7.
as go and q2 are the final states of the nondeterministic system [qo, q]l and
kin, ql" q2] are the final states of the deterministic system.
5.2.4 ALGEBRAIC METHOD USING ARDEN'S THEOREM
The following method is an extension of the Arden's theorem (Theorem 5.1).
This is used to find the Le. recognized by a transition system.
The following assumptions are made regarding the transition system:
(i) The transition graph does not have A-moves.
(ii) It has only one initial state, say VI'
(iii) Its vertices are 1'\ .•• V".
(i\) Vi the Le. represents the set of strings accepted by the system even
though v, is a final state.
(Y) (Xii denotes the I.e. representing the set of labels of edges from l'i to
1> When there is no such edge. aU == 0. Consequently, we can get the
following set of equations in Vi .. , V,,:
VI == Viall + V 2 a 21 + ... + Vila,,] + A
By repeatedly applying substitutions and Theorem 5.1 (Arden's theorem),
we can express Vi in terms of aii's.
For getting the set of strings recognized by the transition system, we have
to take the 'union" of all V;'s corresponding to final states.
EXAMPLE 5.R
Consider the transition system given in Fig. 5.13. Prove that the strings
recognized are (a + a(b + aa)*b)* arb + aa)* a.
a
a
b
Fig. 5.12 Deterministic transition system for Example 5.7.
as go and q2 are the final states of the nondeterministic system [qo, q]l and
kin, ql" q2] are the final states of the deterministic system.
5.2.4 ALGEBRAIC METHOD USING ARDEN'S THEOREM
The following method is an extension of the Arden's theorem (Theorem 5.1).
This is used to find the Le. recognized by a transition system.
The following assumptions are made regarding the transition system:
(i) The transition graph does not have A-moves.
(ii) It has only one initial state, say VI'
(iii) Its vertices are 1'\ .•• V".
(i\) Vi the Le. represents the set of strings accepted by the system even
though v, is a final state.
(Y) (Xii denotes the I.e. representing the set of labels of edges from l'i to
1> When there is no such edge. aU == 0. Consequently, we can get the
following set of equations in Vi .. , V,,:
VI == Viall + V 2 a 21 + ... + Vila,,] + A
By repeatedly applying substitutions and Theorem 5.1 (Arden's theorem),
we can express Vi in terms of aii's.
For getting the set of strings recognized by the transition system, we have
to take the 'union" of all V;'s corresponding to final states.
EXAMPLE 5.R
Consider the transition system given in Fig. 5.13. Prove that the strings
recognized are (a + a(b + aa)*b)* arb + aa)* a.