The language
L = {a n b n c n : n ≥ 1}
is accepted by some linear bounded automaton. This follows from the discussion
in Example 9.8. The computation outlined there does not require space outside
the original input, so it can be carried out by a linear bounded automaton.
Example 10.5
Find a linear bounded automaton that accepts the language
L = {a n! : n ≥ 0}.
One way to solve the problem is to divide the number of a’s successively by 2, 3,
4,…, until we can either accept or reject the string. If the input is in L, eventually
there will be a single a left; if not, at some point a nonzero remainder will arise.
We sketch the solution to point out one tacit implication of Definition 10.5.
Since the tape of a linear bounded automaton may be multitrack, the extra tracks
can be used as work space. For this problem, we can use a two-track tape. The
first track contains the number of a’s left during the process of division, and the
second track contains the current divisor (Figure 10.18). The actual solution is
fairly simple. Using the divisor on the second track, we divide the number of a's
on the first track, say by removing all symbols except those at multiples of the
divisor. After this, we increment the divisor by one, and continue until we either
find a nonzero remainder or are left with a single a.
Figure 10.18
The last two examples suggest that linear bounded automata are more
powerful than pushdown automata, since neither of the languages is context-free.
To prove such a conjecture, we still have to show that any context-free language
can be accepted by a linear bounded automaton. We will do this later in a
somewhat roundabout way; a more direct approach is suggested in Exercises 6
and 7 at the end of this section. It is not so easy to make a conjecture on the
L = {a n b n c n : n ≥ 1}
is accepted by some linear bounded automaton. This follows from the discussion
in Example 9.8. The computation outlined there does not require space outside
the original input, so it can be carried out by a linear bounded automaton.
Example 10.5
Find a linear bounded automaton that accepts the language
L = {a n! : n ≥ 0}.
One way to solve the problem is to divide the number of a’s successively by 2, 3,
4,…, until we can either accept or reject the string. If the input is in L, eventually
there will be a single a left; if not, at some point a nonzero remainder will arise.
We sketch the solution to point out one tacit implication of Definition 10.5.
Since the tape of a linear bounded automaton may be multitrack, the extra tracks
can be used as work space. For this problem, we can use a two-track tape. The
first track contains the number of a’s left during the process of division, and the
second track contains the current divisor (Figure 10.18). The actual solution is
fairly simple. Using the divisor on the second track, we divide the number of a's
on the first track, say by removing all symbols except those at multiples of the
divisor. After this, we increment the divisor by one, and continue until we either
find a nonzero remainder or are left with a single a.
Figure 10.18
The last two examples suggest that linear bounded automata are more
powerful than pushdown automata, since neither of the languages is context-free.
To prove such a conjecture, we still have to show that any context-free language
can be accepted by a linear bounded automaton. We will do this later in a
somewhat roundabout way; a more direct approach is suggested in Exercises 6
and 7 at the end of this section. It is not so easy to make a conjecture on the