168 J;! Theory ofComputer Science
5.6.1 CONSTRUCTION OF A REGULAR GRAMMAR
GENERATING T(M) FOR A GIVEN DFA M
Let lv! = ({ q(j, .... qll}, L. 8. qo, F). If w is in T(M), then it is obtained by
concatenating the labels conesponding to several transitions, the first from qo
and the last tem1inating at some final state. So for the grammar G to be
constructed. productions should conespond to transitions. Also, there should
be provision for tenninating the derivation once a transition tenninating at
some final state is encountered. With these ideas in mind, we construct G as
G = ({A o , Aj, .... All}, .L p. ,10)
where P is defined by the following rules:
(i) Ai -'> aA j is included in P if 8(qi' a) = qj eo F.
(ii) Ai -'> aA) and Ai -'> a are included in P if 8(qi' a) = qj E F.
We can show that L(G) = T(M) by using the construction of P. Such a
construction gives
Ai:=} aA j
iff 8(qi, a) = qi
Ai:=} a
iff 8(qi' a) E F
So.
,10 :=} alA 1 :=} ala:A: :=} . . . :=} a1 ... ak-lAk :=} ala2 ... ak
iff
8(qo. aj) = qjo
8(qj. a2) = q:• ...,
8(qk' ak) E F
This proves that H' = aj ... ak E L(G) iff 8(qo, aj ... ak) E F, l.e. iff
W E T(M).
EXAMPLE 5.24
Construct a regular grammar G generating the regular set represented by
P = a*b(a + b)*.
Solution
We construct the DFA conesponding to P using the construction given III
Section 5.2.5. The construction is shown in Fig. 5.31.
- - - + I 'OI--_a*_ _'O}-__b .~
A
a, b
Fig. 5.31
a
--o----:--Of----.-,\-I b
j\
DFA of Example 5.24, with A-moves.
After eliminating the A-moves. we get the DFA straightaway, as shown in
Fig. 5.32.