正规式和正规集之间是否有一一对应的关系()。A、存在B、不存在C、描述D、无法确定
题目
正规式和正规集之间是否有一一对应的关系()。
A、存在
B、不存在
C、描述
D、无法确定
相似考题
更多“正规式和正规集之间是否有一一对应的关系()。A、存在B、不存在C、描述D、无法确定 ”相关问题
-
第1题：
两个正规式等价，当且仅当它们所描述的正规集相同。()
参考答案：正确
-
第2题：
对于以下编号为①、②、③的正规式，正确的说法是(35)。
①(aa*|ab)*b
②(a|b)*b
③((a|b)*|aa)*b
A．正规式①、②等价
B．正规式①、③等价
C．正规式②、③等价
D．正规式①、②、③互不等价
正确答案：C
解析：根据正规式r和s的意义，两个正规式等价说明，和s代表的字符串集合相同，因此可用证明集合相等的方法判断。另外，也可构造出与每个正规式对应的自动机进行说明。但是这两个方法实施起来都很繁琐，因此可根据正规式的含义及其代数性质进行判断。由于题目中给出的正规式①、②和③的共同之处是以字符b结尾，所以只需考虑(aa*|ab)*、(a|b)*和((a|b)*|aa)*之间的等价关系。从直观的角度理解，正规式(aa*|ab)*表示的是包含空串ε以及a开头的且每个b之后必然出现a的字符串的集合，而(a|b)*表示包含空串ε在内的所有a、b构成的字符串集合，并不限制b的出现方式，正规式((a|b)*|aa)*表示的字符串也不具有必须以a开头的特点，因此，正规式①与②、③的等价关系即可排除。至于(a|b)*和((a|b)*|aa)*，很明显正规式((a|b)*|aa*中的“aa'’是画蛇添足的部分，因为(a|b)*已经包括了含有“aa”子串的所有a、b字符串，因此(a|b)，b和((a|b)*|aa)*b是等价的。 -
第3题：
若两个正规式所表示的正规集相同,则认为二者是等价的。()此题为判断题(对，错)。
正确答案：正确
-
第4题：
对于以下编号为①、②、③的正规式，正确的说法是(5)。
①(aa*|ab)*b
②(a|b)*b
③((a|b)*|aa)*b
A．正规式①、②等价
B．正规式①、③等价
C．正规式②、③等价
D．正规式①、②、③互不等价
正确答案：C
解析：由正规式①产生的字串为a*b或(ab)*b；②产生的字串为a*b或b*b、③产生的字串为a*b或b*b。因此，正规式②、③等价。 -
第5题：
有限自动机(FA)可用于识别高级语言源程序中的记号(单词)，FA可分为确定的有限自动机(DFA)和不确定的有限自动机(NFA)。若某DFA D与某NFA M等价，则(48)。
A．DFA D与NFA M的状态数一定相等
B．DFA D与NFA M可识别的记号相同
C．NFA M能识别的正规集是DFA D所识别正规集的真子集
D．DFA D能识别的正规集是NFA M所识别正规集的真子集
正确答案：B
解析：本题考查程序语言翻译基础知识。非确定有限自动机NFA是一个五元组(5-tuple)：M=(S，∑，move，s0，F)其中，①S是有限个状态(state)的集合；②∑是有限个输入字符(包括ε)的集合：③move是一个状态转移函数，move(si，ch)=sj表示，当前状态si下若遇到输入字符ch，则转移到状态即④sj；④s0是唯一的初态(也称开始状态)；⑤F是终态集(也称接受状态集)，它是S的子集，包含了所有的终态。确定的有限自动机DFA是WA的特例：①DFA没有状态具有ε状态转移(ε-transition)，即状态转换图中没有标记ε的边；②对每一个状态s和每一个字符a，最多有一个下一状态。若两个FA识别同一个正规集，则这两个FA等价。对于每个NFA，都存在与之等价的DFA。