a) Show that for every nonnegative integer k, Rk is an

Chapter 12, Problem 12.3.58

(choose chapter or problem)

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 s Rk t. b) Show that R* is an equivalence relation on S. We say that two states s and t are *-equivalent if s R* 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 - 1 )-equivalent d) Show that the equivalence classes of Rk are a refinement of the equivalence classes of RkI if k is a positive integer. (The refinement of a partition of a set is defined in the preamble to Exercise 49 in Section 8.5.) e) Show that if s and t are k-equivalent for every nonnegative integer k, then they are *-equivalent. 1) 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 E I.