In Exercises 58 we introduce a technique for constructing

Chapter , Problem 58E

(choose chapter or problem)

Problem 58E

In Exercises 58 we introduce a technique for constructing a deterministic finite-state machine equivalent to a given deterministic finite-state machine with the least number of states possible. Suppose that M = (S, I, f, so, F) is a finite- state automaton and that k is a nonnegative integer. Let Rk be the relation on the set S of states of M such that Rkt if and only if for every input string x with l(x) ≤ k [where l(x) is the length of x, as usual], f(s, x) and f(t. x) are both final states or both not final states. Furthermore, let R* be the relation on the set of states of M such that sR*t if and only if for every input string x, regardless of length, f(s,x) and f(t,x) are both final states or both not final states.

a) Show that for every nonnegative integer k, Rk is an equivalence relation on S. We say that two states s and t are k-equivalent if sRkt.

b)   Show that R* is an equivalence relation on S. We say that two states s and t are k-equivalent if sR*t.

c) Show that if s and t are two k-equivalent states of M, where k is a positive integer, then s and k are also (k ‒ l)-equivalent

d)   Show that the equivalence classes of Rk are a refinement of the equivalence classes of Rk ‒1 if k is a positive integer. (The refinement of a partition of a set is defined in the preamble to Exercise 49 in Section 9.5.)

e) Show that if s and t are k-equivalent for every non- negative integer k, then they are *-equivalent.

f) Show that all states in a given R*-equivalence class are final states or all are not final states.

g)   Show that if s and t are R*-equivalent, then f(s, a) and f(t, a) are also R*-equivalent for all a ∈ I.