语言可以用正则表达式表示为 C 。其含义为 D 。 A: ①歧义的 ②非歧义的 ③确定的 ④非确定的 B:
C： ①(0|1)* ②00(0|1)* ③(0|1)*00 ④0(0|1)*0 D：①由0和1所组成的符号串的集合；
②以0为头符号和尾符号、由0和1所组成的符号串的集合； ③以两个0结束的，由0和1所组成的符号串的集合； ④以两个0开始的，由0和1所组成的符号串的集合。
答案 A:③ B:② C:② D:④ 3.2 (1)有穷自动机接受的语言是正则语言。（） (2)若r1和r2是Σ上的正规式，则r1|r2也是。（）
(3)设M是一个NFA，并且L(M)＝{x,y,z}，则M的状态数至少为4个。 (4)令Σ＝{a,b}，则Σ上所有以b为首的字构成的正规集的正规式为b*(a|b)*。
(5)对任何一个NFA M，都存在一个DFA M'，使得L(M')=L(M)。（）
(6)对一个右线性文法G，必存在一个左线性文法G'，使得L(G)=L(G')，反之亦然。（）
答案 (1) T (2) T (3) F (4) F (5) T 3.3 描述下列各正规表达式所表示的语言。 (1) 0(0|1)*0 (2) ((ε|0)1*)* (3) (0|1)*0(0|1)(0|1) (4) 0*10*10*10*
(5) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
答案 (1) 以0开头并且以0结尾的，由0和1组成的所有符号串
(2) {α|α∈{0,1}*}即由0和1组成的所有符号串。 (3) 由0和1组成的符号串，且从右边开始数第3位为0。 (4) 含3个1的由0和1组成的所有符号串。 {α|α∈{0,1}+，且α中含有3个1 } (5) {α|α∈{0,1}*,α中含0和1的数目为偶数。} 4.10 已知文法G[S]，其产生式如下：S→(L)|a L→L,S|S 文法G[S]的算符优先关系由下表给出。建立与下表相应的算符优先函数并用算符优先分析法分析句子(a,(a,a))。 文法G[S]的算符优先关系表：
解：对每个终结符或＄建立符号f与g，把f(和g)分成一组。 根据G[S]的算符优先关系表，画出如下的有向图:
优先函数如下：
用算符优先分析法分析句子(a,(a,a))
4.19 (1) 存在有左递归规则的文法是LL(1)的。 (2) 任何算符优先文法的句型中不会有两个相邻的非终结符号。 (3) 算符优先文法中任何两个相邻的终结符号之间至少满足三种 关系(＜·，·＞，
)之一。
(4) 任何LL(1)文法都是无二义性的。 (5) 每一个SLR(1)文法也都是LR(1)文法。
(6) 存在一种算法，能判定任何上下文无关文法是否是LL(1)的。 (7) 任何一个LL(1)文法都是一个LR(1)文法，反之亦然。 (8)' LR(1)'括号中的1是指，在选用产生式A→α进行分析，看当前读入符号是否在FIRST(α)中。
答案：(1)× (2)√ (3)× (4)√ (5)√ (6)√ (7)× (8)× 4.20 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类。__A__和LL(1)分析法属于自顶向下分析；__B__和LR分析法属于自底向上分析。自顶向下分析试图为输入符号串构造一个__C__；自底向上分析试图为输入符号串构造一个__D__。采用自顶向下分析方法时，要求文法中不含有__E__。 A、B： ①深度分析法 C、D： E：
③算符优先分析法
①语法树 ③最左推导 ①右递归 ③直接右递归
②宽度优先分析法 ④预测递归分析法
②有向无环图 ④最右推导 ②左递归 ④直接左递归
A：④ B：③ C：③ D：④ E：②