2012秋第一次在线作业
试卷总分：100
单选题 判断题
一、单选题（共 20 道试题，共 60 分。）
1.设有文法G[T]：T::=T*F|F，F::=F↑P|P，P::=(T)|a，下列符号串中是该文法句型T*P↑(T*F)的直接短语是哪个()。
A. (T*F)
B. T*F
C. P↑
D. P↑(T*F)
2.对于状态转换图中用矢线连接的任意两个结点，把靠箭尾一侧的结点称为该矢线的什么结点()。
A. 进入
B. 射出
C. 初态
D. 终态
3.语言L={ambn|m≥0，n≥1}的正规表达式是什么()。
A. a*bb*
B. aa*bb*
C. aa*b*
D. a*b*
4.下述正规表达式中，能描述字母表｛0，1｝上所有长度不为3的符号串的是哪个()。
A. (ε|0|1|00|11|10|01)((0|1)(0|1)*)
B. ε|0|1(00|11|10|01)*
C. ε|0|1(00|11|10|01)(0|1)*
D. 没有一个
此题选: D
5.通常把每个非终结符号的右部符号串称为该非终结符号的什么()。
A. 推导项
B. 选择式
C. 规则项
D. 候选式
此题选: D
6.所谓NFA的确定化，是指对任给的NFA，都能相应地构造一DFA，使它们有相同的什么()。
A. 状态集
B. 符号集
C. 接受集
D. 结点集
7.编译程序已成为现今任何计算机系统的最重要的什么之一()。
A. 系统程序
B. 应用程序
C. 支撑程序
D. 自动化程序
8.不属于编译程序组成部分的是什么()。
A. 词法分析程序
B. 代码生成程序
C. 设备管理程序
D. 语法分析程序
9.词法分析时，单词的识别依据什么来实现()。
A. 下推自动机
B. 图灵机
C. 状态转换图
D. 抽象机
10.词法分析器用于识别什么()。
A. 句柄
B. 句型
C. 单词
D. 产生式
11.设有文法G[S]：S→SaT|T，T→TbR|R，R→PdR|P，P→fSｇ|e，考察该文法的句型SaTbfSgde，其中哪个是句柄()。
A. SaT
B. b
C. fSg
D. e
12.一个文法所描述的语言是什么样的()。
A. 唯一的
B. 不唯一的
C. 可能唯一
D. 可能不唯一
13.Chmosky的3型语言是这样一种语言，其产生式限制为什么()。
A. A::=α
B. A::=a,A::=Ab
C. α::=β
D. αAβ::=απβ
14.设有文法G[S]：S→aTS|b|(T)，T→TSd|a，则该文法的右句型是哪个()。
A. aT(T)
B. aTaaS
C. aT(T)dS
D. aTSdS
15.Σ={0，1}上的正规式(0|1)*表示什么()。
A. 0开头的串
B. 1开头的串
C. 有一个0和一个1的串
D. 由0、1组成的任意串
此题选: D
16.设有文法G[S]：S::=S*S|S+S|(S)|a，该文法是否是二义性文法()。
A. 是
B. 不是
C. 可能是
D. 无法判断
17.在语法分析处理中，FIRST集合、FOLLOW集合均是什么样的集合()。
A. 非终极符集
B. 终极符集
C. 字母表
D. 状态集
18.产生式是用于定义什么的一种书写规则()。
A. 语法范畴
B. 推导
C. 句柄
D. 短语
19.在一个规范句型中，位于句柄右边的符号(如果有的话)必然是什么()。
A. 非终结符号
B. 终结符号
C. 开始符号
D. 空符号串
20.存在这样的前后文无关语言，用来定义该语言的一切文法都是二义性的。通常把这样的语言称为什么()。
A. 自然二义性语言
B. 纯粹二义性语言
C. 前后文二义性语言
D. 先天二义性语言
此题选: D
2012秋第一次在线作业
试卷总分：100
单选题 判断题
二、判断题（共 20 道试题，共 40 分。）
1.若在一个右线性文法中含有多个右部相同的产生式，则由该文法构造的状态转换图一定是NFA。
A. 错误
B. 正确
2.语法树的根结点以文法的非终结符号标记。
A. 错误
B. 正确
3.一个二义性文法所描述的语言不是唯一的。
A. 错误
B. 正确
4.对于一个语言来说，如何对其单词进行分类和编码并没有一个原则性的规定，而主要取决于处理上的方便。
A. 错误
B. 正确
5.若一个文法G含有既是左递归亦是右递归的非终结符号，则G必定是无二义性文法。
A. 错误
B. 正确
6.编译程序的特点是先将高级语言程序翻译成机器语言程序，即先翻译、后执行。
A. 错误
B. 正确
7.已经证明文法的二义性是可判定的。
A. 错误
B. 正确
8.根据文法等价的概念，可对文法进行等价改造，以期得到所需形式的文法。
A. 错误
B. 正确
9.若消除文法中的ε-产生式，将会改变文法所定义的语言，故不能消除ε-产生式。
A. 错误
B. 正确
10.一个字母表上全部符号串所组成的集合必然为一有限集。
A. 错误
B. 正确
11.一个仅能处理绝对正确源程序的编译程序才具有实用价值。
A. 错误
B. 正确
12.存在既不是左句型也不是右句型的句型。
A. 错误
B. 正确
13.二义性是一种常见的现象。
A. 错误
B. 正确
14.文法G的一个句子对应于多个推导,则G是二义的。
A. 错误
B. 正确
15.有时若干个在外形上颇不相同的正规式可描述同一正规集。
A. 错误
B. 正确
16.文法的二义性和语言的二义性是两个不同的概念。
A. 错误
B. 正确
17.高级语言程序必须经过编译程序的翻译才能被计算机识别和执行。
A. 错误
B. 正确
18.字母表A的自反传递闭包就是A上所有符号串所组成的集合。
A. 错误
B. 正确
19.若G是已化简的文法，则G中的每一符号X都能推出非终结符号串来。
A. 错误
B. 正确
20.对任何正规表达式e，都存在一个DFA M，满足L(M)=L(e)。
A. 错误
B. 正确
版权声明
声明：有的资源均来自网络转载，版权归原作者所有，如有侵犯到您的权益
请联系本站我们将配合处理！