Chapter 13.3, Problem 60E

To determine

(a)

To show that $s$ and $t$ are $0-$ equivalent if and only if either both $s\text{ and }t$ are final states or neither of them is a final state and also conclude that each final state of $M$ which is an $R^{*}-$ equivalence class contains only final states of $M$.

To determine

(b)

To prove that $s\text{ and }t$ are also $k-1$ equivalent and to conclude that transition function $\overline{f}$ is well defined.

To determine

(c)

To show that a quotient automaton $\overline{M}$ can’t be constructed form a finite state automaton $M$.