Last Lecture Revisited State transition graph Source Code String Stream Combination Lexical Units Tokens Pattern Name Non-formalization description Formalization description Computer realization ? Regular expression Letters Combination String Language Set Alphabet Table Plus LUM Conjunction LM Closure L* Positive closure L+ conjunction exponent

2.2 The description and recognition of lexical tokens 2.2.4 Convention  Relational operator convention relop  < | < = | = | < > | > | > =   5 1 6 2 4 8 3 7 return(relop, LE) return(relop, NE) return(relop, LT) return(relop, GE) return(relop, GT) return(relop, EQ) Start < = > * other

Convention of Identifiers and reserved words id  letter (letter | digit )* 9 10 11 Start letter other * letter or digit return(install_id( )) 1、To check the reserved words. If any, return the corresponding token. if none, goto 2. 2、To look for the identifiers. If the unit is there, return the pointer. If not, goto 3. 3、To add the lexical unit in a new item to the identifier set, and return the pointer.

Convention of the unsigned integer num  digit+ (.digit+)? (E (+ | )? digit+)? Start 19 12 13 14 15 16 17 18 digit other . E +/ return( install_num( ) ) *

BLANK Convention delim  blank | tab | newline ws  delim+ 21 22 Start delim other * 20

？ 2.3 The finite automation State convention graph Regular expression Computer realization Equivalence The finite automation Deterministic finite automaton Nondeterministic finite automaton

2.3.1 The nondeterministic finite automaton (NFA) The Corresponding mathematic models State set S； Input identifier set ； Convention function move : S  ({})  P(S)； S0 = Starting point； F  S which is the accepted state set Drawbacks: 1 Input identifiers includes . 2 One state may have several output edges. 1 2 Start a b Language Recognition (a|b)*ab NFA

NFA Convention Input Identifiers a b {0, 1} {0} 1  {2} 2 States 1 2 {0, 1} {0} 1  {2} 2 States 1 2 Start a b Language Recognition (a|b)*ab NFA

The NFA to recognize aa*|bb* 1 2 Start a b 3 4 

2.3.2 The deterministic finite automaton (DFA) The Corresponding mathematic models: State set S； Input identifier set ； Convention function move : S    S； The unique starting point s S； Final states F  S； Advantages： 1 Input identifiers do not include . 2 One state has only one output edge. 1 2 Start a b Language Recognition (a|b)*ab DFA

Subset Construction Method: 2.3.3 From NFA to DFA Subset Construction Method: One state in DFA corresponds with one state set in NFA When got the input a1 a2 … an, NFA can reach the states: s1, s2, …, sk, and DFA can reach {s1, s2, …, sk} 1 2 Start a b

Inputs a b States 1 9 Start  a b 6 7 8 2 3 4 5

Inputs a b A A = {0, 1, 2, 4, 7} States 1 9 Start  a b 6 7 8 2 3 4 5

Inputs a b A B A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} States 1 9 Start  a b 6 7 8 2 3 4 5

Inputs a b A B A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} States 1 9 Start  a b 6 7 8 2 3 4 5

Inputs a b A B C A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} States 1 9 Start  a b 6 7 8 2 3 4 5

Inputs a b A B C A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} States 1 9 Start  a b 6 7 8 2 3 4 5

Inputs a b A B C A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} States 1 9 Start  a b 6 7 8 2 3 4 5

Inputs a b A B C D A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} States 1 9 Start  a b 6 7 8 2 3 4 5

Inputs a b A B C D A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} States 1 9 Start  a b 6 7 8 2 3 4 5

Inputs a b A B C D A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} States 1 9 Start  a b 6 7 8 2 3 4 5

Inputs a b A B C D A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} States 1 9 Start  a b 6 7 8 2 3 4 5

Inputs a b A B C D States 从转换表构造转换图。 B D Start a A b C 1 9 Start  a b a b 6 7 8 2 3 4 5 从转换表构造转换图。 23

1 2 Start a b B D Start a A b C 1 9 Start  a b 6 7 8 2 3 4 5 Language b Language Recognition (a|b)*ab Automaton B D Start a A b C 1 9 Start  a b 6 7 8 2 3 4 5 将前面的DFA和现在的DFA进行比较，引出DFA化简问题。 24

1 2 Start a b B D Start a A b C 1 2 Start a b 1 9 Start  a b 6 7 8 2 Language Recognition (a|b)*ab Automaton 1 2 Start a b B D Start a A b C 1 2 Start a b 1 9 Start  a b 6 7 8 2 3 4 5 将手工构造的NFA和由算法构造的NFA进行比较，鼓励在掌握算法的同时，学会手工构造简单的DFA。 25

2.3.4 DFA Simplification The dead state B D Start a A b a, b C E B D Remain the LEFT and put the dead state E to the RIGHT B D Start a A b a, b C E B D Start a A b C

A and B are distinguishable States A and C are undistinguishable States B D Start a A b C

Method: 1. {A, B, C}, {D} move({A, B, C}, a} = {B} move({A, B, C}, b} = {C, D} 2. {A, C}, {B}, {D} move({A, C}, a} = {B} move({A, C}, b} = {C} B D Start a A b C

Method: 1. {A, B, C}, {D} move({A, B, C}, a} = {B} 2 Start a b Method: 1. {A, B, C}, {D} move({A, B, C}, a} = {B} move({A, B, C}, b} = {C, D} 2. {A, C}, {B}, {D} move({A, C}, a} = {B} move({A, C}, b} = {C} B D Start a A b C

2.4 From the regular expression to the finite automaton State convention graph Computer realization ？ Equivalence The finite automation Deterministic finite automaton Nondeterministic finite automaton Content of this class

NFA to recognize  NFA to recognize a Construct the NFA to recognize  and one symbol i Start  NFA to recognize  a f NFA to recognize a

N (s)  Start f i N (t) NFA to recognize s | t Construct the NFA to recognize the main operators as the selection  f i Start NFA to recognize s | t N (s) N (t)

Start N (s) N (t) i f NFA to recognize st Construct the NFA to recognize the main operators as the conjunction i N (s) f Start NFA to recognize st N (t)

Start  N (s) i f NFA to recognize s* Construct the NFA to recognize the main operators as the closure N (s) f Start NFA to recognize s* i 

For (s), we take N(s) as its NFA.

The NFA of this method has the following attributes: The max number of states of N(r) is twice as many as the number of symbols and operators in r. N(r) has only one start state and one accepted state，and the accepted state has no convention outwards Every state in N(r) has a convention with  pointing to another state or two conventions of  pointing to another state.

The decomposition of (a|b)*ab r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b The decomposition of (a|b)*ab 1 9 Start  a b 6 7 8 2 3 4 5

The decomposition of (a|b)*ab 1 9 Start  a b 6 7 8 2 3 4 5 r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 | The decomposition of (a|b)*ab

The decomposition of (a|b)*ab  1 9 Start a b 6 7 8 2 3 4 5 r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 | The decomposition of (a|b)*ab

The decomposition of (a|b)*ab 1 9 Start  a b 6 7 8 2 3 4 5 r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 | The decomposition of (a|b)*ab

The decomposition of (a|b)*ab 1 9 Start  a b 6 7 8 2 3 4 5 r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 | The decomposition of (a|b)*ab

The decomposition of (a|b)*ab 1 9 Start  a b 6 7 8 2 3 4 5 r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 | The decomposition of (a|b)*ab

The decomposition of (a|b)*ab 1 9 Start  a b 6 7 8 2 3 4 5 r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 | The decomposition of (a|b)*ab

The comparison of the two NFA on (a|b)*ab 1 2 Start a b 1 9 Start  a b 6 7 8 2 3 4 5 比较手工构造的NFA和用教材上语法制导的算法构造的NFA。鼓励学生写出引入尽可能少的 转换的语法制导的算法，在将来的解题中使用这个算法。 44

Appendix : From language to the deterministic finite automaton Example: To find the binary digits divisible by 5 in  ={0,1} Method： 1 List all possible states. 2 Construct the edges and input tokens on every state. 1 2 3 Start 4 《编译原理习题精选》1.5题。 45

Example: To find the binary digits divisible by 5 in  ={0,1} 1 2 3 Start 4

1 2 3 Start 4

1 2 3 Start 4

1 2 3 Start 4

1 2 3 Start 4

1 2 3 Start 4

1 2 3 Start 4

1 2 3 Start 4

1 2 3 Start 4

1 2 3 Start 4

1 2 3 Start 4

Summary State convention graph Regular expression Equivalence Computer realization Regular expression grammar Equivalence Equivalence Subset construction Nondeterministic finite automaton Deterministic finite automaton Minimalist deterministic finite automaton Combining the undistinguishable states Deterministic finite automaton Language Sate enumeration method

习 题 2.7 (c) (d), 2.8 ( 仅为2.7(c) )， 2.12（a） 练习：构造 DFA，接受 0和1的个数都是偶数的二进制串。 eg: 0011, 00, 1100, 1010, 111100