300 ~ Theory of Computer Science
We now describe the construction which involves two steps:
Step 1 (i) No change in length of IDs: (a) Right move. akRqt corresponding
to qt-row and arcolumn leads to the production
qta) -+ ak-Cft
(b) Left move. akLqt cOlTesponding to qt-row and arcolumn yields several
productions
for all am E r
(ii) Change in length of IDs: (a) Left-end. akLqt cOlTesponding to q/-row
and arcolumn gives
[q;a; -+ [cltbak
When b occurs next to the left-bracket, it can be deleted. This is achieved
by including the production [b -+ [.
(b) Right-end. When b occurs to the left of ], it can be deleted. This is
achieved by the production
a;b] -+ a;J
for all aj E r
When the RJW head moves to the right of ], the length mcreases.
Corresponding to this \ve have a production
q;] -+ qtb]
for all qt E Q
(iii) lmrodllction ofendmarkers. For introducing endmarkers for the input
string, the following productions are included:
at -+ [qj ¢ a;
for at E r. at 1= b
for all at E r, at 1= b
For removing the brackets from [q2b], we include the production
[q2b] -+ S
Recall that qj and q2 are the initial and final states, respectively.
Step 2 To get the required grammar, reverse the arrows of the productions
obtained in step 1. The productions we get can be called inverse productions.
The new grammar is called the generative grammar. We illustrate the
construction \'lith an example.
EXAMPLE 9.11
Consider the TM described by the transition table given in Table 9.9. Obtain
the inverse production rules.
Solution
In this example. qj is both initial and final.
Step 1 (i) Prodllctions corresponding to right moves
(9.1)