Understanding Computation (21 page)

A nondeterministic
machine is more difficult to simulate than a deterministic
one, but we’ve already done the hard work for NFAs in
Nondeterminism
, and we can reuse the same ideas for NPDAs.
We need an
NPDARulebook
for holding a
nondeterministic collection of
PDARule
s, and its implementation is almost
exactly the same as
NFARulebook
:

require
'set'
class
NPDARulebook
<
Struct
.
new
(
:rules
)
def
next_configurations
(
configurations
,
character
)
configurations
.
flat_map
{
|
config
|
follow_rules_for
(
config
,
character
)
}
.
to_set
end
def
follow_rules_for
(
configuration
,
character
)
rules_for
(
configuration
,
character
)
.
map
{
|
rule
|
rule
.
follow
(
configuration
)
}
end
def
rules_for
(
configuration
,
character
)
rules
.
select
{
|
rule
|
rule
.
applies_to?
(
configuration
,
character
)
}
end
end

In
Nondeterminism
, we simulated an NFA by keeping track of a
Set
of possible states; here we’re simulating an NPDA with a
Set
of possible
configurations
.

Our rulebook needs the usual support for free moves, again
virtually identical to
NFARulebook
’s
implementation:

class
NPDARulebook
def
follow_free_moves
(
configurations
)
more_configurations
=
next_configurations
(
configurations
,
nil
)
if
more_configurations
.
subset?
(
configurations
)
configurations
else
follow_free_moves
(
configurations
+
more_configurations
)
end
end
end

And we need an
NPDA
class to
wrap up a rulebook alongside the
Set
of current configurations:

class
NPDA
<
Struct
.
new
(
:current_configurations
,
:accept_states
,
:rulebook
)
def
accepting?
current_configurations
.
any?
{
|
config
|
accept_states
.
include?
(
config
.
state
)
}
end
def
read_character
(
character
)
self
.
current_configurations
=
rulebook
.
next_configurations
(
current_configurations
,
character
)
end
def
read_string
(
string
)
string
.
chars
.
each
do
|
character
|
read_character
(
character
)
end
end
def
current_configurations
rulebook
.
follow_free_moves
(
super
)
end
end

This lets us step through a simulation of all possible
configurations of an NPDA as each character is read:

>>
rulebook
=
NPDARulebook
.
new
(
[
PDARule
.
new
(
1
,
'a'
,
1
,
'$'
,
[
'a'
,
'$'
]
),
PDARule
.
new
(
1
,
'a'
,
1
,
'a'
,
[
'a'
,
'a'
]
),
PDARule
.
new
(
1
,
'a'
,
1
,
'b'
,
[
'a'
,
'b'
]
),
PDARule
.
new
(
1
,
'b'
,
1
,
'$'
,
[
'b'
,
'$'
]
),
PDARule
.
new
(
1
,
'b'
,
1
,
'a'
,
[
'b'
,
'a'
]
),
PDARule
.
new
(
1
,
'b'
,
1
,
'b'
,
[
'b'
,
'b'
]
),
PDARule
.
new
(
1
,
nil
,
2
,
'$'
,
[
'$'
]
),
PDARule
.
new
(
1
,
nil
,
2
,
'a'
,
[
'a'
]
),
PDARule
.
new
(
1
,
nil
,
2
,
'b'
,
[
'b'
]
),
PDARule
.
new
(
2
,
'a'
,
2
,
'a'
,
[]
),
PDARule
.
new
(
2
,
'b'
,
2
,
'b'
,
[]
),
PDARule
.
new
(
2
,
nil
,
3
,
'$'
,
[
'$'
]
)
]
)
=> #
>>
configuration
=
PDAConfiguration
.
new
(
1
,
Stack
.
new
(
[
'$'
]
))
=> #>
>>
npda
=
NPDA
.
new
(
Set
[
configuration
]
,
[
3
]
,
rulebook
)
=> #
>>
npda
.
accepting?
=> true
>>
npda
.
current_configurations
=> ##>,
#>,
#>
}>
>>
npda
.
read_string
(
'abb'
);
npda
.
accepting?
=> false
>>
npda
.
current_configurations
=> ##>,
#>,
#>
}>
>>
npda
.
read_character
(
'a'
);
npda
.
accepting?
=> true
>>
npda
.
current_configurations
=> ##>,
#>,
#>,
#>
}>

And finally an
NPDADesign
class
for testing strings directly:

class
NPDADesign
<
Struct
.
new
(
:start_state
,
:bottom_character
,
:accept_states
,
:rulebook
)
def
accepts?
(
string
)
to_npda
.
tap
{
|
npda
|
npda
.
read_string
(
string
)
}
.
accepting?
end
def
to_npda
start_stack
=
Stack
.
new
(
[
bottom_character
]
)
start_configuration
=
PDAConfiguration
.
new
(
start_state
,
start_stack
)
NPDA
.
new
(
Set
[
start_configuration
]
,
accept_states
,
rulebook
)
end
end

Now we can check that our NPDA actually does recognize
palindromes:

>>
npda_design
=
NPDADesign
.
new
(
1
,
'$'
,
[
3
]
,
rulebook
)
=> #
>>
npda_design
.
accepts?
(
'abba'
)
=> true
>>
npda_design
.
accepts?
(
'babbaabbab'
)
=> true
>>
npda_design
.
accepts?
(
'abb'
)
=> false
>>
npda_design
.
accepts?
(
'baabaa'
)
=> false