Understanding Computation (13 page)

We can create a
nondeterministic rulebook and ask it questions:

>>
rulebook
=
NFARulebook
.
new
(
[
FARule
.
new
(
1
,
'a'
,
1
),
FARule
.
new
(
1
,
'b'
,
1
),
FARule
.
new
(
1
,
'b'
,
2
),
FARule
.
new
(
2
,
'a'
,
3
),
FARule
.
new
(
2
,
'b'
,
3
),
FARule
.
new
(
3
,
'a'
,
4
),
FARule
.
new
(
3
,
'b'
,
4
)
]
)
=> #
>>
rulebook
.
next_states
(
Set
[
1
]
,
'b'
)
=> #
>>
rulebook
.
next_states
(
Set
[
1
,
2
]
,
'a'
)
=> #
>>
rulebook
.
next_states
(
Set
[
1
,
3
]
,
'b'
)
=> #

The next step is to implement an
NFA
class to represent the simulated
machine:

class
NFA
<
Struct
.
new
(
:current_states
,
:accept_states
,
:rulebook
)
def
accepting?
(
current_states
&
accept_states
)
.
any?
end
end

This
NFA
class is very similar
to our
DFA
class from earlier. The
difference is that it has a set of possible
current_states
instead of a single definite
current_state
, so it’ll say it’s in
an
accept state if any of its
current_states
is an accept state:

>>
NFA
.
new
(
Set
[
1
]
,
[
4
]
,
rulebook
)
.
accepting?
=> false
>>
NFA
.
new
(
Set
[
1
,
2
,
4
]
,
[
4
]
,
rulebook
)
.
accepting?
=> true

As with the
DFA
class, we can
implement a
#read_character
method
for reading a single character of input, and a
#read_string
method for reading several in
sequence:

class
NFA
def
read_character
(
character
)
self
.
current_states
=
rulebook
.
next_states
(
current_states
,
character
)
end
def
read_string
(
string
)
string
.
chars
.
each
do
|
character
|
read_character
(
character
)
end
end
end

These methods really are almost identical to their
DFA
counterparts; we’re just saying
current_states
and
next_states
in
#read_character
instead of
current_state
and
next_state
.

That’s the hard work over with. Now we’re able to start a
simulated NFA, pass characters in, and ask whether the input so far has
been accepted:

>>
nfa
=
NFA
.
new
(
Set
[
1
]
,
[
4
]
,
rulebook
);
nfa
.
accepting?
=> false
>>
nfa
.
read_character
(
'b'
);
nfa
.
accepting?
=> false
>>
nfa
.
read_character
(
'a'
);
nfa
.
accepting?
=> false
>>
nfa
.
read_character
(
'b'
);
nfa
.
accepting?
=> true
>>
nfa
=
NFA
.
new
(
Set
[
1
]
,
[
4
]
,
rulebook
)
=> #, accept_states=[4], rulebook=…>
>>
nfa
.
accepting?
=> false
>>
nfa
.
read_string
(
'bbbbb'
);
nfa
.
accepting?
=> true

As we saw with the
DFA
class,
it’s convenient to use an
NFADesign
object to automatically manufacture new
NFA
instances on demand rather than creating
them manually:

class
NFADesign
<
Struct
.
new
(
:start_state
,
:accept_states
,
:rulebook
)
def
accepts?
(
string
)
to_nfa
.
tap
{
|
nfa
|
nfa
.
read_string
(
string
)
}
.
accepting?
end
def
to_nfa
NFA
.
new
(
Set
[
start_state
]
,
accept_states
,
rulebook
)
end
end

This makes it easier to check different strings against the same
NFA:

>>
nfa_design
=
NFADesign
.
new
(
1
,
[
4
]
,
rulebook
)
=> #
>>
nfa_design
.
accepts?
(
'bab'
)
=> true
>>
nfa_design
.
accepts?
(
'bbbbb'
)
=> true
>>
nfa_design
.
accepts?
(
'bbabb'
)
=> false

And that’s it: we’ve successfully built a simple implementation of
an unusual nondeterministic machine by simulating all of its possible
executions. Nondeterminism is a convenient tool for designing more
sophisticated finite automata, so it’s fortunate that NFAs are usable in
practice rather than just a theoretical
curiosity.

We’ve seen
how relaxing the determinism constraints gives us new ways
of designing machines without sacrificing our ability to implement them.
What else can we safely relax to give ourselves more design
freedom?

It’s easy to design a DFA that accepts strings of
a
s
whose length is a multiple of two (
'aa'
,
'aaaa'
…):

But how can we design a machine that accepts strings whose length
is a multiple of
two or three
? We know that
nondeterminism gives a machine more than one execution path to follow,
so perhaps we can design an NFA that has one “multiple of two” path and
one “multiple of three” path. A naïve attempt might look like
this:

The idea here is for the NFA to move between states 1 and 2 to accept strings like
'aa'
and
'aaaa'
, and
between states 1, 3, and 4 to accept strings like
'aaa'
and
'aaaaaaaaa'
. That works fine, but the problem is that
the machine also accepts the string
'aaaaa'
, because it
can move from state 1 to state 2 and back to 1 when reading the first two characters, and
then move through states 3, 4, and back to 1 when reading the next three, ending up in an
accept state even though the string’s length is not a multiple of two or three.
^[
22
]

Again it may not be immediately obvious whether an NFA can do this
job at all, but we can address the problem by introducing another
machine feature called
free moves
. These are
rules that the machine may spontaneously follow without reading any
input, and they help here because they give the NFA an initial choice
between two separate groups of states:

The free moves are shown by the dotted unlabeled arrows from state 1 to states 2 and 4.
This machine can still accept the string
'aaaa'
by
spontaneously moving into state 2, and then moving between states 2 and 3 as it reads the
input, and likewise for
'aaaaaaaaa'
if it begins with a
free move into state 4. Now, though, there is no way for it to accept the string
'aaaaa'
: in any possible execution, it must begin by committing
to a free move into either state 2 or state 4, and once it’s gone one way, there’s no route
back again. Once it’s in state 2, it can only accept a string whose length is a multiple of
2, and likewise once it’s in state 4, it can only accept a string whose length is a multiple
of 3.

How do we support free moves in our Ruby NFA simulation? Well, this new choice between
staying in state 1, spontaneously moving into state 2, or spontaneously moving into state 4
is not really any stranger than the nondeterminism we already have, and our implementation
can handle it in a similar way. We already have the idea of a simulated machine having many
possible states at once, so we just need to broaden those possible states to include any
that are reachable by performing one or more free moves. In this case, the machine starting
in state 1 really means that it can be in state 1, 2, or 4 before it’s read any
input.

First we need a way to represent free moves in Ruby. The easiest
way is to use normal
FARule
instances
with a
nil
where a character should
be. Our existing implementation of
NFARulebook
will treat
nil
like any other character, so we can ask
“from state 1, what states can we get to by performing one free move?”
(instead of “…by reading one
a
character?”):

>>
rulebook
=
NFARulebook
.
new
(
[
FARule
.
new
(
1
,
nil
,
2
),
FARule
.
new
(
1
,
nil
,
4
),
FARule
.
new
(
2
,
'a'
,
3
),
FARule
.
new
(
3
,
'a'
,
2
),
FARule
.
new
(
4
,
'a'
,
5
),
FARule
.
new
(
5
,
'a'
,
6
),
FARule
.
new
(
6
,
'a'
,
4
)
]
)
=> #
>>
rulebook
.
next_states
(
Set
[
1
]
,
nil
)
=> #

Next we need some helper code for finding all the states that can be reached by
following free moves from a particular set of states. This code will have to follow free
moves repeatedly, because an NFA can spontaneously change states as many times as it likes
as long as there are free moves leading from its current state. A method on the
NFARulebook
class is a convenient place to put it:

class
NFARulebook
def
follow_free_moves
(
states
)
more_states
=
next_states
(
states
,
nil
)
if
more_states
.
subset?
(
states
)
states
else
follow_free_moves
(
states
+
more_states
)
end
end
end

NFARulebook#follow_free_moves
works by recursively
looking for more and more states that can be reached from a given set of states by following
free moves. When it can’t find any more—that is, when every state found by
next_states(states, nil)
is already in
states
—it returns all the states it’s found.
^[
23
]

This code correctly identifies the possible states of our NFA
before it’s read any input:

>>
rulebook
.
follow_free_moves
(
Set
[
1
]
)
=> #

Now we can bake this free move support into
NFA
by overriding the existing implementation
of
NFA#current_states
(as provided by
Struct
). Our new implementation will
hook into
NFARulebook#follow_free_moves
and ensure that
the possible current states of the automaton always include any states
that are reachable via free moves:

class
NFA
def
current_states
rulebook
.
follow_free_moves
(
super
)
end
end

Since all other
NFA
methods
access the set of possible current states by calling the
#current_states
method, this transparently
provides support for free moves without having to change the rest of
NFA
’s code.

That’s it. Now our simulation supports free moves, and we can see
which strings are accepted by our NFA:

>>
nfa_design
=
NFADesign
.
new
(
1
,
[
2
,
4
]
,
rulebook
)
=> #
>>
nfa_design
.
accepts?
(
'aa'
)
=> true
>>
nfa_design
.
accepts?
(
'aaa'
)
=> true
>>
nfa_design
.
accepts?
(
'aaaaa'
)
=> false
>>
nfa_design
.
accepts?
(
'aaaaaa'
)
=> true

So free moves are pretty straightforward to implement, and they
give us extra design freedom on top of what nondeterminism already
provides.