Lecture on Compilation Principles

DFA To minimize

Why minimize

DFA To minimize the number of States is to seek the minimum number of states , And with the original DFA equivalent DFA

significance ： Minimization can reduce the complexity of compiler construction , Improve the running efficiency of the compiler

Minimize whether there is

P56 Theorem 3.2： To any one DFA N There is an equivalent DFA M bring M Contains the minimum number of States , And M only ( Except for isomorphism with different state names )

The minimization algorithm

Pre knowledge

1. Equivalence and distinguishability between states ：

hypothesis s and t by M Two states of

• If from the State s And status t You can read a word when you start α And stop in the final state , said s and t Equivalent

• There is a word α, bring s and t One readout α Stop in the final state , The other reads α Stop in a non final state , said s and t Distinguishable

So through the empty string , All non final states and final states are distinguishable

2. Useless state and unreachable state

Useless state ： There is no path from this state to the final state
Inaccessible state ： There is no path from the initial state to this state

eg：

The detailed steps

1. Preprocessing ： Delete N All useless and unreachable states in

2. Yes N The state set of

• Initial division ：Π={F,S-F [,{error}] }

• Yes Π Each subset of P division , until Π The states of any two different subsets of are distinguishable , And any two states of the same subset are equivalent ( Basis of division )

Basis of division ：

For any subset of States
$$I_j=\{q_1,q_2,q_3...q_k\}$$
If there is an input in the alphabet a, bring
$$\begin{gathered} T(q_i,a)=s,T(q_j,a)=t,sandtNostayWhenfrontdrawbranch\Pi OfrenWhatOneindividualshapestateSonSetin \\ T(q_i,a)andT(q_j,a)OfrenWhatOneindividualnothingsetThe\; righteous \end{gathered}$$
Then you can put $$I_j$$ Split in two

3. Let each subset choose a representative , At the same time, other states of the subset are eliminated

example

P55 chart 3-13