Deterministic Finite State Acceptors play many important roles in computing applications such as compiler design and regular language equivalence testing (the task of determining whether or not two regular languages are indeed the same despite their different looks). And, in certain cases, it is not only convenient but critical that they employ the minimum possible number of states.

Luckily, there are some simple and efficient procedures to reduce/minimize the number of states in a DFA such as methods “Mark” and “Reduce” on pages 67 and 69 of the newly added Other Reference #4.

Task:

To compute and output all equivalent sets of indistinguishable states using the “Mark” method (page 67) of the new Other Reference #4 which was added today to our Course Syllabus.

Sample DFA:

You can use following simplification assumptions to make the required input task relatively simple:

· States are numbered consecutively starting from 1 and state 1 is the Initial State.

· Likewise input symbols are each one character long and are consecutively ordered such as 0, 1, 2, 3, … or a, b, c, d, …

· A DFA may have one or more number of states and zero or more number of Final states.

Under these simplifying assumptions, our sample DFA can be completely specified by the following input frame: (Note comments are NOT parts of inputs)

· 7 // total number of states

· 4 // total number of Final states

· 2 // two input symbols, 0 and 1 in that order

· 1 2 3 4 // these are four Final states. So, the other three states are non-final.

· 1 2 // two transitions of state 0, Q0

· 3 4 // two transitions of state 1, Q1

· 5 5 // two transitions of state 2, Q2

· 3 4

· 5 5

· 6 5

· 6 6 // two transitions of the last state, Q6

Illustration.

Sample DFA: We consider the following DFA with seven states and two input symbols where Q1, Q2, Q3 and Q4 are final.