Understanding Computation (17 page)

Now we can create an NFA in any set of possible states, feed it a character, and see what
states it might end up in, which is a crucial step for converting an NFA into a DFA. When our
NFA is in state 2 or 3 and reads a
b
, what states can it be
in afterward?

>>
nfa
=
nfa_design
.
to_nfa
(
Set
[
2
,
3
]
)
=> #, accept_states=[3], rulebook=…>
>>
nfa
.
read_character
(
'b'
);
nfa
.
current_states
=> #

The answer: state 1, 2, or 3, as we already discovered during the
manual conversion process. (Remember that the order of elements in a
Set
doesn’t matter.)

Let’s use this idea by creating the
NFASimulation
class
and giving it a method to calculate how the state of the simulation will change in response to
a particular input. We’re thinking of the state of the simulation as being the current set of
possible states for the NFA (e.g., “1, 2, or 3”), so we can write a
#next_state
method that takes a simulation state and a character, feeds that
character to an NFA corresponding to that state, and gets a new state back out by inspecting
the NFA afterward:

class
NFASimulation
<
Struct
.
new
(
:nfa_design
)
def
next_state
(
state
,
character
)
nfa_design
.
to_nfa
(
state
)
.
tap
{
|
nfa
|
nfa
.
read_character
(
character
)
}
.
current_states
end
end

This gives us a convenient way to explore the different states of
the simulation:

>>
simulation
=
NFASimulation
.
new
(
nfa_design
)
=> #
>>
simulation
.
next_state
(
Set
[
1
,
2
]
,
'a'
)
=> #
>>
simulation
.
next_state
(
Set
[
1
,
2
]
,
'b'
)
=> #
>>
simulation
.
next_state
(
Set
[
3
,
2
]
,
'b'
)
=> #
>>
simulation
.
next_state
(
Set
[
1
,
3
,
2
]
,
'b'
)
=> #
>>
simulation
.
next_state
(
Set
[
1
,
3
,
2
]
,
'a'
)
=> #

Now we need a way to systematically explore the simulation states
and record our discoveries as the states and rules of a DFA. We intend to
use each simulation state directly as a DFA state, so the first step is to
implement
NFASimulation#rules_for
,
which builds all the rules leading from a particular simulation state by
using
#next_state
to discover the
destination of each rule. “All the rules” means a rule for each possible
input character, so we also define an
NFARulebook#alphabet
helper method to tell us
what characters the original NFA can read:

class
NFARulebook
def
alphabet
rules
.
map
(
&
:character
)
.
compact
.
uniq
end
end
class
NFASimulation
def
rules_for
(
state
)
nfa_design
.
rulebook
.
alphabet
.
map
{
|
character
|
FARule
.
new
(
state
,
character
,
next_state
(
state
,
character
))
}
end
end

As intended, this lets us see how different inputs will take the
simulation between different states:

>>
rulebook
.
alphabet
=> ["a", "b"]
>>
simulation
.
rules_for
(
Set
[
1
,
2
]
)
=> [
# --a--> #>,
# --b--> #>
]
>>
simulation
.
rules_for
(
Set
[
3
,
2
]
)
=> [
# --a--> #>,
# --b--> #>
]

The
#rules_for
method gives us a way of exploring
outward from a known simulation state and discovering new ones, and by doing this repeatedly,
we can find all possible simulation states. We can do this with an
NFASimulation#discover_states_and_rules
method, which recursively finds more
states in a similar way to
NFARulebook#follow_free_moves
:

class
NFASimulation
def
discover_states_and_rules
(
states
)
rules
=
states
.
flat_map
{
|
state
|
rules_for
(
state
)
}
more_states
=
rules
.
map
(
&
:follow
)
.
to_set
if
more_states
.
subset?
(
states
)
[
states
,
rules
]
else
discover_states_and_rules
(
states
+
more_states
)
end
end
end

Initially, we only know about a single state of the simulation: the set of possible states
of our NFA when we put it into its start state.
#discover_states_and_rules
explores outward from this starting point, eventually
finding all four states and eight rules of the simulation:

>>
start_state
=
nfa_design
.
to_nfa
.
current_states
=> #
>>
simulation
.
discover_states_and_rules
(
Set
[
start_state
]
)
=> [
##,
#,
#,
#
}>,
[
# --a--> #>,
# --b--> #>,
# --a--> #>,
# --b--> #>,
# --a--> #>,
# --b--> #>,
# --a--> #>,
# --b--> #>
]
]

The final thing we need to know for each simulation state is whether
it should be treated as an accept state, but that’s easy to check by
asking the NFA at that point in the simulation:

>>
nfa_design
.
to_nfa
(
Set
[
1
,
2
]
)
.
accepting?
=> false
>>
nfa_design
.
to_nfa
(
Set
[
2
,
3
]
)
.
accepting?
=> true

Now that we have all the pieces of the simulation DFA, we just need an
NFASimulation#to_dfa_design
method to wrap them up neatly as an
instance of
DFADesign
:

class
NFASimulation
def
to_dfa_design
start_state
=
nfa_design
.
to_nfa
.
current_states
states
,
rules
=
discover_states_and_rules
(
Set
[
start_state
]
)
accept_states
=
states
.
select
{
|
state
|
nfa_design
.
to_nfa
(
state
)
.
accepting?
}
DFADesign
.
new
(
start_state
,
accept_states
,
DFARulebook
.
new
(
rules
))
end
end

And that’s it. We can build an
NFASimulation
instance
with any NFA and turn it into a DFA that accepts the same strings: