Understanding Computation (21 page)

Read Understanding Computation Online

Authors: Tom Stuart

Tags: #COMPUTERS / Programming / General

That’s great, but the
m
in the
middle of the input string is a cop-out. Why can’t we design a machine
that just recognizes palindromes—
aa
,
abba
,
babbaabbab
, etc.—without having to put a marker
halfway through?

The machine has to change from state 1 to state 2 as soon as it reaches the halfway point
of the string, and without a marker, it has no way of knowing when to do that. As we’ve seen
before with NFAs, these “how do I know when to…?” problems can be solved by relaxing the
determinism constraints and allowing the machine the freedom to make that vital state change
at any point, so that it’s
possible
for it to accept a palindrome by
following the right rule at the right time.

Unsurprisingly, a pushdown automaton without determinism constraints
is called a
nondeterministic pushdown automaton
.
Here’s one for recognizing palindromes with an even number of
letters:
[
34
]

This is identical to the DPDA version except for the rules that lead from state 1 to state
2: in the DPDA, they read an
m
from the input, but here
they’re free moves. This gives the NPDA the opportunity to change state anywhere during the
input string without needing a
marker.

Simulation

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

Other books

The Fires of Spring by James A. Michener
The Imperium by PM Barnes
Sweet Home Carolina by Rice, Patricia
The Dragon of Avalon by T. A. Barron
The Rose of Sarifal by Paulina Claiborne