Backgrounds: Deterministic 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 re gular languages not only convenient but critial that they employ the minimum possible number of states are indeed the same despite their different looks). And, in certain cases, it is 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 our textbook. Task Write a program that computes and outputs all equivalent sets of indistinguishable states asing the "Mark" method (page 67) of our textbook Input DFA: Use the Example DFA below in test-running your program You can use following simplification assumptions to make the required input task relatively simple: States are numbered consecutively starting from 0 and state 0 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 input DFA can be completely specified by the following input frame: (Note comments are NOT parts of inputs) / total number of states // total number of Final states /i two input symbols, 0 and 1 in that order // these are four Final states. So, the other three states are non-final. // two transitions of state 0, Q // two transitions of state 1,0 .1234 34 /two transitions of state 2, Q .3 4 .6 s / two transitions of the last state, Qs Illustration. I find the descripion of this procedure in our book a little bit confusing. So, I decided to give an illustration on how it is going to work Example DFA: We consider the following DFA with seven states and two input symbols where Qi, Q2. Qs and Q4 are final. States/inputs Qi Qs Qs Q4 Qs Qs Q4 Qs Our goal of state minimization can be achieved by an indirect approach. That is, although we need to identify all states that can be treated as the same (indistinguishable or equivalent states) so that they can be combined into just one state, we will instead identify every pair of two states that is just the opposite, namely distinguishable pairs. And, the method"Mark" is supposed to find all pairs that are distinguishable pairwise. Since a pair of two states is either distinguishable or indistinguishable, after we find all distinguishable pairs, we are able to identify all indistinguishable pairs from which we can compute all sets of equivalent (indistinguishable) states so that all states in each such set will be combuned into a single state thereby reducing/minimizing the total number of necessary states in the DFA We will maintain a two-column table, distingPairs, that contains all pairs of distinguishable states found so far. By definition, every Final state and every NonFinal state are distinguishable as they are obvious different. So, in our example twelve pairs of a Final state and a Nonfinal state are automatically distinguishable. No computations are needed So, initially distingPairs will show these twelve pairs as follows: (from now I skip subscripts for state notations) 92 95 96 04 2. After this initialization, we iterate computing aditional pairs of two distinguishable states, either both Final or both Nonfinal, until no more are found, using two equations (2.5) and (2.6) of page 68. Iteration-1 We find the following six pairs here: (90.g5),(90.46), q1.42), (q1.44), (q2.q3) and (q3, q4). Note that in the first pair on input symbol 0 (1) from g0 move is to ql which is Final while (2) from qs move is to q6 which is Nonfinal. Also in next state from g0 is Final while the next state from q6 is Nonfinal and so forth. the second pair on input symbol 0 the So, at the end of Iteration-1, the opdated distingRairs will look lke 92 94 ql a5 g6 96 g6 96 92 g4 04 02 04 4. Since at least one additional distinguishable pair has been found during Itean we will go ahead to the Iteration-2 5. Iteration-2 During this iteration, luckily we find no more distinguishable pair in this case. 6. We found a total of 18 distinguishable pairs. As there are 21 possible pairs ou seven states we have, there are a total of three indistinguishable pairs: They are: (ql, q3), (q2, q4) and (g5, q6). So, this example DFA has four classes of indistinguishable sets of states. They are (g0). (ql, q3),(q2, q4) and (q5, q6). This is the expected outputs of yo programn Note that the initial state q0 is not indistinguishable from any state, namely, it is not equivalent to any state we have or it is different from every other state Backgrounds: Deterministic 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 re gular languages not only convenient but critial that they employ the minimum possible number of states are indeed the same despite their different looks). And, in certain cases, it is 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 our textbook. Task Write a program that computes and outputs all equivalent sets of indistinguishable states asing the "Mark" method (page 67) of our textbook Input DFA: Use the Example DFA below in test-running your program You can use following simplification assumptions to make the required input task relatively simple: States are numbered consecutively starting from 0 and state 0 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 input DFA can be completely specified by the following input frame: (Note comments are NOT parts of inputs) / total number of states // total number of Final states /i two input symbols, 0 and 1 in that order // these are four Final states. So, the other three states are non-final. // two transitions of state 0, Q // two transitions of state 1,0 .1234 34 /two transitions of state 2, Q .3 4 .6 s / two transitions of the last state, Qs Illustration. I find the descripion of this procedure in our book a little bit confusing. So, I decided to give an illustration on how it is going to work Example DFA: We consider the following DFA with seven states and two input symbols where Qi, Q2. Qs and Q4 are final. States/inputs Qi Qs Qs Q4 Qs Qs Q4 Qs Our goal of state minimization can be achieved by an indirect approach. That is, although we need to identify all states that can be treated as the same (indistinguishable or equivalent states) so that they can be combined into just one state, we will instead identify every pair of two states that is just the opposite, namely distinguishable pairs. And, the method"Mark" is supposed to find all pairs that are distinguishable pairwise. Since a pair of two states is either distinguishable or indistinguishable, after we find all distinguishable pairs, we are able to identify all indistinguishable pairs from which we can compute all sets of equivalent (indistinguishable) states so that all states in each such set will be combuned into a single state thereby reducing/minimizing the total number of necessary states in the DFA We will maintain a two-column table, distingPairs, that contains all pairs of distinguishable states found so far. By definition, every Final state and every NonFinal state are distinguishable as they are obvious different. So, in our example twelve pairs of a Final state and a Nonfinal state are automatically distinguishable. No computations are needed So, initially distingPairs will show these twelve pairs as follows: (from now I skip subscripts for state notations) 92 95 96 04 2. After this initialization, we iterate computing aditional pairs of two distinguishable states, either both Final or both Nonfinal, until no more are found, using two equations (2.5) and (2.6) of page 68. Iteration-1 We find the following six pairs here: (90.g5),(90.46), q1.42), (q1.44), (q2.q3) and (q3, q4). Note that in the first pair on input symbol 0 (1) from g0 move is to ql which is Final while (2) from qs move is to q6 which is Nonfinal. Also in next state from g0 is Final while the next state from q6 is Nonfinal and so forth. the second pair on input symbol 0 the So, at the end of Iteration-1, the opdated distingRairs will look lke 92 94 ql a5 g6 96 g6 96 92 g4 04 02 04 4. Since at least one additional distinguishable pair has been found during Itean we will go ahead to the Iteration-2 5. Iteration-2 During this iteration, luckily we find no more distinguishable pair in this case. 6. We found a total of 18 distinguishable pairs. As there are 21 possible pairs ou seven states we have, there are a total of three indistinguishable pairs: They are: (ql, q3), (q2, q4) and (g5, q6). So, this example DFA has four classes of indistinguishable sets of states. They are (g0). (ql, q3),(q2, q4) and (q5, q6). This is the expected outputs of yo programn Note that the initial state q0 is not indistinguishable from any state, namely, it is not equivalent to any state we have or it is different from every other state