740
Modeling Arithmetic, Computation, and Languages
It is not hard to see that k-equivalence is an equivalence relation on the states
of M (check the reflexive, symmetric and transitive properties). It is possible to test
two states of M for k-equivalence directly, since we can actually produce the finite
number of input strings having no more than k symbols. However, it turns out
that we don’t have to do this. We can begin by finding 0-equivalent states. These
are states producing the same output for 0-length input strings, that is, states having the same associated output symbol. Thus, we can identify the 0-equivalence
classes directly from the description of M.
example 34
Let M be defined by the state table of Table 9.5. (Here we’ve started writing
0, 1, 2 … for states instead of s 0 , s 1 , s 2 , … . ) The 0-equivalence classes of the
states of M are
50, 2, 56 and 51, 3, 4, 66
table 9.5
present state
next state
output
present input
0
1
0
2
3
0
1
3
2
1
2
0
4
0
3
1
5
1
4
6
5
1
5
2
0
0
6
4
0
1
Our procedure to find k-equivalent states is a recursive one; we know how to
find 0-equivalent states, and we will show how to find k-equivalent states once we
have identified states that are (k − 1)-equivalent. Suppose, then, that we already
know which states are (k − 1)-equivalent. If states s i and s j are k-equivalent, they
must produce the same output strings for any input string of length k or less,
which includes any string of length k − 1 or less. Thus, s i and s j must at least be
(k − 1)-equivalent. But they also must produce the same output strings for any
k-length input string.
An arbitrary k-length input string consists of a single arbitrary input symbol
followed by an arbitrary (k − 1)-length input string. If we apply such a k-length
string to states s i and s j (which themselves have the same output symbol), the
single input symbol moves s i and s j to next states s i
′ and s j
′; then s i
′ and s j
′ must
produce identical output strings for the remaining, arbitrary (k − 1)-length string,
which will surely happen if s i
′ and s j
′ are (k − 1)-equivalent. Therefore, to find kequivalent states, look for (k − 1)-equivalent states whose next states under any
input symbol are (k − 1)-equivalent.
Modeling Arithmetic, Computation, and Languages
It is not hard to see that k-equivalence is an equivalence relation on the states
of M (check the reflexive, symmetric and transitive properties). It is possible to test
two states of M for k-equivalence directly, since we can actually produce the finite
number of input strings having no more than k symbols. However, it turns out
that we don’t have to do this. We can begin by finding 0-equivalent states. These
are states producing the same output for 0-length input strings, that is, states having the same associated output symbol. Thus, we can identify the 0-equivalence
classes directly from the description of M.
example 34
Let M be defined by the state table of Table 9.5. (Here we’ve started writing
0, 1, 2 … for states instead of s 0 , s 1 , s 2 , … . ) The 0-equivalence classes of the
states of M are
50, 2, 56 and 51, 3, 4, 66
table 9.5
present state
next state
output
present input
0
1
0
2
3
0
1
3
2
1
2
0
4
0
3
1
5
1
4
6
5
1
5
2
0
0
6
4
0
1
Our procedure to find k-equivalent states is a recursive one; we know how to
find 0-equivalent states, and we will show how to find k-equivalent states once we
have identified states that are (k − 1)-equivalent. Suppose, then, that we already
know which states are (k − 1)-equivalent. If states s i and s j are k-equivalent, they
must produce the same output strings for any input string of length k or less,
which includes any string of length k − 1 or less. Thus, s i and s j must at least be
(k − 1)-equivalent. But they also must produce the same output strings for any
k-length input string.
An arbitrary k-length input string consists of a single arbitrary input symbol
followed by an arbitrary (k − 1)-length input string. If we apply such a k-length
string to states s i and s j (which themselves have the same output symbol), the
single input symbol moves s i and s j to next states s i
′ and s j
′; then s i
′ and s j
′ must
produce identical output strings for the remaining, arbitrary (k − 1)-length string,
which will surely happen if s i
′ and s j
′ are (k − 1)-equivalent. Therefore, to find kequivalent states, look for (k − 1)-equivalent states whose next states under any
input symbol are (k − 1)-equivalent.