By the Lemma, we can choose either B or C as the distinguisher, let's say B. Suppose we also have classes D, E, and F D and E have states with transitions into B on character c, while F has transitions into C on character c. Įxample: Suppose we have an equivalence class Y that splits into equivalence classes B and C. Given a fixed character c and an equivalence class Y that splits into equivalence classes B and C, only one of B or C is necessary to refine the whole partition. When no more splits of this type can be found, the algorithm terminates. Since A is already known to have different behavior than the other sets of the partition, the subsets that lead to A also have different behavior than the subsets that do not lead to A. The algorithm then repeatedly chooses a set A from the current partition and an input symbol c, and splits each of the sets of the partition into two (possibly empty) subsets: the subset of states that lead to A on input symbol c, and the subset of states that do not lead to A. The initial partition is a separation of the states into two subsets of states that clearly do not have the same behavior as each other: the accepting states and the rejecting states. It gradually refines the partition into a larger number of smaller sets, at each step splitting sets of states into pairs of subsets that are necessarily inequivalent. The algorithm starts with a partition that is too coarse: every pair of states that are equivalent according to the Myhill–Nerode relation belong to the same set in the partition, but pairs that are inequivalent might also belong to the same set. The state p while ( W is not empty ) do choose and remove a set A from W for each c in Σ do let X be the set of states for which a transition on c leads to a state in A for each set Y in P for which X ∩ Y is nonempty and Y \ X is nonempty do replace Y in P by the two sets X ∩ Y and Y \ X if Y is in W replace Y in W by the same two sets else if | X ∩ Y | <= | Y \ X | add X ∩ Y to W else add Y \ X to W end end end ( September 2020) ( Learn how and when to remove this template message) Unsourced material may be challenged and removed. Please help improve this section by adding citations to reliable sources.
optionally, re-create a single dead state ("sink" state) if the resulting DFA is required to be complete.remove dead and unreachable states (this will accelerate the following step),.These states can be merged.ĭFA minimization is usually done in three steps: Nondistinguishable states are those that cannot be distinguished from one another for any input string.These states can be removed unless the automaton is required to be complete. Dead states are the states from which no final state is reachable.
The minimal DFA ensures minimal computational cost for tasks such as pattern matching. For each regular language, there also exists a minimal automaton that accepts it, that is, a DFA with a minimum number of states and this DFA is unique (except that states can be given different names).
0 kommentar(er)
