A finite automaton consists of a set of states, which we shall take to be the in

Question

A finite automaton consists of a set of states, which we shall take to be the integers 1..n and a table transitions[state, input] giving a next state for each state and each input character. For our purposes, we shall assume that the input is always either 0 or 1. Further, certain of the states are designated accepting states. For our purposes, we shall assume that all and only the even numbered states are accepting. Two states p and q are equivalent if either they are the same state, or (i) they are both accepting or both nonaccepting, (ii) on input 0 they transfer to equivalent states, and (iii) on input 1 they transfer to equivalent states. Intuitively, equivalent states behave the same on all sequences of inputs; either both or neither lead to accepting states. Write a program using the MFSET operations that computers the sets of equivalent states of a given finite automaton.

Explanation / Answer

An MFSET (merge-find set), also called a union-find, supports three operations: make-set (which creates a singleton set from a single instance), union (which merges two sets), and find (which determines which set a given element belongs to). Usually, find returns a single element that is a "representative" of the set (and it returns the same representative when called on any element of that set).

Translating this to apply to Deterministic Finite-state Automata (described above) is fairly direct. Initially, each state (from 1 to n) is in its own set; when we find two that are equivalent we union the sets.

We can solve this recursively. (Note that it will be much faster if we memorize/save our answers instead of recomputing every time, especially for the base cases.) Let (p,a) be the value stored in the table at (p, a).

Initialize a union-find data structure with each of the states as singleton sets. Then, loop i from 1 to n, and j from i to n (we only need pairs of states). Within that loop, call the recursive function called "equivalent" defined on two arguments p and q as follows:

(Base case) If p is accepting and q is non-accepting, return false. If find(p) == find(q), return true.

(Recursive case) Check whether equivalent((p,a),(q,a)) is true for all a{0,1}. If so union p and q, and return true. Otherwise return false.

This is a direct translation of the problem statement: Two states are equivalent if the are the same, or (i) they are both accepting or both nonaccepting, (ii) on input 0 they transfer to equivalent states, and (iii) on input 1 they transfer to equivalent states. If (i) is false, or (ii) is false, or (iii) is false, then we return false.

Once we've checked equivalence for all pairs of states, then the union-find data structure will represent the sets of equivalent states on the machine, since every time we return true, we either union p and q, or they were in the same set in the first place.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.