Chapter 9: Turing Machines and Linear Bounded Automata J;! 297
2. If the state q say in the current ID xqa), is not an accepting state of M 1
and O(q, a) has k triples, M 1 copies the ID xqay in the second tape and
makes k copies of this ID at the end of the sequence of IDs in tape 2.
3. M j modifies these k IDs in tape 2 according to the k choices given by
O(q, a).
4. M 1 returns to the marked current ID. erases the mark x and marks the
next ID-separator * with x (to the * which is to the left of the next ID
to be processed). Then M j goes back to step 1.
M j stops when an accepting state of M is reached in step 1.
Now M 1 accepts an input string IV only when it is able to find that M has
entered an accepting state, after a finite number of moves. This is clear from
the simulated sequence of moves of M j (ending in step 1)
We have to prove that M j will eventually reach an accepting ID (that is,
an ID having an accepting state of M) if M enters an accepting ID after n
moves. Note each move of M is simulated by several moves of M j •
Let m be the maximum number of choices that M has for various (q, a)'s.
(It is possible to find m since we have only finite number of pairs in Q x r.)
So for each initial ID of M. there are at most m IDs that M can reach after one
move. at most m
2 IDs that I'v! can reach after two moves. and so on. So
corresponding to n moves of M, there are at most 1 + m + m
2 + ... + mil moves
of M 1 • Hence the number of IDs to be explored by M 1 is at most nm".
We assume that M] explores these IDs. These IDs have a tree structure
having the initial ID as its root. We can apply breadth-first search of the nodes
of the tree (that is. the nodes at level 1 are searched. then the nodes at level 2,
and so on.) If At reaches an accepting ID after n moves. then M 1 has to search
atmost nm/! IDs before reaching an accepting ID. So. if M accepts lV, then M 1
also accepts lV (eventually). Hence T(M) = T(M j ).
9.8 THE MODEL OF LINEAR BOUNDED AUTOMATON
This model is important because (a) the set of context-sensitive languages is
accepted by the model. and (b) the infinite storage is restricted in size but not
in accessibility to the storage in comparison with the Turing machine model. It
is called the linear bounded automaton (LBA) because a linear function is used
to restrict (to bound) the length of the tape.
In this section we define the model of linear bounded automaton and
develop the relation between the linear bounded automata and context-sensitive
languages. It should be noted that the study of context-sensitive languages is
important from practical point of view because many compiler languages lie
between context-sensitive and context-free languages.
A linear bounded automaton is a nondetelministic Turing machine which
has a single tape whose length is not infinite but bounded by a linear function
2. If the state q say in the current ID xqa), is not an accepting state of M 1
and O(q, a) has k triples, M 1 copies the ID xqay in the second tape and
makes k copies of this ID at the end of the sequence of IDs in tape 2.
3. M j modifies these k IDs in tape 2 according to the k choices given by
O(q, a).
4. M 1 returns to the marked current ID. erases the mark x and marks the
next ID-separator * with x (to the * which is to the left of the next ID
to be processed). Then M j goes back to step 1.
M j stops when an accepting state of M is reached in step 1.
Now M 1 accepts an input string IV only when it is able to find that M has
entered an accepting state, after a finite number of moves. This is clear from
the simulated sequence of moves of M j (ending in step 1)
We have to prove that M j will eventually reach an accepting ID (that is,
an ID having an accepting state of M) if M enters an accepting ID after n
moves. Note each move of M is simulated by several moves of M j •
Let m be the maximum number of choices that M has for various (q, a)'s.
(It is possible to find m since we have only finite number of pairs in Q x r.)
So for each initial ID of M. there are at most m IDs that M can reach after one
move. at most m
2 IDs that I'v! can reach after two moves. and so on. So
corresponding to n moves of M, there are at most 1 + m + m
2 + ... + mil moves
of M 1 • Hence the number of IDs to be explored by M 1 is at most nm".
We assume that M] explores these IDs. These IDs have a tree structure
having the initial ID as its root. We can apply breadth-first search of the nodes
of the tree (that is. the nodes at level 1 are searched. then the nodes at level 2,
and so on.) If At reaches an accepting ID after n moves. then M 1 has to search
atmost nm/! IDs before reaching an accepting ID. So. if M accepts lV, then M 1
also accepts lV (eventually). Hence T(M) = T(M j ).
9.8 THE MODEL OF LINEAR BOUNDED AUTOMATON
This model is important because (a) the set of context-sensitive languages is
accepted by the model. and (b) the infinite storage is restricted in size but not
in accessibility to the storage in comparison with the Turing machine model. It
is called the linear bounded automaton (LBA) because a linear function is used
to restrict (to bound) the length of the tape.
In this section we define the model of linear bounded automaton and
develop the relation between the linear bounded automata and context-sensitive
languages. It should be noted that the study of context-sensitive languages is
important from practical point of view because many compiler languages lie
between context-sensitive and context-free languages.
A linear bounded automaton is a nondetelministic Turing machine which
has a single tape whose length is not infinite but bounded by a linear function