大学MOOC 离散数学概论(内蒙古工业大学)1453172175 最新慕课完整章节测试答案
10 抽象代数
文章目录
单元10测验
1、单选题：
设
是代数系统，*是X上的二元运算，R是X上的等价关系。若
当
且
时，有
，则称R是X上关于*的同余关系，称R产生的等价类是关于*的同余类。考察代数系统
，
是整数集合，
是整数加法。问以下的二元关系是上的关于的同余关系个数是？
a) 
b) 
c) 
d) 
选项：
A: 0
B: 1
C: 2
D: 3
答案: 【 0】
2、多选题：
设I为整数集合。选出下列是I上的二元运算的二元关系
选项：
A: 
B: 
C: 
D: 
E: 
F: 
G: 
H: 
I: 
答案: 【 ;;;;;;】
3、填空题：
设
，A上的二元运算*定义为：
，则在代数结构
中，幺元是( )，零元是( )。(注：答案之间用英文逗号,分开)
答案: 【 2,6】
4、填空题：
设
，A上的二元运算*定义为：
，则在代数结构中，幺元是( )，零元是( )；(注：答案之间用英文逗号,分开)
答案: 【 9,3】
5、填空题：
设
是代数系统，*是X上的二元运算。
。问*是否满足结合律，是否满足交换律，是否有幺元，是否有零元，每个元素是否有逆元。
只回答是否，5个判断中间用“/”隔开
答案: 【 是/否/否/否/否】
6、填空题：
设是代数系统，*是X上的二元运算，e是关于*的幺元。对于X中的元素x，若存在
，使得
，则称y是x的左逆元。若存在
，使得
，则称z是x的右逆元。指出下表中各元素的左、右逆元的情况。表格（取变量方法是先纵后横）幺元是____，有两个左逆元和两个右逆元的是____，没有左逆元的是____(注：答案之间用英文逗号,分开)
答案: 【 a,c,e】
7、填空题：
设
是补运算。问X和Y是否同构，如果是，回答是；如果否，则因为__结构的__运算不符合相关要求
填字母、汉字(注：答案之间用英文逗号,分开，并且注意大小写)
答案: 【 Y,补】
11 形式语言与自动机基本概念
单元11测验
1、单选题：
设一个短语结构语法是G=({A}，{a}，{A→a|aA}，A)，那么下面不是它产生的语句个数是
(1)aaaaaaaaaa (2)aaaaaaAaaa (3)AaAaaAaAA (4)aaAaaAaaa
本次测验采用的语法定义如图
其他题目相同
选项：
A: 3
B: 1
C: 2
D: 4
答案: 【 3】
2、单选题：
对下面文法的生成式，找出其正则式G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下：S→aA S→BA→abS A→bBB→b B→cCC→D D→bBD→d
选项：
A: (aab)*(ab|ε)(cb)*(cd|b)
B: (aab)*(ab|ε)*(cb)*(cd|b)
C: (aab)*(ab|ε)(cb)(cd|b)
D: (aab)*(ab|ε)(cb)*(cd|b)*
答案: 【 (aab)*(ab|ε)(cb)*(cd|b)】
3、单选题：
对下面文法的生成式，找出其正则式G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下：S→aA S→BA→cC A→bBB→bB B→aC→D C→abBD→d
选项：
A: ab+a|acd|acab+a|b*a
B: ab*a|acd|acab+a|b*a
C: ab*a|acd|acab*a|b*a
D: ab+a|acd|acab+a|b+a
答案: 【 ab+a|acd|acab+a|b*a】
4、单选题：
设文法G有如下产生式 S→aB│bA；A→a│aS│bAA；B→b│bS│aBB；则L(G)的内容是____
选项：
A: L(G)＝{ω│ω中含有相同个数的a和b，且ω非空}。
B: L = {anbmam|n,m≥1}
C: L = {anbnan|n≥1}
D: 其他选项皆不正确
答案: 【 L(G)＝{ω│ω中含有相同个数的a和b，且ω非空}。】
5、单选题：
对下面文法，他的产生语言是G = ({S, A, B, C}, { a, b, c}, P, S)其中P:{S→aBC | aSBC，CB→BC ，aB→ab，bB→bb，bC→bc，cC→cc}
选项：
A: L = {anbncn | n≥1}
B: L = {anbmcm|n,m≥1}
C: L = {anbmck|n,m,k≥1}
D: 其他选项皆不正确
答案: 【 L = {anbncn | n≥1}】
6、单选题：
对下面文法G=（{S, A}，{a, b}，{S→ABA, A→Aa|a, B→bB|b}，S），产生的语言是
选项：
A: L = {anbmak|n,m,k≥1}
B: L = {anbmam|n,m≥1}
C: L = {anbnan|n≥1}
D: 其他选项皆不正确
答案: 【 L = {anbmak|n,m,k≥1}】
12 形式语言与自动机-有限状态机
单元12测验
1、单选题：
利用泵引理，判断下列属于RL语言的个数是_____{0n1n|n≥1}{0n|n为素数}{0n1m2m+n|m,n≥1}
选项：
A: 0
B: 1
C: 2
D: 无法确定
答案: 【 0】
2、单选题：
考虑两个机器如图，给出它们的形式描述分别是（从左到右）___________
PS：你们想要的target标签已经加上，妈妈再也不用担心手贱了……
选项：
A: [01+(00+1)(11+0)][11+(10+0)(11+0)]*(01+1+000){(01)*+[(001+11)(01+1+000)]*}
B: (01+1+000){(01)*+[(001+11)(01+1+000)]*}[01+(00+1)(11+0)][11+(10+0)(11+0)]*
C: [11+(10+0)(11+0)]*{(01)*+[(001+11)(01+1+000)]*}
D: 其余答案皆不正确
答案: 【 [01+(00+1)(11+0)][11+(10+0)(11+0)]*(01+1+000){(01)*+[(001+11)(01+1+000)]*}】
3、单选题：
如下状态图，关于他的语法含义正确的是____
PS：这类题目真正掌握应该是给定语法，自行设计状态图
选项：
A: {x|x∈{0，1}+且x的第十个字符为1}
B: {x|x∈{0，1}+且x的第十个字符为0}
C: 一旦第九、十字符分别为10 则进入陷阱状态
D: 毫无陷阱状态，因为陷阱也要按照基本Fa
答案: 【 {x|x∈{0，1}+且x的第十个字符为1}】
4、单选题：
如下状态图，关于他的语法含义正确的是____
PS：这类题目真正掌握应该是给定语法，自行设计状态图
选项：
A: {x|x∈{0，1}+且如果x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度为奇数}
B: {x|x∈{0，1}*且如果x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度为奇数}
C: {x|x∈{0，1}+且如果x以0结尾，则它的长度为偶数；如果x以1结尾，则它的长度为奇数}
D: {x|x∈{0，1}*且如果x以0结尾，则它的长度为偶数；如果x以1结尾，则它的长度为奇数}
答案: 【 {x|x∈{0，1}+且如果x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度为奇数}】
5、单选题：
识别状态图的语言，正确的是____
PS：这是不确定的有穷状态自动机(non-deterministic finite automaton ,NFA)，稍微区别于确定的有穷状态自动机(deterministic finite automaton，DFA) ，但都是有穷状态自动机(finite automaton,FA)
选项：
A: {x|x∈{0, 1}+且x的首尾字符相等}
B: {x|x∈{0, 1}*且x的首尾字符相等}
C: {x|x∈{0, 1}+且x的首尾字符不相等}
D: {x|x∈{0, 1}*且x的首尾字符不相等}
答案: 【 {x|x∈{0, 1}+且x的首尾字符相等}】
13 形式语言与自动机-图灵机与计算理论
单元13测试
1、单选题：
关于“图灵机”，下列说法不正确的个数是_____图灵机给出的是计算机的理论模型；图灵机的状态转移函数q, X, Y, R(或L或N), p，其实就是一条指令，即在q状态下，当输入为X时，输出为Y，读写头向右(R)、向左(L)移动一格或不动(N)，状态变为p；图灵机是一种离散的、有穷的、构造性的问题求解思路；凡是能用算法方法解决的问题也一定能用图灵机解决；凡是图灵机解决不了的问题算法也解决不了；
选项：
A: 0
B: 1
C: 2
D: 3
答案: 【 0】
2、单选题：
下图为用状态转换图示意的一个图灵机，其字母集合为{0,1,X,Y,B}，其中B为空白字符；状态集合{S1，S2，S3，S4，S5}，其中S1为起始状态，S5为终止状态；箭头表示状态转换，其上标注的如in, out, direction表示输入是in时，输出out，向direction方向移动一格，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，direction可以为R(向右移动)、L(向左移动)、N(停留在原处)。
该图灵机的功能是_