Reference no: EM131577703
Qusetion: We introduce a technique for constructing a deterministic finite-state machine(DFSM) equivalent to a given deterministic finite-state machine with the least number of states possible. Suppose that M = (S, I, f, s0,F) is a finitestate automaton and that k is a nonnegative integer. Let Rk be the relation on the set S of states of M such that sRkt 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 *-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 - 1)-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.
e) Show that if s and t are k-equivalent for every nonnegative 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.