19．算符优先分析中的可归约串是指（最左素短语）。 20．（自下而上）语法分析的关键问题是精确定义可归约串的概念。
四、简答
1．给出上下文无关文法的定义。
一个上下文无关文法G是一个四元式(VT，VN，S，P)，其中： VT是一个非空有限集，它的每个元素称为终结符号；
VN是一个非空有限集，它的每个元素称为非终结符号，VT∪VN=Φ； S是一个非终结符号，称为开始符号；
P是一个产生式集合(有限)，每个产生式的形式是P→α，其中，P∈VN，α∈(VT∪*
VN)。
开始符号S至少必须在某个产生式的左部出现一次。
2．给出正规式与正规集的递归定义。
(1)ε和Φ都是∑上的正规式，它们所表示的正规集分别为{ε}和Φ； (2)任何a∈∑，a是∑上的一个正规式，它所表示的正规集为{a}；
(3)假定U和V都是∑上的正规式，它们所表示的正规集分别记为L(U)和L(V)，那么，
*
(U|V)、(U·V)和(U)也都是正规式，它们所表示的正规集分别为L(U)∪L(V)、L(U)L(V)(连
*
接积)和(L(U))(闭包)。
仅由有限次使用上述三步骤而得到的表达式才是∑上的正规式。仅由这些正规式所表示的字集才是∑上的正规集。
3．设文法G为： S→aAcB|BdS A→BaB|aBc|a B→aScA|cAB|b
对于输入串aacabccb，给出最左推导。
S=>aAcB=>aaBccB=>aacABccB=>aacaBccB=>aacabccB=>aacabccb
4．设文法G为： S→BA A→BS|d B→aA|bS|c
对于输入串adccd，给出最左推导。
S=>BA=>aAA=>adA=>adBS=>adcS=>adcBA=>adccA=>adccd
5
5．证明：文法G：
P→PaP|PbP|cP|Pe|f 为二义文法。
对于文法G定义的句子fbfbf，有两棵不同的语法树：
P P P b P P b P
P b P f f P b P
f f f f
所以该文法是二义文法。
6．证明：文法G：
P→S+S|S*S|i|(S) 为二义文法。
对于文法G定义的句子i+i*i，有两棵不同的语法树：
S S S * S S + S
S + S i i S * S
i i i i
所以该文法是二义文法。
7．给定正规文法G:
S→aS|bA|b a b A→aS
S a A 请构造与之等价的有限自动机。
b f 6
8．给定正规文法G: S→aA
A→bA|aB|b B→aA
请构造与之等价的有限自动机。
b
a b F S A a a
B
9．对下面给出的NFA确定化。
a b
a b a
S A F a a b a 1 2 3 a 4a
10．对下面给出的NFA确定化。 a
S a A
a a Bb 7
a
a 3 2
1 a b a
4b 或
a a
2 a 1 b a
3b
11．对下面给出的DFA最小化。 b a A a a
a
S b B Db b
C a
b
1 a 2 a a
3b
8