Chapter 9: Turing Machines and Linear Bounded Automata ~ 301
(ii) (a) Productions corresponding to left-end
[b ~ [
(b) Productions corresponding to rig',ot-end
(9.2)
bb] ~ b],
(iii) 1 ~ [qj ¢1,
lb] ~ 1],
1 ~ IS],
ql] ~ qlb],
[qlb] ~ S
(9.3)
(9.4)
TABLE 9.9 Transition Table for Example 9.11
Present state
b
Step 2 The inverse productions are obtained by reversing the arrows of the
productions (9.1)-(9.4).
¢ql ~ ql¢
bq~ ~ q l l,
bql ~ q~l
[ ~ [b, b] ~ bb],
1] ~ lb]
qlb ~ ql],
q~b ~ q~].
[cII¢l ~ 1
1$] ~ 1,
S ~ [q1b]
Thus we have shown that there exists a type 0 grammar corresponding to
a Turing machine. The converse is also true (we are not proving this), i.e. given
a type 0 grammar G. there exists a Tming machine accepting L(G). Actually,
the class of recursively enumerable sets, the type 0 languages, and the class of
sets accepted by TM are one and the same. We have shown that there exists
a recursively enumerable set which is not a context-sensitive language (see
Theorem 4.4). As a recursive set is recursively enumerable, Theorem 4.4 gives
a type 0 language which is not type 1. Hence, 4s1 c.~ (d Property 4,
Section 4.3) is established.
9.10 LINEAR BOUNDED AUTOMATA AND LANGUAGES
A linear bounded automaton M accepts a string w if. after starting at the initial
state with RIW head reading the left-endmarker, M halts over the right-endmarker in a final state. Otherwise, w is rejected.
The production rules for the generative grammar are constructed as in the
case of Turing machines. The following additional productions are needed in
the case of LBA.
Qiqr$ ~ qf$
¢lrS ~ ¢qr,
for all Qi E r
¢qf ~ qt