编译原理教学课件：Chapter 3 - Lexical Analysis.pptVIP

* * Associated computation on the set of states Ia Subset I is a set of states, a is a character in the alphabet Move（I,a）={t | s∈I, and s t} Ia= ε_closure ( Move( I , a ) ) a 1 2 5 3 4 6 8 7 a a ? ? ? ? ? a I={1}, Ia=? 1 a 4 5 a 3 a 2 ? 7 ? 8 ? 6 2 ? ? Ia Problem： I={2}, Ia=？ 2 3 a 8 ? Ia 1 a 4 5 a ? … … 1: ?-closure(I)={1,2}； 3: Ia =?-closure({5,3,4}) ={2,3,4,5,6,7,8}； 2: move({1,2},a)={5,4,3} Constructing a DFA M’ form a given NFA M 4 f 3 5 6 2 1 i ? ? ? ? a a a a b b b b {i，1，2} Ia Ib {1，2，3} {1，2，3} {1，2，4} {1，2，4} {1, 2, 3, 5, 6, f} {1, 2, 3, 5, 6, f} {1, 2, 3, 5, 6, f} {1, 2, 3, 6, f} {1, 2, 3, 6, f} {1, 2, 4, 5, 6, f} {1, 2, 4, 6, f} {1, 2, 4, 5, 6, f} {1, 2, 4, 5, 6, f} {1, 2, 4, 6, f} S {1，2，3} A {1，2，4} B {1, 2, 3, 5, 6, f} C {1, 2, 4, 5, 6, f} D {1, 2, 4, 6, f} E {1, 2, 3, 6, f} F A C A C F F C B B D E D D E S b A a a C a a B b b D b E b b a b F a F a * * 2.4.3 Minimizing the Number of States in a DFA They are all DFA for regular expression a*,but the later is minimal TheoryGiven any DFA, there is an equivalent DFA containing a minimum number of states, and that this minimum-state DFA is unique a a a * * Equivalent States If s and t are two states, they are equivalent if and only if: s and t are both accepting states or both nonaccepting states. For each character ‘a’ of the alphabet ,s and t have transitions on ‘a’ to the equivalent states * * Example C and F are all accepting states. they have transitions on ‘a’ to C, and have transitions on ‘b’ to E, so they are equivalent states S is a nonaccepting state and C is a accepting state, they are not equivalent states a C D B A E F S b a a a a a b b b b b a b F * * Minimizing Algorithm Split the set of states into some unintersected sets, so states in one set are equivalent to each other, while any two states of different sets are distinguishable. First, split the set of states into two sets, one consists of all accepting states and the other consists of all nonaccepting states. Consi