解：状态转换表为

{1} {2,3,4,5,7,10} {4,5,6,7,9,10} {4,5,7,8,9,10} 最小化DFA为：

letter {2,3,4,5,7,10} {4,5,6,7,9,10} {4,5,6,7,9,10} {4,5,6,7,9,10} digit {4,5,7,8,9,10} {4,5,7,8,9,10} {4,5,7,8,9,10}

例2.19 将下面与正则表达式(a| ε) b*对应的DFA进行最小化。

解：状态转换表为

{1} {2} {3} 最小化DFA为：

a {2} b {3} {3} {3}

词法分析代码：

state := 1; {start}

while state = 1 or 2 do case state of

1: case input character of

letter: advance the input;

state := 2;

else state := ... {error or other}; end case;

2: case input character of letter, digit: advance the input;

state := 2; {actually unnecessary} else state := 3; end case; end case; end while;

if state = 3 then accept else error;

state := 1; {start}

while state = 1, 2, 3 or 4 do case state of

1: case input character of “/”: advance the input; state := 2;

else state := ... ; {error or other} end case;

2: case input character of “*”: advance the input; state := 3;

else state := ... ; {error or other} end case;

3: case input character of “*”: advance the input; state := 4;

else advance the input; {and stay in state 3} end case;

4: case input character of

“/” : advance the input; state := 5;

“*”: advance the input; {and stay in state 4} else advance the input; state := 3; end case; end case; end while;

if state = 5 then accept else error;

递归子程序分析法

问题1： G[S] = { }

S → aA | bB A → cdA | d B → efB | f

试编写一个能分析该文法所对应任何串（如串acdd）的程序。

void match( expectedToken ){ if( token == expectedToken ) getToken(); else

Error(); }

void S(){

if( token == ‘a’ ){ match(‘a’); A();

}else if( token == ‘b’ ){ match(‘b’); B();

}else Error(); }//S

void A(){

if( token == ’c’ ){ match(‘c’); match(‘d’); A();

}else if( token == ‘d’ ){ match(‘d’); }else Error(); }//A

void B(){

if( token == ‘e’ ){ match(‘e’); match(‘f’); B();

}else if( token == ‘f’ ){