Understanding Computation (19 page)

Instead of doing this job manually, let’s use the rulebook to
build a
DPDA
object that can keep
track of the machine’s current configuration as it reads characters from
the input:

class
DPDA
<
Struct
.
new
(
:current_configuration
,
:accept_states
,
:rulebook
)
def
accepting?
accept_states
.
include?
(
current_configuration
.
state
)
end
def
read_character
(
character
)
self
.
current_configuration
=
rulebook
.
next_configuration
(
current_configuration
,
character
)
end
def
read_string
(
string
)
string
.
chars
.
each
do
|
character
|
read_character
(
character
)
end
end
end

So we can create a
DPDA
, feed
it input, and see whether it’s accepted it:

>>
dpda
=
DPDA
.
new
(
PDAConfiguration
.
new
(
1
,
Stack
.
new
(
[
'$'
]
)),
[
1
]
,
rulebook
)
=> #
>>
dpda
.
accepting?
=> true
>>
dpda
.
read_string
(
'(()'
);
dpda
.
accepting?
=> false
>>
dpda
.
current_configuration
=> #>

Fine so far, but the rulebook we’re using contains a free move, so
the simulation needs to support free moves before it’ll work properly.
Let’s add a
DPDARulebook
helper
method for dealing with free moves, similar to the one in
NFARulebook
(see
Free Moves
):

class
DPDARulebook
def
applies_to?
(
configuration
,
character
)
!
rule_for
(
configuration
,
character
)
.
nil?
end
def
follow_free_moves
(
configuration
)
if
applies_to?
(
configuration
,
nil
)
follow_free_moves
(
next_configuration
(
configuration
,
nil
))
else
configuration
end
end
end

DPDARulebook#follow_free_moves
will repeatedly follow any free moves that apply to the current
configuration, stopping when there are none:

>>
configuration
=
PDAConfiguration
.
new
(
2
,
Stack
.
new
(
[
'$'
]
))
=> #>
>>
rulebook
.
follow_free_moves
(
configuration
)
=> #>

>>
DPDARulebook
.
new
(
[
PDARule
.
new
(
1
,
nil
,
1
,
'$'
,
[
'$'
]
)
]
)
.
follow_free_moves
(
PDAConfiguration
.
new
(
1
,
Stack
.
new
(
[
'$'
]
)))
SystemStackError: stack level too deep

We also need to
wrap the default implementation of
DPDA#current_configuration
to take advantage
of the rulebook’s free move support:

class
DPDA
def
current_configuration
rulebook
.
follow_free_moves
(
super
)
end
end

Now we have a simulation of a DPDA that we can start up, feed characters to, and check
for acceptance:

>>
dpda
=
DPDA
.
new
(
PDAConfiguration
.
new
(
1
,
Stack
.
new
(
[
'$'
]
)),
[
1
]
,
rulebook
)
=> #
>>
dpda
.
read_string
(
'(()('
);
dpda
.
accepting?
=> false
>>
dpda
.
current_configuration
=> #>
>>
dpda
.
read_string
(
'))()'
);
dpda
.
accepting?
=> true
>>
dpda
.
current_configuration
=> #>

If we wrap this simulation up in a
DPDADesign
as usual, we can easily check as
many strings as we like:

class
DPDADesign
<
Struct
.
new
(
:start_state
,
:bottom_character
,
:accept_states
,
:rulebook
)
def
accepts?
(
string
)
to_dpda
.
tap
{
|
dpda
|
dpda
.
read_string
(
string
)
}
.
accepting?
end
def
to_dpda
start_stack
=
Stack
.
new
(
[
bottom_character
]
)
start_configuration
=
PDAConfiguration
.
new
(
start_state
,
start_stack
)
DPDA
.
new
(
start_configuration
,
accept_states
,
rulebook
)
end
end

As expected, our DPDA design can recognize complex strings of
balanced brackets nested to arbitrary depth:

>>
dpda_design
=
DPDADesign
.
new
(
1
,
'$'
,
[
1
]
,
rulebook
)
=> #
>>
dpda_design
.
accepts?
(
'(((((((((())))))))))'
)
=> true
>>
dpda_design
.
accepts?
(
'()(())((()))(()(()))'
)
=> true
>>
dpda_design
.
accepts?
(
'(()(()(()()(()()))()'
)
=> false

There’s one final detail to take care of. Our simulation works
perfectly on inputs that leave the DPDA in a valid state, but it blows
up when the machine gets stuck:

>>
dpda_design
.
accepts?
(
'())'
)
NoMethodError: undefined method `follow' for nil:NilClass

This happens because
DPDARulebook#next_configuration
assumes it
will be able to find an applicable rule, so we shouldn’t call it when
none of the rules apply. We’ll fix the problem by modifying
DPDA#read_character
to check for a usable rule
and, if there isn’t one, put the DPDA into a special stuck state that it
can never move out of:

class
PDAConfiguration
STUCK_STATE
=
Object
.
new
def
stuck
PDAConfiguration
.
new
(
STUCK_STATE
,
stack
)
end
def
stuck?
state
==
STUCK_STATE
end
end
class
DPDA
def
next_configuration
(
character
)
if
rulebook
.
applies_to?
(
current_configuration
,
character
)
rulebook
.
next_configuration
(
current_configuration
,
character
)
else
current_configuration
.
stuck
end
end
def
stuck?
current_configuration
.
stuck?
end
def
read_character
(
character
)
self
.
current_configuration
=
next_configuration
(
character
)
end
def
read_string
(
string
)
string
.
chars
.
each
do
|
character
|
read_character
(
character
)
unless
stuck?
end
end
end