MOOC 形式语言与自动机理论-哈尔滨工业大学 中国大学慕课答案

MOOC形式语言与自动机理论-哈尔滨工业大学中国大学慕课答案第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章测试有穷自动机1、问题：由字符0和1构成且长度为偶数的全部字符串的DFA，至少需要几个状态？选项：A、2B、1C、3D、0正确答案:【2】2、问题：确定的有穷自动机中，“确定的”含义是：选项：A、状态转移是确定的B、输入字符是确定的C、状态是确定的D、语言是确定的正确答案:【状态转移是确定的】3、问题：由字符0和1构成且含有偶数个1的DFA，至少需要几个状态？选项：A、2B、3C、1D、4正确答案:【2】4、问题：由字符0和1构成且含有奇数个1的DFA，至少需要几个状态？选项：A、2B、1C、3D、4正确答案:【2】5、问题：由字符0和1构成且含有奇数个1和偶数个0的DFA，至少需要几个状态？选项：A、1B、2C、3D、4正确答案:【4】6、问题：如果字母表选项：,以下哪个接受语言的DFA？A、B、C、D、E、正确答案:【#】7、问题：如果字母表选项：,以下哪个接受语言的DFA？A、B、C、D、E、正确答案:【#】8、问题：如果字母表选项：,以下哪个接受语言的DFA？A、B、C、D、E、正确答案:【】9、问题：如果字母表选项：,以下哪个接受语言的DFA？A、B、C、D、E、正确答案:【】10、问题：带有空转移的非确定有穷自动机中，对于某一个状态，是否可以同时存在“对某字符a的非确定性”和“空转移”？选项：A、可以。B、不可以。C、有空转移时可以有对某个字符a的非确定性，但反之不可以。D、对某个字符a有非确定性时可以有空转移，但反之不可以。正确答案:【可以。】11、问题：NFA处于某个状态q且输入某字符a时，如果状态转移函数未定义，则NFA会：选项：A、跳过该输入字符，继续运行。B、停止自动机的运行，是否接受该字符串，由当前状态是否为终态决定。C、停止自动机的运行，并接受该串。D、停止自动机的运行，并拒绝该串。正确答案:【停止自动机的运行，并拒绝该串。】12、问题：NFA的状态转移图如下，则其状态转移表为：选项：A、B、C、D、正确答案:【】13、问题：若NFA选项：，则其接受的语言的定义是：A、B、C、D、正确答案:【】14、问题：语言是以下哪一个？选项：的NFAA、B、C、D、正确答案:【】15、问题：利用子集构造法，构造与NFA等价的DFA时，其中为选项：A、B、C、D、正确答案:【】16、问题：利用子集构造法，构造与NFA等价的DFA时，对，为选项：A、B、C、D、正确答案:【】17、问题：将如下转移图中的NFA转换为下面表格中的DFA时，表中的A处应该填入？NFA:选项：A、B、C、D、E、F、G、H、I、J、K、正确答案:【】18、问题：所有由0和1构成的字符串，或者由01重复一次或多次，或者由010重复一次或多次构成，其NFA为？选项：A、B、C、D、正确答案:【】19、问题：下图的NFA中，状态的闭包选项：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章测试正则表达式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、问题：正则表达式选项：与以下哪个等价？A、B、C、D、正确答案:【】5、问题：正则表达式选项：可化简为A、B、C、D、正确答案:【】6、问题：正则表达式选项：=？A、B、C、D、正确答案:【】7、问题：由0和1构成的、至多有一对儿连续1的全部字符串，正则表达式为选项：A、B、C、D、正确答案:【】8、问题：利用递归式将下表DFA转换为正则表达式时，选项：A、B、C、D、E、F、正确答案:【#】9、问题：正则表达式选项：所定义的语言为？A、由0和1构成的、没有连续1的字符串。B、由0和1构成的、不以0开头的字符串。C、由0和1构成的、由01和0构成的字符串。D、由0和1构成的、以0结尾的字符串。正确答案:【由0和1构成的、没有连续1的字符串。】10、问题：正则表达式选项：所定义的语言为？A、由0和1构成的、没有连续的1在0前的字符串。B、由0和1构成的、只能以1结尾的字符串。C、由0和1构成的、没有连续1的字符串。D、由0和1构成的、不以1开头的字符串。正确答案:【由0和1构成的、没有连续的1在0前的字符串。】11、问题：设是字母表上的任意语言，则语言的闭包一定是无穷的。选项：A、正确B、错误正确答案:【错误】12、问题：设和是字母表上的任意语言且是无穷的，则两个语言的连接一定是无穷的。选项：A、正确B、错误正确答案:【错误】作业1第4章测试正则语言的性质1、问题：有关正则语言的泵引理，以下描述正确的是：选项：A、如果一个语言是正则的，一定符合泵引理。B、如果一个语言符合泵引理，一定是正则的。C、有限的语言一定是正则的，但不符合泵引理。D、无限的语言如果符合泵引理，一定是正则的。E、无限的语言如果不符合泵引理，一定不是正则的。F、无限的语言如果不符合泵引理，一定是正则的。正确答案:【如果一个语言是正则的，一定符合泵引理。#无限的语言如果不符合泵引理，一定不是正则的。】2、问题：泵引理中与某正则语言相关的正整数，与识别该语言的DFA状态数之间的关系为？选项：A、B、C、D、无关正确答案:【】3、问题：设同一字母表上的语言述正确的是：选项：和，如果满足，那么以下描A、如果是正则的，则一定是正则的。B、如果和都是正则的，则一定是正则的。C、如果和都是正则的，则一定是正则的。D、如果是正则的，则和至少有一个是正则的。正确答案:【如果和都是正则的，则一定是正则的。】4、问题：设同一字母表上的语言述正确的是：选项：和，如果满足，那么以下描A、如果和都不是正则的，则一定不是正则的。B、如果是正则的，但不是正则的，则一定不是正则的。C、如果不是正则的，则和一定都不是正则的。D、如果是正则的，不是正则的，则一定不可能正则的。正确答案:【如果是正则的，但不是正则的，则一定不是正则的。】5、问题：设同一字母表上的语言述正确的是：选项：和，如果满足，那么以下描A、如果和都不是正则的，则一定不是正则的。B、如果和都不是正则的，则一定不是正则的。C、如果是正则的，不是正则的，则一定不是正则的。D、如果不是正则的，是正则的，则一定是正则的。正确答案:【如果是正则的，不是正则的，则一定不是正则的。】6、问题：设同一字母表上的语言和，如果满足，那么以下描述正确的是：选项：A、如果不是正则的，是正则的，则一定不是正则的。B、如果不是正则的，是正则的，则一定是正则的C、如果和都不是正则的，则一定不是正则语言。D、如果是正则，不是正则的，则一定不是正则的。E、如果不是正则的，是正则的，则一定是正则的。正确答案:【如果是正则，不是正则的，则一定不是正则的。】7、问题：使用泵引理证明某个语言是非正则的时候，有关该语言的正整数N是一个：选项：A、依赖于该语言的正整数常数。B、与该语言无关的正整数常数。C、依赖于该语言且大于特定值的变量。D、与该语言无关且大于特定值的变量。正确答案:【依赖于该语言的正整数常数。】8、问题：使用泵引理证明某语言非正则的证明方法是：选项：A、反证法。B、归纳法。C、演绎法。D、赋值法。E、归谬法。正确答案:【反证法。#归谬法。】9、问题：每一个有穷的语言都是正则语言。选项：A、正确B、错误正确答案:【正确】10、问题：每一个无穷的语言都不是正则语言。选项：A、正确B、错误正确答案:【错误】11、问题：如果语言不是正则的，则对每个选项：都有一个DFA接受。，那么也是正则的。，那么不是正则的。A、正确B、错误正确答案:【正确】12、问题：如果语言是正则的，且选项：A、正确B、错误正确答案:【错误】13、问题：如果语言是正则的，且选项：A、正确B、错误正确答案:【错误】14、问题：如果语言是正则的，则语言选项：也是正则的。A、正确B、错误正确答案:【正确】15、问题：语言选项：不是正则语言。A、正确B、错误正确答案:【错误】第5章测试上下文无关文法1、问题：由文法？选项：，无法产生下面的哪个字符串A、100001B、010010C、110001000D、001010100正确答案:【100001】2、问题：以下文法中那个是定义语言选项：的文法。A、B、C、D、正确答案:【】3、问题：以下哪个，是该文法定义的语言选项：A、B、由0和1构成且至少含有一个1的字符串的集合C、由0和1构成且必须以0开头的字符串的集合D、E、正确答案:【#由0和1构成且至少含有一个1的字符串的集合】4、问题：若文法为的最左派生（推导）为？选项：，那么字符串A、B、C、D、正确答案:【】5、问题：若文法为选项：，那么字符串的语法分析树为？A、B、C、D、正确答案:【】6、问题：如果有产生式且变元都是可空的，那么在消除空产生式的化简中，需要增加哪些产生式才能使语言保持等价？选项：A、B、C、D、正确答案:【】7、问题：文法表示语言的能力与正则表达式等价。选项：A、正确B、错误正确答案:【错误】8、问题：语言选项：是上下文无关语言。A、正确B、错误正确答案:【正确】9、问题：语言选项：是正则语言。A、正确B、错误正确答案:【正确】10、问题：任何有限的语言都是上下文无关语言。选项：A、正确B、错误正确答案:【正确】11、问题：以下文法不是歧义的。选项：A、正确B、错误正确答案:【错误】第6章测试下推自动机1、问题：假设具有下列转移函数：的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、错误正确答案:【正确】第7章测试上下文无关语言的性质1、问题：由某字母表中的字符构