13.化简下列各个文法
（1）解：S→bCACdA→cSA| cCCC→cS | c （2）解：S→aAB | fA | gA→e | dDAD→eAB→f （3）解：S→ac
14.消除下列文法中的ε产生式 （1）解：S→aAS | aS | bA→cS
（2）解：S→aAA | aA | aA→bAc| bc | dAe| de 15.消除下列文法中的无用产生式和单产生式 （1）消除后的产生式如下： S→aB | BC B→DB | b C→b D→b | DB
（2）消除后的产生式如下： S→SA | SB |（）|（S）|[] |[S] A→() |（S）|[]|[S] Bà[] |[S]
（3）消除后的产生式如下： E→E+T | T*F | (E) | P↑F | i T→T*F | (E) | P↑F | i F→P↑F | (E) | i P→(E) | i
第三章 词法分析及词法分析程序
3.1试用某种高级语言编写一个FORTRAN源程序的预处理子程序，其功能是： 每调用它一次，即把源程序中的一个完整语句送入扫描缓冲区。要求删去语句中的注释行；删去续行标记字符，把语句中的各行连接起来，并在语句的末端加上语句结束符。此外，还要求此程序具有组织源程序列表输出的功能。
3.2画出用来识别如下三个关键字的状态转移图。 STEP STRING SWITCH
3.3假定有一个猎人带着一只狼、一头山羊和一棵白菜来到一条河的左岸，拟摆渡过河，而岸边只有一条小船，其 大小仅能装载人和其余三件东西中的一件，也就是说，每一次猎人只能将随行者中的一件带到彼岸。若猎人将狼和山羊留在同一岸上而无人照管，那么，狼就会将羊吃掉；如果猎人把山羊和白菜留在同一岸，山羊也会把白菜吃掉。现在，请你用状态转换图作为工具，描述猎人可能采取的种种摆渡方案，并从中找出可将上述三件东西安全地带到右岸的方案来。
3.4设已给文法G=(VN,VT,P,S)，其中，P仅含形如 A→αBA→αα∈V*T，B∈VN
的产生式，试证明： 由此种文法所产生的语言是一正规语言。 3.5试证明： 任何有限个符号串所组成的集合 L={x1,x3,?,xn}xi∈Σ+ 都是3型语言。
3.6试构造一右线性文法，使得它与如下的文法等价 S→ABA→UTU→a|aU T→b|bTB→c|cB
并根据所得的右线性文法，构造出相应的状态转换图。 3.7对于如题图37所示的状态转换图 (1) 写出相应的右线性文法； (2) 指出它接受的最短输入串；
(3) 任意列出它接受的另外四个输入串； (4) 任意列出它拒绝接受的四个输入串。 题图37
3.8对于有限自动机 M=(K,Σ,f,S0,Z)
其中，K={S0,S1,S2,S3,S4,S5},Σ={a,b},Z={S1,S4,S5}。 f由如下的状态转移矩阵给出：
[]a[]bS0[]S2[]S1S1[]S3[]S1S2[]S0[]S4S3[]S0[]S0S4[]S5[]S4S5[]S4[]S0 试找出一个长度最小的输入串，使得：
(1) 在识别此输入串的过程中，每一状态至少经历一次； (2) 每一状态转换至少经历一次。 3.9对于下列的状态转换矩阵： []a[]bS[]A[]SA[]A[]BB[]B[]B(i) 初态：S
终态：B[][][]a[]bS[]A[]BA[]B[]AB[]B[]B(ii) 初态：S 终态：A[]a[]bS[]A[]BA[]C[]AB[]B[]CC[]C[]C(iii) 初态：S 终态：A,C[][][]a[]bS[]A[]SA[]C[]BB[]B[]CC[]C[]C(iv) 初态：S 终态：C
(1) 分别画出相应的状态转换图； (2) 写出相应的3型文法；
(3) 用自然语言分别描述它们所识别的输入串的特征。 3.10对于下面所给的文法： G1=({S,A,B,C,D}, {a,b,c,d},P1,S) P1由如下产生式组成： S→aAS→BA→abS A→bBB→bB→cC C→DD→dD→bB
以及G2=({S,A,B,C,D},{a,b,c,d},P2,S) P2由如下产生式组成： S→AaS→BA→Cc A→BbB→BbB→a C→DC→BabD→d
(1) 试分别对G1和G2构造相应的状态转换图 (提示：对于右线性文法，可将形如C→D的产生式视为C→εD；而对左线性文法，则可将它视为C→Dε)。
(2) 对于G1，构造一等价的左线性文法G1′；对于G2构造一等价的右线性文法G2′。 (3) 对于G1和G1′，分别给出如下符号串的推导序列： abbaababbbcdcbb
对于G2和G2′分别给出如下符号串的推导序列： aabaaabcadca
(4) 试给出若干个不能由G1或G2产生的符号串，并验证它们同样不能用G1′和G2′产生。
3.11分别构造将左线性文法转换为右线性文法以及将右线性文法转换为左线性文法的算法。
3.12将如题图312所示的NFA确定化和最小化。 题图312
3.13将如题图313所示的具有ε动作的NFA确定化。 题图313
3.14将如题图314所示的有限自动机最小化。
3.15试用一种高级语言分别写出将NFA确定化以及将DFA最小化的算法。 3.16构造一产生FORTRAN语言COMMON语句的3型文法 (假定分别用λ和μ代表标识符和整常数，它们都是终结符号，且假定数组的维数不加限定)，构造相应的DFA，并写出描述COMMON语句的正规式。
3.17设r,s等为任意的正规式，试证明下列的关系式成立： (1) r*=(ε|r)*=ε|rr*=(r*)* (2) (rs)*r=r(sr)*
(3) (r|s)*=(r*s*)*=(r*|s*)*
3.18对于解习题36所得的文法，试用正规式描述它所产生的语言。
[]a[]bS0[]S1[]S5S1[]S2[]S7S2[]S3[]S5S3[]S5[]S7S4[]S5[]S5S5[]S3[]S1S6[]S3[]S0S7[]S0[]S1S8[]S3[]S8(1) 初态：S0 终态：S1，S2，S6，
S7[][][]a[]bS0[]S5[]S2S1[]S6[]S2S2[]S0[]S4S3[]S3[]S5S4[]S6[]S2S5[]S3[]S0S6[]S3[]S1(2) 初态：S0 终态：S4,S5,S6题图314
3.19对于习题310所给的文法G1和G2，试分别用正规式描述它们所产生的语言。 3.20设有如下的文法G［〈标号说明〉］： 〈标号说明〉→′LABEL′〈标号表〉 〈标号表〉→d〈标号段〉
〈标号段〉→d〈标号段〉|,〈标号〉|； 〈标号〉→d〈标号段〉
其中′LABEL′,′d′,′,′,′;′等为终结符号。 (1) 试求出描述此文法所产生语言的正规式； (2) 构造识别此语言的具有最少状态的DFA。
3.21求出描述习题37所给有限自动机所识别语言的正规式。 3.22分别构造识别如下正规语言的DFA： (1) ((0*|1)(1*0))* (2) (b|a(aa*b)*b)* (3) a(abab*|a(bab)*a)*b (4) (b|aa|ac|aaa|aac)*
(5) a(a|b)*b(a|b)*a(a|b)*b(a|b)*
3.23试设计一个识别器，它识别由下列英语单词： ONE, TWO, THREE, ?， NINE， TEN，
ELEVEN， TWELVE， THIRTEEN， ?， NINETEEN， TWENTY， THIRTY， FORTY， ?， NINETY， HUNDRED
所表示的从1到999间的任何整数 (各单词间用空格分隔，如THREE HUNDRED FIFTY SIX)，并将它们翻译为相应的阿拉伯数字 (如356)作为输出。 3.24设有辅助定义式 D0=a|b D1=D0D0 D2=D1D1 ?
Dn=Dn-1Dn-1 试回答如下问题：
(1) 由Dn所表述的正规集是什么?
(2) 如果将Dn中所出现的Dn-1用前面已定义的辅助定义式反复进行替换，则可最终将Dn化为Σ={a,b}上的正规式，此正规式有多长? (3) 用来识别Dn的DFA至多需要几个状态?
3.25试将LEX中的“动作子程序”Ai的功能加以扩充，使之可用来生成文本编辑程序。
3.26指出下列LEX正规式所匹配的字符串： (1) \［^{］*\
(2) ^［^a-z］［A-Z］［0-9］$ (3) ［^0-9］|［＼r＼n］
(4) ＼′(［^′＼n］|＼′＼′)+＼′ (5) ＼\［^\＼n］|＼＼［\＼n］)*＼\
3.27写出一个LEX正规式，它能匹配C语言的所有无符号整数 (例如：OX89ab，0123，45，′Z′,′＼t′,′＼xab′,′＼012′,等等)。 3.28写出一个LEX正规式，它能匹配C语言的标识符。
3.29编写一个LEX源程序，它将一个正文文件中的全部小写字母均换为大写字母，并将其中的制表字符、空白字符序列均用单个空格字符进行替换 (提示： 在语义动作中使用全程变量yytext)。
3.30编写一个LEX源程序，它能统计一个PASCAL程序中所含用户定义之标识符个数，并能找出最长标识符中的字符个数 (提示： 使用全程变量yytext及yyleng)。 上 机 实 习 题
对于如下文法所定义的PASCAL语言子集，试编写并上机调试一个词法分析程序： 〈程序〉→〈变量说明〉BEGIN〈语句表〉END.
