Solutions (or Hints) to Chapter-end Exercises J;\ 395
bA 4 , A 4 ~ bA 3 (corresponding to the first six transitions) and A 2 ~
bAj, A 2 ~ b, A 4 ~ aAJ, A 4 ~ a (corresponding to the last two
transitions). So G = ({Aj, A 2 , A 3 , A 4 }, {a, b}, P, A j ), where P
consists of the induced productions given above.
5.22 The required productions are:
S ~ ASjlBSjl .,. IZSJ,
SI ~ ASI!BSjl '" IZSj,
SI ~ OSlllSI! ... 19S 1
Sj ~ AIBI ... IZ and Sj ~ 0[11 '" 19
5.24 The given grammar is equivalent to G = ({S, A, B}, {a, b}, P, S),
where P consists of S ~ as IbS IaA, A ~ bB, B ~ a(B ~ aC and
C ~ A is replaced by B ~ a). Let qo, qj and q2 correspond to S, A
and B. qf is the only final state. The transition system M accepting
I(G) is given as
M = ({qo, qj, q2' qf}, {a, b}, 8, qo, {qr})
where qo, qj, and q2 correspond to S, A and Band qf is the (only)
final state. S ~ as, S ~ bS, S ~ aA and A ~ bB induce transitions
from qo to qo with, labels b and a, from qo ~ qj with label a and
from qj to q2 with label b. B ~ a induces a transition from q2 to qf
with label a. M is defined by Fig. AS.5.
a, b
Fig AS.S Transition system for Exercise 5.24.
The equivalent DFA is given in Table AS.S.
TABLE AS.S State Table of DFA for Exercise 5.24
State/I.
a
b
[qQ]
[qQ, q1]
[qQl
[qQ, q1]
[qQ, q1]
[qQ, q2]
[qQ, q2]
[qQ. q1. qf]
[qQ]
[qQ, q1, qf]
[qQ. q1]
[qQ. q2]