question archive A finite automaton consists of a set of states, which we shall take to be the integers 1
Subject:Computer SciencePrice: Bought3
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. Code a program using the
MFSET operations that computes the sets of equivalent states of a given
finite automaton.