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

【MOOC】形式语言与自动机理论-哈尔滨工业大学中国大学慕课MOOC答案第1章测试基础知识1、【单选题】令字母表,则克林闭包中元素的数量为？本题答案：【可数无穷个】2、【单选题】令字母表,则克林闭包中元素的长度为？本题答案：【只能是有限的】3、【单选题】集合和分别等于？本题答案：【】4、【单选题】集合和分别等于？本题答案：【】5、【单选题】令字符串集合，则和分别等于？本题答案：【】6、【单选题】令字符串集合，则和分别等于？本题答案：【】7、【判断题】字符串的长度可以是任意的，那么也可以是无穷长的。本题答案：【错误】8、【判断题】任意有穷集合的克林闭包一定是无穷集合。本题答案：【错误】9、【判断题】集合的克林闭包与正比包一定不相等本题答案：【错误】第2章测试有穷自动机1、【单选题】由字符0和1构成且长度为偶数的全部字符串的DFA，至少需要几个状态？本题答案：【2】2、【单选题】确定的有穷自动机中，“确定的”含义是：本题答案：【状态转移是确定的】3、【单选题】由字符0和1构成且含有偶数个1的DFA，至少需要几个状态？本题答案：【2】4、【单选题】由字符0和1构成且含有奇数个1的DFA，至少需要几个状态？本题答案：【2】5、【单选题】由字符0和1构成且含有奇数个1和偶数个0的DFA，至少需要几个状态？本题答案：【4】6、【单选题】如果字母表,以下哪个接受语言的DFA？本题答案：【#】7、【单选题】如果字母表,以下哪个接受语言的DFA？本题答案：【#】8、【单选题】如果字母表,以下哪个接受语言的DFA？本题答案：【】9、【单选题】如果字母表,以下哪个接受语言的DFA？本题答案：【】10、【单选题】带有空转移的非确定有穷自动机中，对于某一个状态，是否可以同时存在“对某字符a的非确定性”和“空转移”？本题答案：【可以。】11、【单选题】NFA处于某个状态q且输入某字符a时，如果状态转移函数未定义，则NFA会：本题答案：【停止自动机的运行，并拒绝该串。】12、【单选题】NFA的状态转移图如下，则其状态转移表为：本题答案：【】13、【单选题】若NFA，则其接受的语言的定义是：本题答案：【】14、【单选题】语言的NFA是以下哪一个？本题答案：【】15、【单选题】利用子集构造法，构造与NFA等价的DFA时，其中为本题答案：【】16、【单选题】利用子集构造法，构造与NFA等价的DFA时，对，为本题答案：【】17、【单选题】将如下转移图中的NFA转换为下面表格中的DFA时，表中的A处应该填入？NFA:H、I、J、K、本题答案：【】18、【单选题】所有由0和1构成的字符串，或者由01重复一次或多次，或者由010重复一次或多次构成，其NFA为？本题答案：【】19、【单选题】下图的NFA中，状态的闭包本题答案：【】20、【判断题】扩展转移函数必须从开始状态处理字符串吗?本题答案：【错误】21、【判断题】从某一个状态开始，对任意的串，经过扩展转移函数，能保证一定会跳转到某个状态吗?本题答案：【正确】22、【判断题】有穷自动机有了非确定性,增加了它识别语言的能力。本题答案：【错误】23、【判断题】有穷自动机有了空转移（不消耗输入串的状态跳转）,改变了它识别语言的能力。本题答案：【错误】24、【判断题】对同一个语言，可能存在两个不同的有穷自动机识别。本题答案：【正确】25、【判断题】两个不同的有穷自动机可能识别同一个语言。本题答案：【正确】26、【判断题】NFA处于某个状态q且输入某字符a时，状态转移函数可以未定义的情况出现。本题答案：【正确】第3章测试正则表达式1、【单选题】字母表{a,b,c}上包含至少一个a和至少一个b的串的集合，正则表达式为？本题答案：【】2、【单选题】由0和1构成的字符串中，不含101子串的全部串，正则表达式为？本题答案：【#】3、【单选题】由数量相等的0和1构成的字符串，且串的任何前缀中，0的数量不比1多2个、1的数量也不比0多2个，正则表达式为？本题答案：【】4、【单选题】正则表达式与以下哪个等价？本题答案：【】5、【单选题】正则表达式可化简为本题答案：【】6、【单选题】正则表达式=？本题答案：【】7、【单选题】由0和1构成的、至多有一对儿连续1的全部字符串，正则表达式为本题答案：【】8、【单选题】利用递归式将下表DFA转换为正则表达式时，本题答案：【#】9、【单选题】正则表达式所定义的语言为？本题答案：【由0和1构成的、没有连续1的字符串。】10、【单选题】正则表达式所定义的语言为？本题答案：【由0和1构成的、没有连续的1在0前的字符串。】11、【判断题】设是字母表上的任意语言，则语言的闭包一定是无穷的。本题答案：【错误】12、【判断题】设和是字母表上的任意语言且是无穷的，则两个语言的连接一定是无穷的。本题答案：【错误】作业1第4章测试正则语言的性质1、【单选题】有关正则语言的泵引理，以下描述正确的是：本题答案：【如果一个语言是正则的，一定符合泵引理。#无限的语言如果不符合泵引理，一定不是正则的。】2、【单选题】泵引理中与某正则语言相关的正整数，与识别该语言的DFA状态数之间的关系为？本题答案：【】3、【单选题】设同一字母表上的语言和，如果满足，那么以下描述正确的是：本题答案：【如果和都是正则的，则一定是正则的。】4、【单选题】设同一字母表上的语言和，如果满足，那么以下描述正确的是：本题答案：【如果是正则的，但不是正则的，则一定不是正则的。】5、【单选题】设同一字母表上的语言和，如果满足，那么以下描述正确的是：本题答案：【如果是正则的，不是正则的，则一定不是正则的。】6、【单选题】设同一字母表上的语言和，如果满足，那么以下描述正确的是：本题答案：【如果是正则，不是正则的，则一定不是正则的。】7、【单选题】使用泵引理证明某个语言是非正则的时候，有关该语言的正整数N是一个：本题答案：【依赖于该语言的正整数常数。】8、【单选题】使用泵引理证明某语言非正则的证明方法是：本题答案：【反证法。#归谬法。】9、【判断题】每一个有穷的语言都是正则语言。本题答案：【正确】10、【判断题】每一个无穷的语言都不是正则语言。本题答案：【错误】11、【判断题】如果语言不是正则的，则对每个都有一个DFA接受。本题答案：【正确】12、【判断题】如果语言是正则的，且，那么也是正则的。本题答案：【错误】13、【判断题】如果语言是正则的，且，那么不是正则的。本题答案：【错误】14、【判断题】如果语言是正则的，则语言也是正则的。本题答案：【正确】15、【判断题】语言不是正则语言。本题答案：【错误】第5章测试上下文无关文法1、【单选题】由文法，无法产生下面的哪个字符串？本题答案：【100001】2、【单选题】以下文法中那个是定义语言的文法。本题答案：【】3、【单选题】以下哪个，是该文法定义的语言本题答案：【#由0和1构成且至少含有一个1的字符串的集合】4、【单选题】若文法为，那么字符串的最左派生（推导）为？本题答案：【】5、【单选题】若文法为，那么字符串的语法分析树为？本题答案：【】6、【单选题】如果有产生式且变元都是可空的，那么在消除空产生式的化简中，需要增加哪些产生式才能使语言保持等价？本题答案：【】7、【判断题】文法表示语言的能力与正则表达式等价。本题答案：【错误】8、【判断题】语言是上下文无关语言。本题答案：【正确】9、【判断题】语言是正则语言。本题答案：【正确】10、【判断题】任何有限的语言都是上下文无关语言。本题答案：【正确】11、【判断题】以下文法不是歧义的。本题答案：【错误】第6章测试下推自动机1、【单选题】假设具有下列转移函数：开始，可达的ID为？本题答案：【#】2、【单选题】如果将转换为CFG，其中某一条转移函数若为则由此条转移函数得到的产生式包括：本题答案：【#】3、【单选题】接受语言的PDA为本题答案：【】4、【判断题】语言是一个DCFL。本题答案：【错误】5、【判断题】语言不是DCFL.本题答案：【正确】6、【判断题】任何正则语言都是上下文无关语言。本题答案：【正确】第7章测试上下文无关语言的性质1、【单选题】由某字母表中的字符构成的全部正则表达式的集合，也可以看做是一个语言，则该语言为