Understanding Computation (18 page)

Some DFAs have the
property of being
minimal
, which means there’s no way to
design a DFA with fewer states that will accept the same strings. The NFA-to-DFA conversion
process can sometimes produce nonminimal DFAs that contain redundant states, but there’s an
elegant way to eliminate this redundancy, known
as
Brzozowski’s algorithm
:

Surprisingly, the resulting DFA is guaranteed to be minimal and contain no redundant
states. The unhappy downside is that it will only accept
reversed
versions of the original DFA’s strings: if our original DFA accepted the strings
'ab'
,
'aab'
,
'aaab'
, and so on, the minimized DFA will accept strings of the
form
'ba'
,
'baa'
, and
'baaa'
. The trick is to fix this by simply performing
the whole procedure a second time, beginning with the reversed DFA and ending up with a
double-reversed DFA, which is again guaranteed to be minimal but this time accepts the same
strings as the machine we started with.

It’s nice to have an automatic way of eliminating redundancy in a design, but
interestingly, a minimized DFA is also
canonical
: any two DFAs that
accept exactly the same strings will minimize to the same design, so we can check whether
two DFAs are equivalent by minimizing them and comparing the resulting machine designs to
see if they have the same structure.
^[
28
]
This in turn gives us an elegant way of checking whether two regular expressions
are equivalent: if we convert two patterns that match the same strings (e.g.,
ab(ab)*
and
a(ba)*b
) into
NFAs, convert those NFAs into DFAs, then minimize both DFAs with Brzozowski’s algorithm,
we’ll end up with two identical-looking machines.

^[
20
]
This design is general enough to accommodate different kinds
of machines and rules, so we’ll be able to reuse it later in the
book when things get more complicated.

^[
21
]
A finite automaton has no record of its own history and no storage aside from its
current state, so two identical machines in the same state are interchangeable for any
purpose.

^[
22
]
This NFA actually accepts any string of
a
characters except for the single-character string
'a'
.

^[
23
]
Technically speaking, this process computes a
fixed point
of
the “add more states by following free moves” function.

^[
24
]
In this simple case, we could get away with just turning the original start state
into an accept state instead of adding a new one, but in more complex cases (e.g.,
(a*b)*
), that technique can produce a machine that
accepts other undesirable strings in addition to the empty string.

^[
25
]
RE2’s tagline is “an efficient, principled regular
expression library,” which is difficult to argue with.

^[
26
]
Although an NFA only has one start state, free moves can make other states
possible before any input has been read.

^[
27
]
The worst-case scenario for a simulation of a three-state NFA is “1,” “2,” “3,” “1 or
2,” “1 or 3,” “2 or 3,” “1, 2, or 3” and “none.”

^[
28
]
Solving this
graph isomorphism problem
requires a clever
algorithm in itself, but informally, it’s easy enough to look at two machine diagrams
and decide whether they’re “the same.”

A simple way to
add storage to a finite automaton is to give it access to a
stack
, a last-in first-out data structure that characters can be
pushed onto and then popped off again. A stack is a simple and restrictive data
structure—only the top character is accessible at any one time, we have to discard the top
character to find out what’s underneath it, and once we’ve pushed a sequence of characters
onto the stack, we can only pop them off in reverse order—but it does neatly deal with the
problem of limited storage. There’s no built-in limit to the size of a stack, so in
principle, it can grow to hold as much data as necessary.
^[
32
]

A finite state machine with a built-in stack is
called a
pushdown automaton
(PDA), and when that
machine’s rules are deterministic, we call it a
deterministic pushdown automaton
(DPDA). Having access to a stack
opens up new possibilities; for example, it’s easy to design a DPDA that recognizes balanced
strings of brackets. Here’s how it works:

This DPDA uses the size of the stack to count how many unclosed opening brackets it’s
seen so far. When the stack’s empty it means that every opening bracket has been closed, so
the string must be balanced. Watch how the stack grows and shrinks as the machine reads the
string
'(()(()()))'
:

The idea behind
the balanced-brackets DPDA is straightforward, but there
are some fiddly technical details to work out before we can actually
build it. First of all, we have to decide exactly how pushdown automata
rules should work. There are several design issues here:

We can answer all of these questions by choosing a single rule
style that is flexible enough to support everything we need. We’ll break
down a PDA rule into five parts:

The first three parts are familiar from DFA and NFA rules. If a rule doesn’t want the
machine to change state, it can make the next state the same as the current one; if it
doesn’t want to read any input (i.e., a free move), it can omit the input character, as long
as that doesn’t make the machine nondeterministic (see
Determinism
).

The other two parts—a character to pop and a sequence of characters to push—are specific
to PDAs. The assumption is that a PDA will
always
pop the top character
off the stack, and then push some other characters onto the stack, every time it follows a
rule. Each rule declares which character it wants to pop, and the rule will only apply when
that character is on the top of the stack; if the rule wants that character to stay on the
stack instead of getting popped, it can include it in the sequence of characters that get
pushed back on afterward.

This five-part rule format doesn’t give us a way to write rules that apply when the
stack is empty, but we can work around that by choosing a special character to mark the
bottom of the stack—the dollar sign,
$
, is a popular
choice—and then checking for that character whenever we want to detect the empty stack. When
using this convention, it’s important that the stack never becomes truly empty, because no
rule can apply when there’s nothing on the top of the stack. The machine should start with
the special bottom symbol already on the stack, and any rule that pops that symbol must push
it back on again afterward.

It’s easy enough to rewrite the balanced-bracket DPDA’s rules in
this format:

We can show these rules on a diagram of the machine. A DPDA
diagram looks a lot like an NFA diagram, except that each arrow needs to
be labelled with the characters that are popped and pushed by that rule
as well as the character that it reads from the input. If we use the
notation
a;b/cd
to label a rule that
reads
a
from the input, pops
b
from the stack, and then pushes
cd
onto the stack, the machine looks like
this:

The next hurdle is
to define exactly what it means for a PDA to be deterministic. For DFAs, we had
the “no contradictions” constraint: there should be no states where the machine’s next move
is ambiguous because of conflicting rules. The same idea applies to DPDAs, so for example,
we can only have one rule that applies when the machine’s in state 2, the next input
character is an opening bracket, and there’s a
b
on the
top of the stack. It’s even okay to write a free move rule that doesn’t read any input, as
long as there aren’t any other rules for the same state and top-of-stack character, because
that would create an ambiguity about whether or not a character should be read from the
input.

DFAs also have a “no omissions” constraint—there should be a rule for every possible
situation—but that idea becomes unwieldy for DPDAs because of the large number of possible
combinations of state, input character, and top-of-stack character. It’s conventional to
just ignore this constraint and allow DPDAs to specify only the interesting rules that they
need to get their job done, and assume that a DPDA will go into an implicit
stuck
state
if it gets into a situation where none of its rules apply. This is what
happens to our balanced-brackets DPDA when it reads a string like
')'
or
'())'
, because there’s no rule for
reading a closing bracket while in state 1.

Now that we’ve dealt
with the technical details, let’s build a Ruby simulation
of a deterministic pushdown automaton so we can interact with it. We
already did most of the hard work when we simulated DFAs and NFAs, so
this’ll just take a bit of fine-tuning.

The most important thing we’re missing is a stack. Here’s one way
of implementing a
Stack
class:

class
Stack
<
Struct
.
new
(
:contents
)
def
push
(
character
)
Stack
.
new
(
[
character
]
+
contents
)
end
def
pop
Stack
.
new
(
contents
.
drop
(
1
))
end
def
top
contents
.
first
end
def
inspect
"##{
top
}
)
#{
contents
.
drop
(
1
)
.
join
}
>"
end
end

A
Stack
object stores its
contents in an underlying array and exposes simple
#push
and
#pop
operations to push characters onto the
stack and pop them off, plus a
#top
operation to read the character at the top of the stack:

>>
stack
=
Stack
.
new
(
[
'a'
,
'b'
,
'c'
,
'd'
,
'e'
]
)
=> #
>>
stack
.
top
=> "a"
>>
stack
.
pop
.
pop
.
top
=> "c"
>>
stack
.
push
(
'x'
)
.
push
(
'y'
)
.
top
=> "y"
>>
stack
.
push
(
'x'
)
.
push
(
'y'
)
.
pop
.
top
=> "x"

In
Chapter 3
, we saw that we can simulate a deterministic
finite automaton by keeping track of just one piece of information—the DFA’s current
state—and then using the
rulebook to update that information each time a character is read from the
input. But there are
two
important things to know about a pushdown
automaton at each step of its computation: what its current state is, and what the current
contents of its stack are. If we use the word
configuration
to refer
to this combination of a state and a stack, we can talk about a pushdown automaton moving
from one configuration to another as it reads input characters, which is easier than always
having to refer to the state and stack separately. Viewed this way, a DPDA just has a
current configuration, and the rulebook tells us how to turn the current configuration into
the next configuration each time we read a character.

Here’s a
PDAConfiguration
class
to hold the configuration of a PDA—a state and a stack—and a
PDARule
class to represent one rule in a PDA’s
rulebook:
^[
33
]

class
PDAConfiguration
<
Struct
.
new
(
:state
,
:stack
)
end
class
PDARule
<
Struct
.
new
(
:state
,
:character
,
:next_state
,
:pop_character
,
:push_characters
)
def
applies_to?
(
configuration
,
character
)
self
.
state
==
configuration
.
state
&&
self
.
pop_character
==
configuration
.
stack
.
top
&&
self
.
character
==
character
end
end

A rule only applies when the machine’s state, topmost stack
character, and next input character all have the values it
expects:

>>
rule
=
PDARule
.
new
(
1
,
'('
,
2
,
'$'
,
[
'b'
,
'$'
]
)
=> #state=1,
character="(",
next_state=2,
pop_character="$",
push_characters=["b", "$"]
>
>>
configuration
=
PDAConfiguration
.
new
(
1
,
Stack
.
new
(
[
'$'
]
))
=> #>
>>
rule
.
applies_to?
(
configuration
,
'('
)
=> true

For a finite automaton, following a rule just means changing from
one state to another, but a PDA rule updates the stack contents as well
as the state, so
PDARule#follow
needs
to take the machine’s current configuration as an argument and return
the next one:

class
PDARule
def
follow
(
configuration
)
PDAConfiguration
.
new
(
next_state
,
next_stack
(
configuration
))
end
def
next_stack
(
configuration
)
popped_stack
=
configuration
.
stack
.
pop
push_characters
.
reverse
.
inject
(
popped_stack
)
{
|
stack
,
character
|
stack
.
push
(
character
)
}
end
end

>>
stack
=
Stack
.
new
(
[
'$'
]
)
.
push
(
'x'
)
.
push
(
'y'
)
.
push
(
'z'
)
=> #
>>
stack
.
top
=> "z"
>>
stack
=
stack
.
pop
;
stack
.
top
=> "y"
>>
stack
=
stack
.
pop
;
stack
.
top
=> "x"

So, if we have a
PDARule
that
applies to a
PDAConfiguration
, we can
follow it to find out what the next state and stack will be:

>>
rule
.
follow
(
configuration
)
=> #>

This gives us enough to implement a rulebook for DPDAs. The
implementation is very similar to the
DFARulebook
from
Simulation
:

class
DPDARulebook
<
Struct
.
new
(
:rules
)
def
next_configuration
(
configuration
,
character
)
rule_for
(
configuration
,
character
)
.
follow
(
configuration
)
end
def
rule_for
(
configuration
,
character
)
rules
.
detect
{
|
rule
|
rule
.
applies_to?
(
configuration
,
character
)
}
end
end

Now we can assemble the rulebook for the balanced-brackets DPDA
and try stepping through a few configurations and input characters by
hand:

>>
rulebook
=
DPDARulebook
.
new
(
[
PDARule
.
new
(
1
,
'('
,
2
,
'$'
,
[
'b'
,
'$'
]
),
PDARule
.
new
(
2
,
'('
,
2
,
'b'
,
[
'b'
,
'b'
]
),
PDARule
.
new
(
2
,
')'
,
2
,
'b'
,
[]
),
PDARule
.
new
(
2
,
nil
,
1
,
'$'
,
[
'$'
]
)
]
)
=> #
>>
configuration
=
rulebook
.
next_configuration
(
configuration
,
'('
)
=> #>
>>
configuration
=
rulebook
.
next_configuration
(
configuration
,
'('
)
=> #>
>>
configuration
=
rulebook
.
next_configuration
(
configuration
,
')'
)
=> #>