a) Show that s arid t are O-equivalent if and only if either both s and t are final states or neither s nor t is a final .; state. Conclude that each final state of M, which is an R* -equivalence class, contains only final states of M. b) Show that if k is a positive integer, then s and t are kequivalent if and only if s and t are (k - I)-equivalent and for every input symbol a E I , f(s, a) and f(t, a) are (k - I)-equivalent. Conclude that the transition function 7 is well-defined. c) Describe a procedure that can be used to construct the quotient automaton of a finite-automaton M.

7/26/2017 OneNote Online 3.1 Monday, September 29, 2010:27 AM https://onedrive.live.com/view.aspxref=button&Bsrc=SMIT&resid=36773184373A8F0B!2562&cid=36773184373a8f0b&app=OneNote&authkey=Avz_…...