4. Given the following DFA, to find a minimum-state DFA, (9 points) start- we first construct E. = {{0,1}, { 2,3,4}} start Eo = b 12 E, consists of two components, the set of non-final states {0, 1), and the set of final states {2, 3, 4]. We then construct Ez = {{0, 1}, {2, 4}, {3}} start 0 E- ---- E1 = Two elements in a component of En will remain in the same component in E, if, for each symbol of the alphabet, they are either mapped to the same state or states in the same component of E.. The reason that 3 and 2 are no longer in the same component in Ei is because they are mapped to states not in the same component in E, for symbol a. 3 a 1 2 _a. 2 {0, 1} E {2,3,4} The reason that 3 and 4 are no longer in the same component in E is because they are mapped to states not in the same component in E, for symbol a. 3 E -41 a . 3 {0, 1} {2,3,4} 4 E Next we construct E2 = {{0,1}, {2}, {3}, {4}} start 0 E2 = 6 The criterion used in the construction of Ez is exactly the same as the one used for the construction of E1. The reason that 2 and 4 are not in the same component in Ez is because they are mapped to states not in the same component in Ei for symbol b. 4 _^_. 3 2 a 2 E {3} E {2,4} Then we construct Ez = {{0},{1}, {2}, {3}, {4}}. start- o E3 = The reason that 0 and 1 are no longer in the same component in Ez is because they are mapped to states not in the same component in E2 for symbol b. 0 0 2 1_b. 4 + {2} E {4} Since each component in Ez has one element only, it cannot be further reduced, i.e., if we construct E4, it will be exactly the same as Ez. Hence, we stop the refining process and the states of the minimum-state DFA are: (5 points) The start state is: (2 point) The final states are: (2 points)