302 g Theory of Computer Science
EXAMPLE 9.12
Find the grammar generating the set accepted by a linear bounded automaton
M whose transition table is given in Table 9.10.
TABLE 9.10 Transition Table for Example 9.12
Present state
Tape input symbol
~
$
0
---7q1
~Rq1
1Lq2
ORq2
q2
~Rq4
1Rq3
1Lq1
q3
$Lq1
1Rq3
1Rq3.
®
Halt
OLq4
ORq4
Solution
Step 1 (A) (i) Productiolls corresponding to right moves. The seven right
moves in Table 9.10 give the following productions:
(9.5)
q30 ~ lq3
q3 1 ~ lq3
q.+l ~ Oq.+
qlc): ~ c):qj.
qjl ~ OC):.
q:c): ~ C):C).+,
q:O ~ lq3
(ii) Productions corresponding to left moves. There are four left moves in
Table 9.10. Each left move yields four productions (corresponding to the four
tape symbols). These are:
(a) lLq: corresponding to ql-row and O-column gives
c):qjO ~ q:¢l, SqjO ~ C)2$}, OqlO ~ q201, lq j O ~ q211
(9.6)
(b) lLql corresponding to qj-rmv and I-column yields
¢q:l ~ ql¢l, Sq:l ~ qjSL Oq:l ~ ql0!, lq:l ~ qlll
(9.7)
(c) SLqj corresponding to qrro\V and $-column gives
c):q3$ ~ qj¢$, Sq3$ ~ CJlS$, 0CJ3$ ~ CJjO$, lCJ3$ ~ CJ l l$
(9.8)
(d) OLq.+ corresponding to CJ.+-row and O-column yields
¢CJ.+O ~ CJ.+¢O, $q.+O ~ q.+$O, Oq.+O ~ q.+OO, lq.+O ~ q410
(9.9)
(B) There are no productions corresponding to change in length.
(C) The productions for introducing the endmarkers are
¢~ [C)l¢¢
$ ~ [CJ1¢$,
°~ [(1J¢0,
1 ~ [ql¢L
[q.+] ~ S
¢ -+ ¢$]
$ ~ $$]
°~ OS]
1 ~ 1$]
(9.10)
(9.11)