Chapter 5: Regular Sets and Regular Grammars ~ 169
a
a, b
r----b-l&
Fig. 5.32 DFA of Example 5.24, without A-moves.
Let G = ({AO, Ad. {a. b}. P. A o ). where P is given by
Al ---+ a.
," \
~ll!
G is the required regular grammar.
5.6.2 CONSTRUCTION OF A TRANSITION SYSTEM M
ACCEPTING L(G) FOR A GIVEN REGULAR
GRAMMAR G
Let G = ({A o . AI' .... A,,}. L. P, A o ). We construct a transition system ,11,1
whose (i) states conespond to variables. (ii) initial state conesponds to A o .
and (iii) transitions in :H conespond to productions in P. As the last
production applied in any derivation is of the form Ai ---+ a, the conesponding
transition terminates at a ne,\' state. and this is the unique final state.
We define M as ({ qo- .... q/p qr}, L. O. qo, {qrD where <5 is defined as
follows:
(i) Each production Ai ---+aA i induces a transition from qi to CJi with
label a,
Each production A k ---+ a induces a transition from qk to {fr with
label a.
From the construction it is easy to see that A o =? alA] =? aja.:?A 2 =? ...
=? aj ... a,,_jA n _] =? aj ... an is a derivation of ala.:? ... all iff there is a
path in M starting from qo and temlinating in CJr with path value aja.:? ... all"
Therefore. L(Gl = TUv1).
EXAMPLE 5.25
Let G =({A o . Ad, {a. b}. P, A o ). where P consists of A o ---+ aA j • Al ---+ bA I ,
A I ---+ a, A! ---+ bAa. Construct a transition system M accepting L(G).
Solution
Let Iv! = ({ CJCi. {fl' {ft}· {a. b}. 8. {fCi, {{ft})· where qo and qj correspond to A o
and AI. respectively and Cit is the ne,v (final) state introduced. A o ---+ aA j
induces a transition from {fo to q] with label a. Similarly. A] ---+ bA l and
AI ---+ bAI) induce transitions from CJj to {fj with label b and from ql to qo with
a
a, b
r----b-l&
Fig. 5.32 DFA of Example 5.24, without A-moves.
Let G = ({AO, Ad. {a. b}. P. A o ). where P is given by
Al ---+ a.
," \
~ll!
G is the required regular grammar.
5.6.2 CONSTRUCTION OF A TRANSITION SYSTEM M
ACCEPTING L(G) FOR A GIVEN REGULAR
GRAMMAR G
Let G = ({A o . AI' .... A,,}. L. P, A o ). We construct a transition system ,11,1
whose (i) states conespond to variables. (ii) initial state conesponds to A o .
and (iii) transitions in :H conespond to productions in P. As the last
production applied in any derivation is of the form Ai ---+ a, the conesponding
transition terminates at a ne,\' state. and this is the unique final state.
We define M as ({ qo- .... q/p qr}, L. O. qo, {qrD where <5 is defined as
follows:
(i) Each production Ai ---+aA i induces a transition from qi to CJi with
label a,
Each production A k ---+ a induces a transition from qk to {fr with
label a.
From the construction it is easy to see that A o =? alA] =? aja.:?A 2 =? ...
=? aj ... a,,_jA n _] =? aj ... an is a derivation of ala.:? ... all iff there is a
path in M starting from qo and temlinating in CJr with path value aja.:? ... all"
Therefore. L(Gl = TUv1).
EXAMPLE 5.25
Let G =({A o . Ad, {a. b}. P, A o ). where P consists of A o ---+ aA j • Al ---+ bA I ,
A I ---+ a, A! ---+ bAa. Construct a transition system M accepting L(G).
Solution
Let Iv! = ({ CJCi. {fl' {ft}· {a. b}. 8. {fCi, {{ft})· where qo and qj correspond to A o
and AI. respectively and Cit is the ne,v (final) state introduced. A o ---+ aA j
induces a transition from {fo to q] with label a. Similarly. A] ---+ bA l and
AI ---+ bAI) induce transitions from CJj to {fj with label b and from ql to qo with