Understanding Computation (23 page)

This execution trace shows us how the machine ping-pongs between
symbol and token rules: the symbol rules repeatedly expand the symbol on
the top of the stack until it gets replaced by a token, then the token
rules consume the stack (and the input) until they hit a symbol. This
back and forth eventually results in an empty stack as long as the input
string can be generated by the grammar rules.
^[
36
]

How does the PDA know which rule to choose at each step of
execution? Well, that’s the power of nondeterminism: our NPDA simulation
tries all possible rules, so as long as there’s
some
way of getting to an empty stack,
we’ll find it.

This parsing
procedure relies on nondeterminism, but in real applications, it’s best to avoid
nondeterminism, because a deterministic PDA is much faster and easier to simulate than a
nondeterministic one. Fortunately, it’s almost always possible to eliminate nondeterminism
by using the input tokens themselves to make decisions about which symbol rule to apply at
each stage—a
technique called
lookahead
—but that makes the translation
from CFG to PDA more complicated.

It’s also not really good enough to only be able to
recognize
valid
programs. As we saw in
Implementing Parsers
, the whole point of parsing a
program is to turn it into a structured representation that we can then do something useful
with. In practice, we can create this representation by instrumenting our PDA simulation to
record the sequence of rules it follows to reach an accept state, which provides enough
information to construct a parse tree. For example, the above execution trace shows us how
the symbols on the stack get expanded to form the desired sequence of tokens, and that tells
us the shape of the parse tree for the
string
'w(v:

^[
29
]
This isn’t quite the same as accepting strings that merely contain equal numbers of
opening and closing brackets. The strings
'()'
and
')('
each contain a single opening and closing bracket,
but only
'()'
is balanced.

^[
30
]
This doesn’t mean that an input string can ever actually be infinite, just that we can
make it as finitely large as we like.

^[
31
]
Briefly, this algorithm works by converting an NFA into a
generalized
nondeterministic finite automaton
(GNFA), a finite state machine where each
rule is labeled with a regular expression instead of a single character, and then
repeatedly merging the states and rules of the GNFA until there are only two states and
one rule left. The regular expression that labels that final rule always matches the same
strings as the original NFA.

^[
32
]
Of course, any real-world implementation of a stack is always going to be limited by
the size of a computer’s RAM, or the free space on its hard drive, or the number of
atoms in the universe, but for the purposes of our thought experiment, we’ll assume that
none of those constraints exist.

^[
33
]
These class names begin with
PDA
, rather than
DPDA
, because their implementations don’t
make any assumptions about determinism, so they’d work just as well
for simulating a nondeterministic PDA.

^[
34
]
The “even number of letters” restriction keeps the machine
simple: a palindrome of length
2n
can be accepted
by pushing
n
characters onto the stack and then
popping
n
characters off. To recognize
any
palindrome requires a few more rules going
from state 1 to state 2.

^[
35
]
The grammar is “context free” in the sense that its rules don’t say anything about
the context in which each piece of syntax may appear; an assignment statement
always
consists of a variable name, equals sign, and expression,
regardless of what other tokens surround it. Not all imaginable languages can be
described by this kind of grammar, but almost all programming languages can.

^[
36
]
This algorithm is called
LL parsing
. The first L stands for
“left-to-right,” because the input string is read in that direction, and the second L
stands for “left derivation,” because it’s always the leftmost (i.e., uppermost) symbol
on the stack that gets expanded.

Turing’s
solution was to equip a
machine with a blank tape of unlimited length—effectively
a one-dimensional array that can grow at both ends as needed—and allow
it to read and write characters anywhere on the tape. A single tape
serves as both storage and input: it can be prefilled with a string of
characters to be treated as input, and the machine can read those
characters during execution and overwrite them if necessary.

A finite state machine with access to an infinitely long tape is
called a
Turing machine
(TM). That name usually
refers to a machine with deterministic rules, but we can also call it a
deterministic Turing machine
(DTM) to be
completely unambiguous.

We already know that a pushdown automaton can only access a single fixed location in its
external storage—the top of the stack—but that seems too restrictive for a Turing machine.
The whole point of providing a tape is to allow arbitrary amounts of data to be stored
anywhere on it and read off again in any order, so how do we design a machine that can
interact with the entire length of its tape?

One option is make the tape addressable by random access, labeling
each square with a unique numerical address like computer RAM, so that
the machine can immediately read or write any location. But that’s more
complicated than strictly necessary, and requires working out details
like how to assign addresses to all the squares of an infinite tape and
how the machine should specify the address of the square it wants to
access.

Instead, a conventional Turing machine uses a simpler arrangement: a
tape
head
that points at a specific position on the tape and can only read or write
the character at that position. The tape head can move left or right by a single square
after each step of computation, which means that a Turing machine has to move its head
laboriously back and forth over the tape in order to reach distant locations. The use of a
slow-moving head doesn’t affect the machine’s ability to access any of the data on the tape,
only the amount of time it takes to do it, so it’s a worthwhile trade-off for the sake of
keeping things simple.

Having access to a tape allows us to solve new kinds of problems beyond simply accepting
or rejecting strings. For example, we can design a DTM for incrementing a binary number
in-place on the tape. To do this, we need to know how to increment a single
digit
of a binary number, but fortunately, that’s easy: if the digit
is a zero, replace it with a one; if the digit is a one, replace it with a zero, then
increment the digit immediately to its left (“carry the one”) using the same technique. The
Turing machine just has to use this procedure to increment the binary number’s rightmost
digit and then return the tape head to its starting position:

This machine is in state 1 when it’s trying to increment a digit, state 2 when it’s
moving back to its starting position, and state 3 when it has finished. Below is a trace of
its execution when the initial tape contains the string
'1011'
; the character currently underneath the tape head is shown surrounded by
brackets, and the underscores represent the blank squares on either side of the input
string.

There are
several “simple operations” we might want a Turing machine
to perform in each step of computation: read the character at the tape
head’s current position, write a new character at that position, move
the head left or right, or change state. Instead of having different
kinds of rule for all these actions, we can keep things simple by
designing a single format of rule that is flexible enough for every
situation, just as we did for pushdown automata.

This unified rule format has five parts:

Here we’re making the assumption that a Turing machine will change state and write a
character to the tape every time it follows a rule. As usual for a state machine, we can
always make the “next state” the same as the current one if we want a rule that doesn’t
actually change state; similarly, if we want a rule that doesn’t change the tape contents,
we can just use one that writes the same character that it reads.

The Turing machine for incrementing a binary number has six rules
when they’re written in this style:

We can show this machine’s states and rules on a diagram similar
to the ones we’ve already been using for finite and pushdown
automata:

In fact, this is just like a DFA diagram except for the labels on
the arrows. A label of the form
a/b;L
indicates a rule that reads character
a
from the tape, writes character
b
, and then moves the tape head one square to
the left; a rule labelled
a/b;R
does
almost the same, but moves the head to the right instead of the
left.

Let’s see how to use a Turing machine to solve a string-recognition problem that
pushdown automata can’t handle: identifying inputs that consist of one or more
a
characters followed by the same number of
b
s and
c
s (e.g.,
'aaabbbccc'
). The Turing machine that solves this problem has 6
states and 16 rules:

It works roughly like this:

If the input string consists of one or more
a
characters followed by the same number of
b
s and
c
s, the machine will make repeated passes across the whole
string, crossing out one of each character on every pass, and then enter an accept state
when the entire string has been crossed out. Here’s a trace of its execution when the input
is
'aabbcc'
:

This machine works because of the exact choice of rules during the scanning stages. For
example, while the machine is in state 3—scanning right and looking for a
c
—it only has rules for moving the head past
b
s and
X
s. If it hits some
other character (e.g., an unexpected
a
), then it has no
rule to follow, in which case it’ll go into an implicit stuck state and stop executing,
thereby rejecting that input.