答：10是文法G[N]的一个句子，并且有两个不同的最右推导。
（1）1S => E => 10
（2）S => SE => S0 => D0 => 10 因此说明此文法有二义性。
3-03．简述DFA与NFA有何区别 ?
答：DFA与NFA的区别表现为两个方面:一是NFA可以若干个开始状态，而DFA仅只
一个开始状态。另一方面，DFA的映象M是从K×∑到K，而NFA的映象M是从K×∑到K的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。
3-04.试给出非确定自动机的定义。
答：一个非确定的有穷自动机（NFA）M是一个五元组：M=（K，Σ，f，S ，Z）。
其中: 1. K是一个有穷集，它的每个元素称为一个状态； 2. Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表；
3. f是状态转换函数，是在K×Σ*→K的子集的映射，即，f: K×Σ*→2K ；
表明在某状态下对于某输入符号可能有多个后继状态； 4. S﹙K是一个非空初态集； 5. Z﹙K是一个终态集（可空）。
3-05. 为正规式（a|b）*a(a|b) 构造一个等价的确定的有限自动机。
解答：
a,b ? 0
a a 1 2 b 3-06. 给定下列自动机，将其转换为确定的自动机。
d
B ― d d ＋ 注：带＋号的结点为初始状态； d ＋ 带―号的结点为终止状态 ― A C · D ― start S d
ε ε d · E G H ―
d d
解答：(1)消除ε边，得到NFA：
d d B ＋ S ＋ ― A ＋ d d ― d d D 21 ― G d C · E 注：带＋号的结点为初始状态；
带―号的结点为终止状态
d d · H ―
(2)确定化，得到DFA： S A B C D E G H
＋ A ― A d BCE BCE B C D E H H G · G D G d H +[SA] [A] [BCE] [G] [DG] [H] [DH] ＋ ― d [BCE] · [G] [A] [A] [BCE] [G] [BCE] [DG] [H] [DH] [H] [DH] · 注：带＋号的结点为初始状态； ＋ · 带―号的结点为终止状态
＋ SA― A A d d 3-07. 给定下列自动机：· DGd DH― BCE
A A A ―d b d 1 a a 其中：开始状态：0 终止状态：2 a ? 0 2 b b (1)把此自动机转换为确定自动机DFA。
(2)给出此DFA的正则表达式。 解答：（1）： 有状态矩阵如图： a b
?0 0,1 2
1 2 ?
－2 1 2
d ― a b ?0 01 2 01 01 2 －2 1 2 1 2
22
从而可得DFA如图：
a
a 极小化后：
01 ? 0 1 b a b b 1 b ? 0 a 2
b a b 2 -
b （2）此DFA的正则表达式为： (aa*b?b)(b?ab)* 或 a*b（b?ab）*。 4-13.消除下列文法G[E]的左递归。
E→E-T∣T T→T/F∣F F→( E )∣i 解答：
消除文法G[E]的左递归后得到： E→TE’
E’→ -TE’∣ε T→FT’
T’→/FT’∣ε F→( E )∣i
4-14.在LL(1)分析法中,LL分别代表什么含义?
答:第一个L代表从左到右的扫描，第二个L代表每次进行最左推导。 4-15.自顶向下分析思想是什么？
答：从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。如果
全部匹配成功，则表示开始符号可推导出给定的终结符串。因此判定给定终结符号串是正确句子。
4-16.自顶向下的缺点是什么？
答：在推导过程中，如果对文法不做限制。那么产生式的选择成为无根据的，只好
一一去试所有可能的产生式，直至成功为止。这种方法的致命弱点是不断地回溯，大大影响速度。
4-17.LL（1）文法的定义是什么？
答：一个上下文无关文法是LL(1)文法的充分必要条件是每个非终结符A的两个不
同产生式，A→α,A→β；满足SELECT(A →α)∩SELECT(A →β)=Ф。其中，α、β不能同时ε。 4-18.什么是文法的左递归？
23
答：一个文法含有下列形式的产生式之一时：
1)A→Aβ，A∈VN，β∈V*
2)A→Bβ，B→Aα，A、B∈VN，α、β∈V* 则称该文法是左递归的。
4-19.递归下降法的主要思想是什么？
答：对每个非终结符按其产生式结构写出相应语法分析子程序。因为文法递归相应
子程序也递归，子程序的结构与产生式结构几乎一致。所以称此种方法称为递归子程序法或递归下降法。
5-19.自底向上分析法的原理是什么？
答：在采用自左向右扫描，自底向上分析的前提下，该类分析方法是从输入符号串入手，通过反复查找当前句型的句柄（最左简单短语），并使用文法的产生式把句柄归约成相应的非终极符来一步步地进行分析的。最终把输入串归约成文法的开始符号，表明分析成功。 5-20.简单优先方法基本思想是什么？
答：简单优先方法基本思想是首先规定文法符号之间的优先关系和结合性质，然后
在利用这种关系，通过比较两个相邻的符号之间的优先顺序来确定句型的“句柄”并进行归约。
5-21.三种优先关系的定义是什么？ 答：三种优先关系的定义是：
1. sisj 当且仅当存在形如下面的产生式U→?SiSj?
2. sisj 当且仅当存在形如下面的产生式U→?SiW?的生产式，且有 WSj 3. sisj 当且仅当存在形如下面的产生式U→?VW?的生产式,且有 VSi
和WSj
5-22.如何确定简单优先文法的句柄？
答：设S1S2?Sn是简单优先文法的规范句型，其子串SiSi+1?Sj是满足下列条件的最左子串：
Si-1 Si
Si Si+1?? Sj-1 Sj Sj Sj+1
则SiSi+1?Sj定是S1S2?Sn的句柄。 5-23. 给定文法G[Z]：
1． Z→C S
2． C→if E then
其中：Z、C、S、A、E∈VN ； 3． S→A＝E
if、then、＝、∨、i∈VT 4． E→E∨A
5． E→A 6． A→i
a) 构造此文法的LR(0)项目集规范族，并给出识别活前缀的DFA。
24
相关推荐：
loading