Please program in java
Program-2 DFA State Minimization 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 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 our textbook. Task: Write a program that computes and outputs all equivalent sets of indistinguishable states using 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 // two input symbols, 0 and 1 in that order I/ these are four Final states. So, the other three states are non-final. // two transitions of state 0, Q /f two transitions of state 1, Q1 /l two transitions of state 2,Q : 1234 123 4 66 I two transitions of the last state, Qs Illustration. I find the description 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 , Q2. Qs and Q4 are final States/inputs Qo Qi Q2 Q4 Qs Q4 Qs Qs Q3 Q3 Q4 Qs Q% 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 combined 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) 96 2.After this initialization, we iterate computing additional pairs of two distinguishable states, cither both Final or both Nonfinal, until no more are found, using two equations (2.5) and (2.6) of page 68. 3. Iteration-1 We find the following six pairs here: (ql.g5), (q0,q6),q1,q2), (ql.q4). (q2.43) and (q3, q4). Note that in the first pair on input symbol 0 (1) from q0 move is to ql which is Final while (2) from q5 move is to q6 which is Nonfinal. Also in the second pair on input symbol 0 the next state from q0 is Fnal while the next state from q6 is Nonfinal and so forth. 2) from q5 move is to q6 which is Nonfinal. Also im the second pair ob input sy b8t0 t state from q0 is Final while the next state from q6 is Nonfinal and so forth. at the end of Iteration-1, the updated distingPairs will look like: 93 9692 94 02 94 4. Since at least one additidhal distinguishable pair has been found during Iteartion-1 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 out of seven states we have, there are a total of three indistinguishable pairs: They are: (ql, q3), (q2, q4) and (qs, q6). 6. We found a total of 18 distinguishable pairs. As there are 21 possible pairs out of seven states we have, there are a total of three indistinguishable pairs: They are: (ql, q3), (2, q4) and (q5, q6. So, this example DFA has four classes of indistinguishable sets of states. They are (g0), (g1, 3), (2,q4) and (q5.g6). This is the expected outputs of your program. 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. Clearly, two states are either indistinguishable or distinguishable. In-distinguishability has the properties of an equivalence relation: Ifp and q are indistinguishable and ifq and r are also indistinguishable, then so are p and r, and all three states are indistinguishable. One method for reducing the states of a dfa is based on finding and combining indistinguishable states. We first describe a method for finding pairs of distinguishable states. procedure: mark 1. Remove all inaccessible states. This can be done by enumerating all simple paths of the graph of 2. Consider all pairs of states(p, q). Ifp e F and q For vice versa, mark the pair 4, q) as 3. Repeat the following step until no previously unmarked pairs are marked. For all pairs (p. q) and We claim that this procedure constitutes an algorithm for marking all distinguishable pairs the dfa starting at the initial state. Any state not part of some path is inaccessible distinguishable all a E , compute (p, a) Pa and (q, a,-qa. If the pair (aAa) is marked as distinguishable. mark (p, q) as distinguishable. procedure: reduce Given a dfa M-( Q , q F), we construct a reduced dfa M (Q..6, ,, F) as follows 1. Use procedure mark to generate the equivalence classes, say , as described. 2. For each set tof such indistinguishable states, create a state labeled iJ...k.for M 3. For each transition rule of M of the form (g,a) ap find the sets to which q, and qp belong. Ifq, e ly,4-...Ak } and qp E {91.Rm rule , q"), add to a 4. The initial state To is that state of whose label includes the 0. 5. F is the set of all the states whose label contains i such that e Example 2.5 Show that the language is regular. L- lawa: wE (a,b To show that this or an other language is regular, all we have to do is find a dfa for it. The construction of a dfa for this language is similar to Example 2.3, but a little more complicated. What this dfa must do is check whether a string begins and ends with an a: what is between is immaterial The solution is complicated by the fact that there is no explicit way of testing the end of the string. This difficulty is overcome by simply putting the dfa into a final state whenever the second a is encountered. If this is not the end of the string, and another b is found, t wil take the dfa out of the final state. Scanning continues in this way, each a taking the automaton back to its final state. The complete solution is shown in Figure 2.6. Again, Example 2.6 Let L be the language in Example 2.5. Show that I2 is regular. Again we show that the language is regular by constructing a dfa for it. We can write an explicit expression for L2, namely Therefore, we need a dfa that recognizes two consecutive strings of essentially the same form (but not necessarily identical in value). The diagram in Figure 2.6 can be used as a starting point, but the vertex q3 has to be modified. This state can no longer be final since, at this point, we must start to look for a second substring of the form awa. To recognize the second substring, we replicate the states of the first part (with new names), with q3 as the beginning of the second part. Since the complete string can be broken into its constituent parts wherever aa occurs, we let the first occurrence of two consecutive a's be the trigger that gets the automaton into its second part. We can do this by making o(q3,a)- q4. The complete solution is in Figure 2.7. This dfa accepts 12, which is therefore regular Program-2 DFA State Minimization 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 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 our textbook. Task: Write a program that computes and outputs all equivalent sets of indistinguishable states using 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 // two input symbols, 0 and 1 in that order I/ these are four Final states. So, the other three states are non-final. // two transitions of state 0, Q /f two transitions of state 1, Q1 /l two transitions of state 2,Q : 1234 123 4 66 I two transitions of the last state, Qs Illustration. I find the description 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 , Q2. Qs and Q4 are final States/inputs Qo Qi Q2 Q4 Qs Q4 Qs Qs Q3 Q3 Q4 Qs Q% 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 combined 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) 96 2.After this initialization, we iterate computing additional pairs of two distinguishable states, cither both Final or both Nonfinal, until no more are found, using two equations (2.5) and (2.6) of page 68. 3. Iteration-1 We find the following six pairs here: (ql.g5), (q0,q6),q1,q2), (ql.q4). (q2.43) and (q3, q4). Note that in the first pair on input symbol 0 (1) from q0 move is to ql which is Final while (2) from q5 move is to q6 which is Nonfinal. Also in the second pair on input symbol 0 the next state from q0 is Fnal while the next state from q6 is Nonfinal and so forth. 2) from q5 move is to q6 which is Nonfinal. Also im the second pair ob input sy b8t0 t state from q0 is Final while the next state from q6 is Nonfinal and so forth. at the end of Iteration-1, the updated distingPairs will look like: 93 9692 94 02 94 4. Since at least one additidhal distinguishable pair has been found during Iteartion-1 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 out of seven states we have, there are a total of three indistinguishable pairs: They are: (ql, q3), (q2, q4) and (qs, q6). 6. We found a total of 18 distinguishable pairs. As there are 21 possible pairs out of seven states we have, there are a total of three indistinguishable pairs: They are: (ql, q3), (2, q4) and (q5, q6. So, this example DFA has four classes of indistinguishable sets of states. They are (g0), (g1, 3), (2,q4) and (q5.g6). This is the expected outputs of your program. 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. Clearly, two states are either indistinguishable or distinguishable. In-distinguishability has the properties of an equivalence relation: Ifp and q are indistinguishable and ifq and r are also indistinguishable, then so are p and r, and all three states are indistinguishable. One method for reducing the states of a dfa is based on finding and combining indistinguishable states. We first describe a method for finding pairs of distinguishable states. procedure: mark 1. Remove all inaccessible states. This can be done by enumerating all simple paths of the graph of 2. Consider all pairs of states(p, q). Ifp e F and q For vice versa, mark the pair 4, q) as 3. Repeat the following step until no previously unmarked pairs are marked. For all pairs (p. q) and We claim that this procedure constitutes an algorithm for marking all distinguishable pairs the dfa starting at the initial state. Any state not part of some path is inaccessible distinguishable all a E , compute (p, a) Pa and (q, a,-qa. If the pair (aAa) is marked as distinguishable. mark (p, q) as distinguishable. procedure: reduce Given a dfa M-( Q , q F), we construct a reduced dfa M (Q..6, ,, F) as follows 1. Use procedure mark to generate the equivalence classes, say , as described. 2. For each set tof such indistinguishable states, create a state labeled iJ...k.for M 3. For each transition rule of M of the form (g,a) ap find the sets to which q, and qp belong. Ifq, e ly,4-...Ak } and qp E {91.Rm rule , q"), add to a 4. The initial state To is that state of whose label includes the 0. 5. F is the set of all the states whose label contains i such that e Example 2.5 Show that the language is regular. L- lawa: wE (a,b To show that this or an other language is regular, all we have to do is find a dfa for it. The construction of a dfa for this language is similar to Example 2.3, but a little more complicated. What this dfa must do is check whether a string begins and ends with an a: what is between is immaterial The solution is complicated by the fact that there is no explicit way of testing the end of the string. This difficulty is overcome by simply putting the dfa into a final state whenever the second a is encountered. If this is not the end of the string, and another b is found, t wil take the dfa out of the final state. Scanning continues in this way, each a taking the automaton back to its final state. The complete solution is shown in Figure 2.6. Again, Example 2.6 Let L be the language in Example 2.5. Show that I2 is regular. Again we show that the language is regular by constructing a dfa for it. We can write an explicit expression for L2, namely Therefore, we need a dfa that recognizes two consecutive strings of essentially the same form (but not necessarily identical in value). The diagram in Figure 2.6 can be used as a starting point, but the vertex q3 has to be modified. This state can no longer be final since, at this point, we must start to look for a second substring of the form awa. To recognize the second substring, we replicate the states of the first part (with new names), with q3 as the beginning of the second part. Since the complete string can be broken into its constituent parts wherever aa occurs, we let the first occurrence of two consecutive a's be the trigger that gets the automaton into its second part. We can do this by making o(q3,a)- q4. The complete solution is in Figure 2.7. This dfa accepts 12, which is therefore regular
