1 74 I;! Theory ofComputer Science
a
b
b
a
b
a
b
a
Fig. 5.35 DFA for Example 5.35.
By applying the construction given in Section 5.6.1. we can construct a
regular grammar G accepting L = T(M).
G = ({A o , A l , A 2 , A 3 }. {a, b}, P. A o ) where P consists of A o ~ aAo,
A o ~ hAl, A l ~ hAl> A l ~ bA 2 , A 2 ~ aA 2 , A 2 ~ bA 3 , A 2 ~ b, A 3 ~ aA 3 ,
A 3 ~ GAo·
EXAMPLE 5.36
Let G = ({A o , A l , A 2 • A 3 I. {a, b}, P. A o ), where P consists of A o ~
aAo IhAl- Al ~ aA 2 1 aA 3 , A 3 ~ a IhAl IhA 3 , A 3 ~ b IbAo· Construct an
NDFA accepting L(G).
Solution
The NDFA accepting L =L(G) is M where M =({qo, ql' q2, q3, q4}, {a, b},
8. qo, {q4})' 8 is described by the state diagram shown in Fig. 5.36.
b
a
Fig. 5.36 NDFA for Example 5.36.