编译原理 第4章习题解答

第四章 习题解答 4.1

词法分析的主要任务是对源程序进行扫描，从中识别出单词，它是编译过程的第一步，也是编译过程中不可缺少的部分。 4.2

单词符号一般分为五类：关键字、标识符、常数、运算符和界限符。分别用整数1、2、3、4、5表示。对于这种非一符一个类别码的编码形式，一个单词符号除了给出它的单词类别码之外，还要给出它的自身值。标识符的自身值被表示成按字节划分的内部码。常数的自身值是其二进制值。由于语言中的关键字、运算符和界限符的数量都是确定的，因此，对这些单词符号可采用一符一个单词类别码。如果采取一符一个单词类别码，那么这些单词符号的自身值就不必给出了。 4.3

设计词法分析程序有如下几种方法：

①由正规文法设计词法分析程序——程序设计语言的单词一般都可以用正规文法描述，从正规文法可构造一个FA。再对FA确定化和状态个数最少化，最后得到一个化简了的DFA。这个DFA正是词法分析程序的设计框图，这样，由DFA编制词法分析程序就容易了。 ②由正规表达式设计词法分析程序——正规表达式也是描述单词的一种方便工具。由正规表达式转换成NDFA，然后再对它确定化和状态个数最少化，可得一个DFA。再由DFA编制词法分析程序。 4.4

符号表在编译程序中具有十分重要的意义，它是编译程序中不可缺少的部分。在编译程序中，符号表用来存放在程序中出现的各种标识符及其语义属性。一个标识符包含了它全部的语义属性和特征。标识符的全部属性不可能在编译程序的某一个阶段获得，而需要在它的各个阶段中去获得。在编译程序的各个阶段，不仅要用获取的标识符信息去更新符号表中的内容，添加新的标识符及其属性，而且需要去查找符号表，引用符号表中的信息。因为，符号表是编译程序进行各种语义检查（即语义分析）的依据，是进行地址分配的依据。

标识符处理的基本思想是，当遇到定义性标识符时，先去查符号表（标识符表）。如果此标识符已在符号表中登记过，那么表明该标识符被多次声明，将作为一个错误，因为一个标识符只能被声明一次；如果标识符在符号表中未登记过，那么将构造此标识符的机内符，并在符号表中进行登记。而当编译程序遇到使用性标识符时，也要去查符号表，在符号表中必须已登记过此标识符，否则会出现“此标识符未定义”的错误。如果在符号表中查到了这个标识符，就可获取此标识符相应的机内符。 4.5

设要识别的实数包括如下各种形式(正负号可以缺省)：

+dd* +dd*.dd* +dd*.dd*e+dd 其中，d?{0,1,2,3,4,5,6,7,8,9}。为方便起见，用f代表+。

根据实数的构成形式得到相应的状态转换图如图3.17所示。

dA?S?Cf,?NdO??Bf,?GdH?f,?DdE?FdIdPZ3?dQY.dRXdf,?TW?eU?Vd?J.KdL??Z1dM?Z2 图3.17 状态转换图

利用子集法构造确定的有穷自动机如表3.2所示(已换名)。DFA相应的状态图如图3.18所示。

表3.2 将NFA确定化为DFA的过程

I [S,A,B,C,D,G,N] [E,F,Z1,H,I,J,O,P,Q] [D,G,N] [F,Z1,I,J,P,Q] [K,R] [L,M,Z2,T,U,V] [M,Z2,U,V] [W,X] [X] [Y] [Z3] 0 1 2 3 4 5 6 7 8 9 10 Id [E,F,Z1,H,I,J,O,P,Q] 1 [F,Z1,I,J,P,Q] 3 [E,F,Z1,H,I,J,O,P,Q] 1 [F,Z1,I,J,P,Q] 3 [L,M,Z2,T,U,V] 5 [M,Z2,U,V] 6 [M,Z2,U,V] 6 [Y] 9 [Y] 9 [Z3] I. If [D,G,N]2 Ie [K,R] 4 [K,R] 4 [W,X] 7 [W,X] 7 [X] 8 10 d3dd0fd21··4d5ed6de7dfd89d10

图3.18 DFA的状态转换图

对此DFA最小化：首先得到两个子集

K1={0，2，4，7，8，9} (非终态集) K2={1，3，5，6，10} (终态集)

由于K1中状态0有d、f输入，而状态2、4、8、9只有d输入，状态7有f、d输入，而状态0输入d到达终态，状态7输入d到达非终态，所以将K1分割成 K11={0} K12={2，4，8，9} K1={7}

又状态8输入d到达状态9是非终态，而状态2、4、9输入d都到达终态，所以将K12分割成

K121={2，4，9} K122={8}

状态2、4、9是否等价取决于状态1、5、10是否等价。

在状态集K2中，状态1、3有d和.输入，状态5和6有d和e输入，状态10无输入，因而将K2分割成

K21={1，3} K22={5，6} K23={10}

由于状态1、5、10不等价，所以状态2、4、9也不等价。因而将K121分割成 K1211={2} K1212={4} K1213={9}

由于K21中，状态1、3输入d都到达状态3，输入.都到达状态4，所以状态1、3等价。在K22中，状态5和6输入d都到达状态6，输入e都到达状态7，所以状态5和6等价。 这样，将原状态集合分割成以下子集：

{0}，{2}，{4}，{9}，{7}，{8}，{1，3}，{5，6}，{10} 所以最小化DFA状态图如图3.19所示。

用PASCAL语言构造相应词法分析程序。引进如下全局变量和过程。

① ch：字符变量，存放最新读进的源程序字符。 ② word：字符数组，存放构成单词符号的字符串。

dd0fd2图3.19 与NFA等价的DFA

d·4d5ed7fd89d101 ③ ReadChar：子程序，将下一输入字符读进ch，搜索指示器前移一个字符。 ④ IsBlack：子程序，检查ch是否空格。是则调用ReadChar直至ch不为空格。 ⑤ Concat：子程序，将ch中的字符连接到word后。

⑥ IsSign：布尔函数，判断ch中的字符是否为“+”或“–”符号。 IsDigit：布尔函数，判断ch中的字符是否为数字。

⑦ GetNum：实型函数，将word中的字符型数字串转换成数值，并将word清空。参数为0时转换成整数，参数为1时转换成小数。

⑧ InsertConst：整型函数，将word中的常数插入常数表，并返回常数表指针。 ⑨ Return：子程序过程，返回单词的类别和单词自身值。 假定实数以“#”结束。 程序为

type wordtype=packed array[1..20]of char； var word:wordtype； ch:char；

sign1,sign2: integer； value: real；

begin

value: =0；

sign1: =1； sign2: =1； ReadChar； IsBlack；

if IsSign

then begin

if ch= ′– ′ then sign1: = –1；

ReadChar end；

if IsDigit then

begin while (IsDigit) do

begin

Concat； ReadChar end；

value: =GetNum(0)； if ch=′. ′ then

begin ReadChar； if IsDigit then

begin

while (IsDigit) do begin

Concat； ReadChar end；

value:=value+GetNum(1)； if ch= ′e ′ then

begin

ReadChar；

if IsSign

then begin

if ch= ′– ′ then sign2: = –1； ReadChar end；

if IsDigit then begin

/* 是有符号实数 */

/* 是负数 */ /* 读进实数的数值部分 */

/* 读进整数部分 */

/* 整数处理完 */ /* 含有小数部分 */ /* 读进小数数值部分 */

/* 小数数值部分处理完 */

/* 含有指数部分 */ /* 指数含有符号 */

/* 指数为负 */ /* 读进指数数值部分 */

Concat； ReadChar； if IsDigit then

begin Concat； ReadChar；

value: = value*exp(sign2*GetNum(0)*ln(10)) end /* 指数数值读完 */ else error /* 指数不完整(2位数) */ end

else error end

end else error end；

value:=value*sign1；

end else error；

/* 缺指数数值部分 */ /* 指数部分处理完 */ /* 小数数值部分读完 */ /* 缺小数数值部分 */ /* 小数处理完 */ /* 实数处理完 */ /* 非实数 */

if not(ch=′# ′)

then error； /* 实数结束错误 */ return(CONST,value) end；

4.6

为了使词法分析程序结构比较清晰，我们现假定要编译的语言中，全部关键字为保留字。在源程序的输入文本中，关键字、标识符、整常数以及标号之间，若未出现表中所列的那些关系运算符，则至少需用一个空白字符加以分隔。

表：一个语言的单词符号及其分类符

单词符号 begin end if then else 标识符 整数 < <= = <> > >= 类别编码 1 2 3 4 5 6 7 8 9 10 11 12 13 类别码的助记符 单值之值 BEGIN END IF THEN ELSE ID INT LT LE EQ NE GT GE 字母数字串 数字串

图：识别表所列语言单词的DFA及相关的语义过程

l,d CAT START GETCHAR l 非l和d C=0, OUT(ID,TOKEN)

INIT 0 CAT 1 RETRACT 2 C≠0, OUT(C,″ ″)

GETCHAR LOOKUP d CAT GETCHAR d 非d CAT 3 RETRACT 4 OUT(INT,TOKEN) GETCHAR

< =

6 OUT(LE,″ ″) GETCHAR 5 > 非=和> RETRACT =

7 OUT(NE,″″) 8 OUT(LT,″″)

OUT(EQ,″″)

9 > = GETCHAR 10

非= RETRACT

其它 ERROR GETCHAR 1. 2. 3. 4. 5. 6.

11 OUT(GE,″″)

12 OUT(GT,″″)

13 GOTO START

函数GETCHAR 每调用一次就把扫描指示器当前所指示的源程序字符送入字符变量ch，然后把扫描指示器前推一个字符位置。

字符数组TOKEN 用来依次存放一个单词词文中的各个字符。

函数CAT 每调用一次，就把当前ch中的字符拼接于TOKEN中所存字符串的右边。

函数LOOKUP 每调用一次，就以TOKEN中的字符串查保留字符。若查到，就将相应关键字的类别码赋给整型变量C，否则将C置为零。

函数RETRACT 每调用一次，就把扫描指示器回退一个字符位置（即退回多读的那个字符）

函数OUT 一般仅在进入终态时调用此函数，调用的形式为OUT(C,VAL)，其中实参C为相应单词的类别码或其助记符；当所识别的单词为标识符和整数时，实参VAL为TOKEN（即词文分别为字母数字串和数字串），对于其余种类的单词，VAL均为空串。

函数OUT的功能是，在送出一个单词的内部表示之后，返回到调用该词法分析程序的那个程序。

根据图所编写的扫描器： #include #include #include #define ID 6 #define INT 7 #define LT 8 #define LE 9 #define EQ 10 #define NE 11 #define GT 12 #define GE 13 Char TOKEN[20];

extern int lookup(char*); extern void out(int,char*); extern report_error(void); void scanner_example(FILE*fp) {

Char ch; int i,c;

ch=fgetc(fp);

if(isalpha(ch))/*it must be a identifer!*/ {

TOKEN[0]=ch;

ch=fgetc(fp);i=1; while(isalnum(ch)) {

TOKEN[i]=ch;i++; ch=fgetc(fp); }

TOKEN[i]=′\\0′;

fseek(fp,-1,1); /*retract*/ c=lookup(TOKEN);

if(c==0)out(ID,TOKEN); else out(c,″″); } else

if(isdigit(ch)) {

TOKEN[0]=ch;

Ch=fgetc(fp);i=1; While(isdigit(ch))

{

TOKEN[i]=ch;i++; ch=fgetc(fp); }

TOKEN[i]=′\\0′; fseek(fp,-1,1); out(INT,TOKEN);

} else

switch(ch)

{case′<′:ch=fgetc(fp)

if(ch==′=′)out(LE,″″);

else if(ch==′>′)out(NE,″″); else {

fseek(fp,-1,1); out(LT,″″); } break;

case′=′:out(EQ,″″);break; case′>′:ch=fgetc(fp);

if(ch==′=′)out(GE,″″); else {

fseek(fp,-1,1); out(GT,″″); }

break;

default:report_error( );

break;

}

return; }

4.7试用某种高级语言编写一个FORTRAN源程序的预处理子程序，其功能是：每调用它一次，即把源程序中的一个完整语句送入扫描缓冲区。要求删去语句中的注释行；删去续行标记字符，把语句中的各行连接起来，并在语句的末端加上语句结束符。此外，还要求此程序具有组织源程序列表输出的功能。 解：# include char buf[81]; FILE * fp;

int main(int argc,char**argc){ char*p; if(argc= =1){ printf(″Usingdefault file dflt.for\\n″;

fp=fopen(″dflt.for″,″r″); }

else fp=fopen(argv[1],″r″); while(1){

p=readline(fp);

if(p) printf(″%s\\n″,buf),else break; }

return 0; }

char*readline(FILE* FP){ int ch,i=0; char*p=buf; ch=fgetc(fp);

while(ch!=′\\n′&& i<80 && ch!=EOF){ *p++=ch;i++; }

*p=′\\0′;

if(ch!=EOF)return buf;else return NULL; }

4.8描述c语言的lex源程序 解：%{

# include # include # include

# define PLUS ′+′ # define MINUS ′-′ # define STAR ′*′ # define AND ′&′ # define QUEST ′?′ # define COLON ′:′ # define LT ′<′ # define GT ′>′ # define DIV ′/′ # define MOD ′%′ # define OR ′|′ # define XOR ′^′ # define POINT ′.′ # define EXCLAMATION ′!′ # define SWUNG ′~′ # define LP ′(′ # define RP ′)′ # define LC ′{′

# define RC ′}′ # define LB ′[′ # define RB ′]′ # define S-QUOT ′\\′′ # define D-QUOT ′\\″′ # define COMMA ′’′ # define SEMI ′; ′ # define EQUAI ′=′

# define –EOI 300/*end of inpt symbol*/ # define NAME 301/*identifier*/

# define STRING 302/*″string constant″*/

# define ICON 303/*integer or character constant*/ # define FCON 304/*floating point constant*/ # define LE 305/*<=*/ # define GE 306/*>=*/ # define NE 307/*!=*/ # define EQEQ 308/*= =*/ # define L-SHIFT 309/*<<*/ # define R-SHIFT 310/*>>*/ # define ANDAND 311/*&&*/ # define OROR 312/*||*/ # define PLUSPLUS 313/*++*/ # define MINUSMINUS 314/*--*/ # define STRUCTOP 315/*->*/ /***The Keywords are defined in following*/

# define INT 320/*int*/ # define FLOAT 321/*float*/ # define CHAR 322/*char*/ # define DOUBLE 323/*double*/ # define SHORT 324/*short*/ # define LONG 325/*long*/ # define ENUM 326/*enum*/ # define EXTERN 327/*extern*/ # define STATIC 328/*static*/ # define AUTO 329/*auto*/ # define VOLATILE 330/*volatile*/ # define REGISTER 331/*register*/ # define CONST 332/*const*/ # define STRUCT 333/*struct*/ # define UNION 334/*union*/ # define RETURN 335/*return*/ # define GOTO 336/*goto*/ # define IF 337/*if*/

# define ELSE 338/*else*/ # define SWITCH 339/*switch*/ # define BREAK 340/*break*/ # define CONTINUE 341/*continue*/ # define WHILE 342/*while*/ # define DO 343/*do*/ # define FOR 344/*for*/ # define DEFAULT 345/*default*/ # define CASE 346/*case*/ # define SIZEOF 347/*sizeof*/ # define TUPEDEF 348/*typedef*/ # define UNSIGNED 349/*unsigned*/ # define SIGNED 350/*signed*/ # define VOID 351/*void*/

# define ASSPLUS 360/*+=*/ # define ASSMINUS 361/*-=*/ # define ASSSTAR 362/**=*/ # define ASSDIV 363/*/=*/ # define ASSMOD 364/*%=*/ # define ASSAND 365/*&=*/ # define ASSANDAND 366/*&&=*/ # define ASSOR 367/*|=*/ # define ASSOROR 368/*||=*/ # define ASSXOR 369/*^=*/ # define ASSLSHIFT 370/*<<=*/ # define ASSRSHIFT 371/*>>=*/

/* * * * The following definitions are used for preprocess symbols * * * * * * */ # define JINGHAO ′#′/* # */ # define INCLUDE 401/*include*/ # define DEFINE 402/*define*/ # define IFDEF 403/*ifdef*/ # define IFNDEF 404/*ifndef*/ # define ENDIF 405/*endif*/

/**The following definitions are used for ′′,′\\t′,′\\n′etc.and error characters*/ # define WHITE 400 # define ERRORCHAR 500 int Ivalue; double Fvalue; char StrBuf[256];

int CalIValue(int c); /*计算像′L′这样的整常数值函数，L只能是字符

a,b,n,t,f,v六者之一*/

int Calooo(char*str); /*计算形如\\ooo的字符串相应的ASCII值*/ int Cal0oStar(char*str); /*计算八进制字符串0ooo?相应的值*/

int Cal0X(char*str); /*将十六进制字符串0XHHH转换为整数*/

int CalInt(char*str); /*将字符串转换为整数，注意，该串可能以U或L

结尾*/

float CalF(char*str); /*将字符串转换为浮点数*/ %}

letter [_A-Za-Z] alnum [_A-Za-z0-9] h [0-9a-fA-F] o [0-7] d [0-9] suffix [UuL1] white [\\t\\n\\40]

%start COMMENT /*用于处理注释*/

%start PRECOMPLIE /*用于处理预处理命令*/ %%

″/*″ {ECHO;BEGIN COMMENT;} \\n {ECHO;}

″*/″ {ECHO;BEGIN 0;} . {ECHO;}

include {ECHO;return INCLUDE;} define {ECHO;return DEFINE;} ifdef {ECHO;return IFDEF;} ifndef {ECHO;return IFNDEF;} endif {ECHO;return ENDIF;} . {ECHO;}

\\\\n {ECHO;BEGIN 0;}

\\\\″(\\\\\\\\.|[^\\\\″])*\\\\″ {ECHO;return STRING;}

\\\\″(\\\\\\\\.|[^\\\\″])*[\\\\r\\\\n] {printf(″Adding missing \\\\″

to string constant\\\\n″); return STRING;}

′.′ {ECHO;Ivalue=yytext[1];return ICON;}

′\\\\\\\\.′ {ECHO;Ivalue=CalIValue(yytext[2];return ICON;) ′\\\\\\\\{o}({o}{o}?)?′ {ECHO;Ivalue=Calooo(yytext);return ICON;} 0{o}*{suffix}? {ECHO;Ivalue=Cal0oStar(yytext);return ICON;} 0[xX]{h}+{suffix}? {ECHO;Ivalue=Cal0X(yytext);return ICON;} [1-9]{d}*{suffix}? {ECHO;Ivalue=CalInt(yytext);return ICON;} ([1-9]{d}+|{d}+\\\\.{d}*|{d}*\\\\.{d}+)([eE][-+]?{d}+)?[fF]? {ECHO;Fvalue=CalF(vvtext);return FCON;} ″(″ {ECHO;return LP;} ″)″ {ECHO;return RP;} ″{″ {ECHO;return LC;} ″}″ {ECHO;return RC;} ″[″ {ECHO;return LB;}

″]″ {ECHO;return RB;}

″->″ {ECHO;return STRUCTOP;} ″++″ {ECHO;return PLUSPLUS;} ″--″ {ECHO;return MINUSMINUS;} ″<<″ {ECHO;return L-SHIFT;} ″>>″ {ECHO;return R-SHIFT;} ″<=″ {ECHO;return LE;} ″>=″ {ECHO;return GE;} ″<″ {ECHO;return LT;} ″>″ {ECHO;return GT;} ″!=″″+″ {ECHO;return PLUS;} ″-″ {ECHO;return MINUS;} ″*″ {ECHO;return STAR;} ″%″ {ECHO;return MOD;} ″/″ {ECHO;return DIV;} ″~″ {ECHO;return SWUNG;}

″!″ {ECHO;return EXCLAMATIONG;} ″^″ {ECHO;return XOR;} ″|″ {ECHO;return OR;} ″&&″″||″″?″ {ECHO;return QUEST;} ″:″ {ECHO;return COLON;} ″,″ {ECHO;return COMMA;} ″;″ {ECHO;return SEMI;} ″+=″″-=″″*=″″/=″″%=″″&=″″&&=″″|=″″||=″″^=″″<<=″″>>=″int {ECHO;return INT;} float {ECHO;return FLOAT;} char {ECHO;return CHAR;} double {ECHO;return DOUBLE;} short {ECHO;return SHORT;} long {ECHO;return LONG;}

{ECHO;return NE;} {ECHO;return ANDAND;} {ECHO;return OROR;} {ECHO;return ASSPLUS;} {ECHO;return ASSMINUS;} {ECHO;return ASSSTAR;} {ECHO;return ASSDIV;} {ECHO;return ASSMOD;} {ECHO;return ASSAND;} {ECHO;return ASSANDAND;} {ECHO;return ASSOR;} {ECHO;return ASSOROR;} {ECHO;return ASSXOR;} {ECHO;return ASSLSHIFT;} {ECHO;return ASSRSHIFT;}

enum {ECHO;return ENUM;} extern {ECHO;return EXTERN;} static {ECHO;return STATIC;} auto {ECHO;return AUTO;} volatile {ECHO;return VOLATILE;} register {ECHO;return REGISTER;} const {ECHO;return CONST;} struct {ECHO;return STRUCT;} union {ECHO;return UNION;} return {ECHO;return RETURN;} goto {ECHO;return GOTO;} if {ECHO;return IF;} else {ECHO;return ELSE;} switch {ECHO;return SWITCH;} break {ECHO;return BREAK;} continue {ECHO;return CONTINUE;} while {ECHO;return WHILE;} do {ECHO;return DO;} for {ECHO;return FOR;} default {ECHO;return DEFAULT;} case {ECHO;return CASE;} sizeof {ECHO;return SIZEOF;} typedef {ECHO;return TYPEDEF;} unsigned {ECHO;return UNSIGNED;} signed {ECHO;return SIGNED;} void {ECHO;return VOID;} {letter}{alnum}* {ECHO;return NAME;}

# {ECHO;NEGIN PRECOMPILE;}

{while}+ {ECHO;}/*Ignore white space*/

{printf(″Invalid char %s\\\\n″,yytext); return ERRORCHAR;} %%

/* The following functions are used only for testing */ FILE * fout;

Void writeout(int c,char * text) {

static int j=0; switch(c){ case ICON:fprintf(fout,″(%d,%s,%d)″,c,text,Ivalue);break; case FCON:fprintf(fout,″(%d,%s,%d)″,c,text,Fvalue);break; default:fprintf(fout,″(%d,%s)″,c,text);break;

}

if(++j%5= =0)fprintf(fout,″\\\\n″); return

}

void main (int argc,char**argv) {

int c;

if(argc>=2){

if((yyin=fopen(argv[1],″r″))= =NULL){

printf(″Can′t open file %s\\\\n″,argv[1]); exit(1); } if((fout=fopen(″result.dat″,″a+″))==NULL){ printf(″Can′t open file resault.dat\\\\n″); exit(2); }

while(c=yylex()){

writeout(c,yytext); }

fclose(yyin); fclose(fout); return; }

int CalIValue(int c){ /*根据c字符，返回相应的数值*/ switch(c){ case ′n′:return′\\\\′n;\\ case ′b′:return′\\\\′b; case ′t′:return′\\\\′t; case ′a′:return′\\\\′a; case ′f′:return′\\\\′f; case ′v′:return′\\\\′v; default: return 0; } }

int Calooo(char*str){/*将字符串″′\\\\ooo′″转换为八进制数0ooo*/ int I=0; char*p=str; p++;p++;

while(*p!=′\\\\′′){i*=8;i+=(*p-′0′);p++;} return i; }

int Cal0oStar(char*str){ char*p=str; int i=0; p++; while(*p>=′0′&&*p<′9′){

i*=8；

i+=*p-′0′; p++; }

return i; }

int Cal0X(char*str){ int i=0;

char buf[256],*p=str; strcpy(buf,p); p=buf;

while(*p)p++;

p--;if(*p==′L′||*p==′1′||*p==′U′||*p==′u′)*p=0; i=atoi(buf); return i; }

float CalF(char*str){ float f=0.0;

int bitCount=0,e=1,exp=0; char buf[256],*p;

strcpy(buf,str);p=buf;

while(*p!=′.′&&*p!=′E′&&*p!=′e′){ f*=10;f+=*p-′0′;p++; }

if(*p==′.′){ p++;

while(*p!=′E′&&*p!=′e′&&*p!=0){ bitCount--;

f*=10;f+=*p-′0′;p++; }

while(bitCount!=0){ f/=10;bitCount++; } }

if(*p==′E′||*p==′e′){ p++;

if(*p==′-′){e=-1;p++;} else if(*p==′+′)p++; bitCount=0; while(*p){

bitCount*=10;

bitCount+=*p-′0′y; p++; }

if(e==-1)while(bitCount--)f/=10;0; else while(bitCount--)f*=10; }

return f; } 4.9

①②略

③对DFA A最小化的算法可简述如下。

步骤1 构造状态集的划分，直到不再有新的划分产生。构造新划分的算法为 FOR 划分的每一子组G DO

BEGIN

把G进一步划分成新的子组，使得G中的两个状态P和Q属于同一个新子组，当且仅当对任何输入字符a，状态P和Q转换成的状态都属于已有划分的同一个子组。

把这样形成的所有新子组放进划分取代原来的子组G END

步骤2 按步骤1构成最终划分后，取每一组中的一个状态作代表，而删去其它一切等价状态，则所有这些状态代表构成了最小化DFA A?的状态集合。

步骤3 删去A?中所有死状态(即对任何字符a都转换到本身而不可能从它达到终止状态的那些非终止状态，以及不可能从开始状态到达它的那些无用状态)。

本文来源：https://www.bwwdw.com/article/hoxp.html