内容发布更新时间 : 2024/11/16 22:28:32星期一 下面是文章的全部内容请认真阅读。
作业一
1.已知文法G[A]，写出它定义的语言描述 如：G[A]:
A → 0B|1C
B → 1|1A|0BB C → 0|0A|1CC
2. 给出生成下述语言的上下文无关文法：
nnmm
（1）{ abab| n，m>=0}
nm mn
(2) { 1010| n，m>=0}
3. 给出生成下述语言的三型文法：
nm
(1){ ab|n,m>=1 }
nmk
(2){abc|n,m,k>=0 }
4、文法G[E]为： E→E+T|T T→T*F|F F→(E)|i
试给出句型(E+F)*i的短语，简单(直接)短语,句柄。
第3章练习题
一、判断题:
1、 编译程序中的词法分析程序以字符形式的源程序作为输入，输出的单词符号常
采用二元组的形式。
2、 正规式的运算符“|”读作“或“。
3、 若两个正规式所表示的正规集相同，则认为二者是等价的。
4、 用l代表字母，d代表数字，Σ={l，d}，则正规式r=dd*定义了无符号整数单词。 5、 一个确定的有穷自动机DFA M的转换函数f是一个从KⅹΣ到K 的子集的映像。
*
6、 一个非确定的有穷自动机NFA N 的转换函数f是一个从KⅹΣ到K 的映像。
7、 一张状态转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。 8、 终态与非终态是可区别的。
9、 对任意一个右线性文法G，都存在一个NFA M，满足L（G）=L（M）。 10、 对任意一个右线性文法G，都存在一个DFA M，满足L（M）=L（R）。
二、构造正规式1(0|1)*101相应的DFA.
练习题2
一、判断题： 1、 空符号串的集合{ε}={}=ф。
0
2、 设A是符号串的集合，则A=ε。
*,
3、 设G是一个文法，S是开始符号，如果S => x且x∈VT则称x是文法G[S]的句型。 4、 在形式语言中，最右推导的逆过程也称为规范归约。 5、 一个语言的文法是唯一的。 6、 若一个语言是无穷集合，则定义该语言的文法一定是递归的。 7、 一个句型中出现某个产生式的右部，则此右部一定是此句型的句柄。
8、 每个直接短语都是某规则的右部。 9、 用二义性文法定义的语言也是二义性的。
10、 文法的二义性与语言的二义性是两个不同的概念。 11、 任何正规文法都是上下文无关文法。
12、 正规文法对规则的限制比上下文无关文法对规则的限制要多一些。 二、选择题（从各题的4个答案中选出一个或多个正确的答案写在横线上） （1） 一般程序设计语言的描述都涉及（ ）3个方面。 A 语法 B 语用 C 语义 D 基本符号的确定
（2）为了使编译程序能对程序设计语言进行正确的翻译，必须采用（ ）方法定义程序设计语言。
Ａ 非形式化 Ｂ 自然语言描述问题 Ｃ 形式化 D自然语言和符号体系相结合
0
（3） 设x是符号串的幂运算 x=（ ）。
A 1 B x C ε D Φ
*
（4）设A是符号串的集合，则A=（ ）。
12N
A A∪A∪?∪A∪?
012N
B A∪A∪A∪?∪A∪?
+
C {ε}∪A
0+
D A∪A
（5）字母表中的元素可以是（ ） A 字母 B字母和数字 C 数字 D字母、数字和其他符号
（6） 文法用来描述语言的语法结构，它由如下4个部分组成：（ ）和文法开始符号。
A文法终结符集合 B 文法规则的集合 C 文法非终结符集合 D字母数字串
（7）在规则中，符号“→”（：：=）表示（ ）。 A 恒等于 B 等于 C 取决于 D 定义为 （8）在规则中，符号“|”表示（ ）。
A 与 B 或 C 非 D 定引导开关参数 （9）设文法G[E]的规则如下：
A→A1|A0|Aa|Ac|a|b|c ,该文法的句子是下列符号串（ ）
A ab0 B a0c01 C aaa D bc10
(10) 如果在推导过程中的任何一步α=>β,都是对α中的最右非终结符进行替换，则称这种推导为（ ）。
A．直接推导 B.最右推导 C. 最左推导 D.规范推导
mn
（11）描述语言L={ab|n≥m≥1}的文法为（ ）。 A. S→ABb B.S→ABb
A→aA|a A→aA|a B→bB|b B→aBb | b C. S→Sb |A D.S→aAb
A→aAb |ab A→Ab|aAb|ε (12) 设有文法G[S]=（{S，B} {b}, {S→bB |b ,B→bS}, S）,该文法描述的语言是（ ）。
n
A. L(G[S])={b|n ≥0}
2n
B. L(G[S])={b |n ≥0}
2n+1
C. L(G[S])={b|n ≥0}
2n+1
D. L(G[S])={ b|n ≥1}
(13) 一个句型最左边的（ ）称为该句型的句柄。 A．短语 B.素短语 C. 直接短语 D.规范短语 (14)设有文法G[S]： E→E+T | E-T |T T→T*F |T/F|F F→(E) |i
该文法的句型E+T*F的句柄是下列符号串（ ）。
A E B E+T C T*F D E+T*F
(15) 设有文法G[T]： T→T*F |F F→F^P | P P→(T) |a
该文法的句型T*P^(T*F)的直接短语是下列符号串（ ）。
A. P B. (T*F) C. T*F D. P^(T*F) (16) 若一个文法满足（ ），则称该文法是二义文法。 A. 文法的某一个句子存在两棵（包括两棵）以上的语法树。
B. 文法的某一个句子，它有两个（包括两个）以上的最右（最左）推导。 C. 文法的某一个句子，它有两个（包括两个）以上的最右（最左）归约。 D. 文法的某一个句子存在一棵（包括一棵）以上的语法树。
(17) 在下列描述含+，*算术表达式的文法中，属于二义性文法的是（ ）。 A． E→E+E|E*E|(E)|i B.E→EAE|(E)|i
A→+|*
C. E→E+T |T D.E→EAE|T T→T*F | F T→TBF|F F→(E) |I F→(E)|i
A→+ B→* (18)乔姆斯基把文法分成4种类型，即0型、1型、2型和3型。2型文法也称为（ ）、3型文法也称为（ ）。
A.上下文无关文法 B.正规文法 C. 上下文有关文法 B.无限制文法
1、如下程序流图(图11.18)中，B3中的i∶=2是循环不变量，可以将其提到前置结点吗?你还能举出一些例子说明循环不变量外移的条件吗?
图11.18
2、2、对图11.19的流图：
(1) 求出流图中各结点n的必经结点集D(n)； (2) 求出流图中的回边； (3) 求出流图中的循环。 图11.19