16.7 k-reversible languages. A nite automaton A0 is said to be k-deterministic if it is deterministic modulo a lookahead k: if two distinct states p and q are both initial, or are both reached from another state r by reading a 2 , then no string u of length k can be read in A0 both from p and q. A nite automaton A is said to be k-reversible if it is deterministic and if AR is k-deterministic. A language L is k-reversible if it is accepted by some k-reversible automaton.

(a) Prove that L is k-reversible i for any strings u; u0; v 2  with jvj = k, SuL(uv) \ SuL(u0v) 6= ; =) SuL(uv) = SuL(u0v):

(b) Show that a k-reversible language admits a characteristic language.

c) Show that the following denes an algorithm for learning k-reversible automata.
Proceed as in the algorithm for learning reversible automata but with the following merging rule instead: merge blocks B1 and B2 if they can be reached by the same string u of length k from some other block and if B1 and B2 are both nal or have a common successor.