【答案】《形式语言与自动机理论》(国家高等教育智慧教育平台)章节期末中国大学慕课答案

第7章上下文无关语言的性质第7章测试上下文无关语言的性质1.单选题：由某字母表中的字符构成的全部正则表达式的集合，也可以看做是一个语言，则该语言为：

选项：

A、上下文无关语言

B、正则语言

C、

D、

答案：【上下文无关语言】2.单选题：语言是CFL.

选项：

A、正确

B、错误

答案：【正确】3.单选题：语言是CFL.

选项：

A、正确

B、错误

答案：【错误】4.单选题：如果一个CFGG的全部产生式均为或形式，其中是终结符串，那么L(G)一定是正则语言。

选项：

A、正确

B、错误

答案：【正确】5.单选题：任何有限的语言都是上下文无关语言。

选项：

A、正确

B、错误

答案：【正确】6.单选题：语言是一个DCFL.

选项：

A、正确

B、错误

答案：【错误】第8章图灵机与不可判定性第8章测试图灵机与不可判定性1.单选题：如果一个语言是不可判定的，那么它的补也一定是不可判定的

选项：

A、正确

B、错误

答案：【错误】2.单选题：递归可枚举语言是可判定的语言。

选项：

A、正确

B、错误

答案：【错误】3.单选题：图灵机是算法的好模型。

选项：

A、正确

B、错误

答案：【错误】4.单选题：确定的图灵机与非确定的图灵机等价。

选项：

A、正确

B、错误

答案：【正确】5.单选题：双栈PDA可以接受任意图灵机接受的语言。

选项：

A、正确

B、错误

答案：【正确】第1章课程简介和基础知识第1章测试基础知识1.单选题：令字母表,则克林闭包中元素的数量为？

选项：

A、有限个

B、可数无穷个

C、不可数无穷个

D、都有可能

答案：【可数无穷个】2.单选题：令字母表,则克林闭包中元素的长度为？

选项：

A、只能是有限的

B、只能是无限的

C、可能是有限的，也可能是无限的

D、可能为0，或有限长，或无限长

答案：【只能是有限的】3.单选题：令字符串集合，则和分别等于？

选项：

A、

B、

C、

D、

答案：【】4.单选题：集合和分别等于？

选项：

A、

B、

C、

D、

答案：【】5.单选题：集合和分别等于？

选项：

A、

B、

C、

D、

答案：【】6.单选题：令字符串集合，则和分别等于？

选项：

A、

B、

C、

D、

答案：【】7.单选题：任意有穷集合的克林闭包一定是无穷集合。

选项：

A、正确

B、错误

答案：【错误】8.单选题：集合的克林闭包与正比包一定不相等

选项：

A、正确

B、错误

答案：【错误】9.单选题：字符串的长度可以是任意的，那么也可以是无穷长的。

选项：

A、正确

B、错误

答案：【错误】第2章有穷自动机第2章测试有穷自动机1.单选题：NFA处于某个状态q且输入某字符a时，如果状态转移函数未定义，则NFA会：

选项：

A、跳过该输入字符，继续运行。

B、停止自动机的运行，是否接受该字符串，由当前状态是否为终态决定。

C、停止自动机的运行，并接受该串。

D、停止自动机的运行，并拒绝该串。

答案：【停止自动机的运行，并拒绝该串。】2.单选题：NFA的状态转移图如下，则其状态转移表为：

选项：

A、

B、

C、

D、

答案：【】3.单选题：若NFA，则其接受的语言的定义是：

选项：

A、

B、

C、

D、

答案：【】4.单选题：语言的NFA是以下哪一个？

选项：

A、

B、

C、

D、

答案：【】5.单选题：如果字母表,以下哪个接受语言的DFA？

选项：

A、

B、

C、

D、

E、

答案：【】6.单选题：如果字母表,以下哪个接受语言的DFA？

选项：

A、

B、

C、

D、

E、

答案：【】7.单选题：如果字母表,以下哪个接受语言的DFA？

选项：

A、

B、

C、

D、

E、

答案：【】8.单选题：带有空转移的非确定有穷自动机中，对于某一个状态，是否可以同时存在“对某字符a的非确定性”和“空转移”？

选项：

A、可以。

B、不可以。

C、有空转移时可以有对某个字符a的非确定性，但反之不可以。

D、对某个字符a有非确定性时可以有空转移，但反之不可以。

答案：【可以。】9.单选题：下图的NFA中，状态的闭包

选项：

A、

B、

C、

D、

答案：【】10.单选题：利用子集构造法，构造与NFA等价的DFA时，其中为

选项：

A、

B、

C、

D、

答案：【】11.单选题：利用子集构造法，构造与NFA等价的DFA时，对，为

选项：

A、

B、

C、

D、

答案：【】12.单选题：将如下转移图中的NFA转换为下面表格中的DFA时，表中的A处应该填入？NFA:DFA:

选项：

A、

B、

C、

D、

E、

F、

G、

H、

I、

J、

K、

答案：【】13.单选题：所有由0和1构成的字符串，或者由01重复一次或多次，或者由010重复一次或多次构成，其NFA为？

选项：

A、

B、

C、

D、

答案：【】14.单选题：由字符0和1构成且含有偶数个1的DFA，至少需要几个状态？

选项：

A、2

B、3

C、1

D、4

答案：【2】15.单选题：由字符0和1构成且含有奇数个1的DFA，至少需要几个状态？

选项：

A、2

B、1

C、3

D、4

答案：【2】16.单选题：由字符0和1构成且含有奇数个1和偶数个0的DFA，至少需要几个状态？

选项：

A、1

B、2

C、3

D、4

答案：【4】17.单选题：如果字母表,以下哪个接受语言的DFA？

选项：

A、

B、

C、

D、

E、

答案：【】18.单选题：由字符0和1构成且长度为偶数的全部字符串的DFA，至少需要几个状态？

选项：

A、2

B、1

C、3

D、0

答案：【2】19.单选题：确定的有穷自动机中，“确定的”含义是：

选项：

A、状态转移是确定的

B、输入字符是确定的

C、状态是确定的

D、语言是确定的

答案：【状态转移是确定的】20.单选题：从某一个状态开始，对任意的串，经过扩展转移函数，能保证一定会跳转到某个状态吗?

选项：

A、正确

B、错误

答案：【正确】21.单选题：有穷自动机有了非确定性,增加了它识别语言的能力。

选项：

A、正确

B、错误

答案：【错误】22.单选题：有穷自动机有了空转移（不消耗输入串的状态跳转）,改变了它识别语言的能力。

选项：

A、正确

B、错误

答案：【错误】23.单选题：对同一个语言，可能存在两个不同的有穷自动机识别。

选项：

A、正确

B、错误

答案：【正确】24.单选题：扩展转移函数必须从开始状态处理字符串吗?

选项：

A、正确

B、错误

答案：【错误】25.单选题：两个不同的有穷自动机可能识别同一个语言。

选项：

A、正确

B、错误

答案：【正确】26.单选题：NFA处于某个状态q且输入某字符a时，状态转移函数可以未定义的情况出现。

选项：

A、正确

B、错误

答案：【正确】第3章正则表达式第3章测试正则表达式1.单选题：字母表{a,b,c}上包含至少一个a和至少一个b的串的集合，正则表达式为？

选项：

A、

B、

C、

D、

答案：【】2.单选题：由0和1构成的字符串中，不含101子串的全部串，正则表达式为？

选项：

A、

B、

C、

D、

E、

F、

答案：【】3.单选题：由数量相等的0和1构成的字符串，且串的任何前缀中，0的数量不比1多2个、1的数量也不比0多2个，正则表达式为？

选项：

A、

B、

C、

D、

答案：【】4.单选题：利用递归式将下表DFA转换为正则表达式时，

选项：

A、

B、

C、

D、

E、

F、

答案：【】5.单选题：正则表达式所定义的语言为？

选项：

A、由0和1构成的、没有连续1的字符串。

B、由0和1构成的、不以0开头的字符串。

C、由0和1构成的、由01和0构成的字符串。

D、由0和1构成的、以0结尾的字符串。

答案：【由0和1构成的、没有连续1的字符串。】6.单选题：正则表达式所定义的语言为？

选项：

A、由0和1构成的、没有连续的1在0前的字符串。

B、由0和1构成的、只能以1结尾的字符串。

C、由0和1构成的、没有连续1的字符串。

D、由0和1构成的、不以1开头的字符串。

答案：【由0和1构成的、没有连续的1在0前的字符串。】7.单选题：正则表达式与以下哪个等价？

选项：

A、

B、

C、

D、

答案：【】8.单选题：正则表达式可化简为

选项：

A、

B、

C、

D、

答案：【】9.单选题：正则表达式=？

选项：

A、

B、

C、

D、

答案：【】10.单选题：由0和1构成的、至多有一对儿连续1的全部字符串，正则表达式为

选项：

A、

B、

C、

D、

答案：【】11.单选题：设和是字母表上的任意语言且是无穷的，则两个语言的连接一定是无穷的。

选项：

A、正确

B、错误

答案：【错误】12.单选题：设是字母表上的任意语言，则语言的闭包一定是无穷的。

选项：

A、正确

B、错误

答案：【错误】第4章正则语言的性质第4章测试正则语言的性质1.单选题：有关正则语言的泵引理，以下描述正确的是：

选项：

A、如果一个语言是正则的，一定符合泵引理。

B、如果一个语言符合泵引理，一定是正则的。

C、有限的语言一定是正则的，但不符合泵引理。

D、无限的语言如果符合泵引理，一定是正则的。

E、无限的语言如果不符合泵引理，一定不是正则的。

F、无限的语言如果不符合泵引理，一定是正则的。

答案：【如果一个语言是正则的，一定符合泵引理。】2.单选题：泵引理中与某正则语言相关的正整数，与识别该语言的DFA状态数之间的关系为？

选项：

A、

B、

C、

D、无关

答案：【】3.单选题：设同一字母表上的语言和，如果满足，那么以下描述正确的是：

选项：

A、如果是正则的，则一定是正则的。

B、如果和都是正则的，则一定是正则的。

C、如果和都是正则的，则一定是正则的。

D、如果是正则的，则和至少有一个是正则的。

答案：【如果和都是正则的，则一定是正则的。】4.单选题：使用泵引理证明某语言非正则的证明方法是：

选项：

A、反证法。

B、归纳法。

C、演绎法。

D、赋值法。

E、归谬法。

答案：【反证法。】5.单选题：设同一字母表上的语言和，如果满足，那么以下描述正确的是：

选项：

A、如果和都不是正则的，则一定不是正则的。

B、如果是正则的，但不是正则的，则一定不是正则的。

C、如果不是正则的，则和一定都不是正则的。

D、如果是正则的，不是正则的，则一定不可能正则的。

答案：【如果是正则的，但不是正则的，则一定不是正则的。】6.单选题：设同一字母表上的语言和，如果满足，那么以下描述正确的是：

选项：

A、如果和都不是正则的，则一定不是正则的。

B、如果和都不是正则的，则一定不是正则的。

C、如果是正则的，不是正则的，则一定不是正则的。

D、如果不是正则的，是正则的，则一定是正则的。

答案：【如果是正则的，不是正则的，则一定不是正则的。】7.单选题：设同一字母表上的语言和，如果满足，那么以下描述正确的是：

选项：

A、如果不是正则的，是正则的，则一定不是正则的。

B、如果不是正则的，是正则的，则一定是正则的

C、如果和都不是正则的，则一定不是正则语言。

D、如果是正则，不是正则的，则一定不是正则的。

E、如果不是正则的，是正则的，则一定是正则的。

答案：【如果是正则，不是正则的，则一定不是正则的。】8.单选题：使用泵引理证明某个语言是非正则的时候，有关该语言的正整数N是一个：

选项：

A、依赖于该语言的正整数常数。

B、与该语言无关的正整数常数。

C、依赖于该语言且大于特定值的变量。

D、与该语言无关且大于特定值的变量。

答案：【依赖于该语言的正整数常数。】9.单选题：语言不是正则语言。

选项：

A、正确

B、错误

答案：【错误】10.单选题：如果语言不是正则的，则对每个都有一个DFA接受。

选项：

A、正确

B、错误

答案：【正确】11.单选题：如果语言是正则的，且，那么也是正则的。

选项：

A、正确

B、错误

答案：【错误】12.单选题：如果语言是正则的，且，那么不是正则的。

选项：

A、正确

B、错误

答案：【错误】13.单选题：如果语言是正则的，则语言也是正则的。

选项：

A、正确

B、错误

答案：【正确】14.单选题：每一个有穷的语言都是正则语言。

选项：

A、正确

B、错误

答案：【正确】15.单选题：每一个无穷的语言都不是正则语言。

选项：

A、正确

B、错误

答案：【错误】第5章上下文无关文法第5章上下文无关语言1.单选题：以下哪个，是该文法定义的语言

选项：

A、

B、由0和1构成且至少含有一个1的字符串的集合

C、由0和1构成且必须以0开头的字符串的集合

D、

E、

答案：【】2.单选题：若文法为，那么字符串的最左派生（推导）为？

选项：

A、

B、

C、

D、

答案：【】3.单选题：若文法为，那么字符串的语法分析树为？

选项：

A、

B、

C、

D、

答案：【】4.单选题：如果有产生式且变元都是可空的，那么在消除空产生式的化简中，需要增加哪些产生式才能使语言保持等价？

选项：

A、

B、

C、

D、

答案：【】5.单选题：由文法，无法产生下面的哪个字符串？

选项：

A、100001

B、010010

C、110001000

D、001010100

答案：【100001】6.单选题：以下文法中那个是定义语言的文法。

选项：

A、

B、

C、

D、

答案：【】7.单选题：文法表示语言的能力与正则表达式等价。

选项：

A、正确

B、错误

答案：【错误】8.单选题：语言是上下文无关语言。

选项：

A、正确

B、错误

答案：【正确】9.单选题：语言是正则语言。

选项：

A、正确

B、错误

答案：【正确】10.单选题：任何有限的语言都是上下文无关语言。

选项：

A、正确

B、错误

答案：【正确】11.单选题：以下文法不是歧义的。

选项：

A、正确

B、错误

答案：【错误】第6章下推自动机第6章测试下推自动机1.单选题：假设具有下列转移函数：那么，当输入串01时，从初始ID开始，可达的ID为？

选项：

A、

B、

C、

D、

E、

F、

答案：【】2.单选题：如果将转换为CFG，其中某一条转移函数若为则由此条转移函数得到的产生式包括：

选项：

A、

B、

C、

D、

E、

F、

G、

答案：【】3.单选题：接受语言的PDA为

选项：

A、

B、

C、

D、

答案：【】4.单选题：语言是一个DCFL。

选项：

A、正确

B、错误

答案：【错误】5.单选题：语言不是DCFL.

选项：

A、正确

B、错误

答案：【正确】6.单选题：任何正则语言都是上下文无关语言。

选项：

A、正确

B、错误

答案：【正确】期末考试期末考试1.单选题：由字符0和1构成且含有偶数个1的DFA，至少需要几个状态？

选项：

A、2

B、3

C、1

D、4

答案：【2】2.单选题：利用子集构造法，构造与NFA等价的DFA时，对，为

选项：

A、

B、

C、

D、

答案：【】3.单选题