Reference no: EM131577698

Question: We introduce a technique for constructing a deterministic finite-state machine equivalent to a given deterministic finite-state machine(DFSM) with the least number of states possible. Suppose that M = (S, I, , 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], (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, (s, x) and (t, x) are both final states or both not final states.