单选题正规式MI和M2等价是指（）A MI和M2的状态数相等B Ml和M2的有向弧条数相等。C M1和M2所识别的语言集相等D Ml和M2状态数和有向弧条数相等

题目

单选题

正规式MI和M2等价是指（）

MI和M2的状态数相等

Ml和M2的有向弧条数相等。

M1和M2所识别的语言集相等

Ml和M2状态数和有向弧条数相等

参考答案和解析

正确答案： C

解析：暂无解析

如果没有搜索结果或未解决您的问题，请直接联系老师获取答案。

相似问题和答案

第1题：

与正规式(a|b)*等价的正规式是哪个()。

A、a*|b*

B、a*b*

C、(a*b*)*

D、(ab)*

参考答案：C

第2题：

MI,M2分别表示截面形状、尺寸、材料强度完全相同的适筋梁和超筋梁的抗弯承载力()。

A.M1>M2

B.M1<M2

C.M1=M2

参考答案：A

第3题：

对于以下编号为①、②、③的正规式，正确的说法是(30)。

①(aa*|ab)*b

②(a|b)*b

③((a|b)*|aa)*b

A．正规式①、②等价

B．正规式①、③等价

C．正规式②、③等价

D．正规式①、②、③互不等价

正确答案：C
解析：根据正规式r和s的意义，两个正规式等价说明r和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是等价的。

第4题：

与正规式(a|b)*等价的正规式是______。

A．a*b*

B．b*a*

C．(a*)|(b*)

D．(a*b*)*

正确答案：D
解析：如果两个正规式对应的正规集相同，那么它们是等价的。正规式(a|b)*对应的正规集为{ε，a，b，aa，ab，…，所有由a和b组成的字符串}，a*b*、b*a*、(a*)|(b*)对应的正规集都是其真子集，因此不可能等价。根据正规式代数运算法则，(a|b)*=(a*b*)*，注意，括号外的“*”是必需的!

第5题：

某一非确定性有限自动机(NFA)的状态转换图如下图所示，与该NFA等价的正规式是(28)，与该NFA等价的DFA是(29)。

A．0*|(0|1)0

B．(0|10)*

C．0*((0|1)0)*

D．0*(10)*

正确答案：B
解析：根据分析题目中给出的状态转换图可知，该NFA可识别空串以及任意数目0组成的串，但若出现1，则其后至少要有1个0才能到达终态，因此，该自动机识别的串等价于正规式(0|10)*。

第6题：

两个正规式等价，当且仅当它们所描述的正规集相同。()

参考答案：正确

第7题：

某一非确定性有限自动机(NFA)的状态转换图如图6-1所示，该NFA等价的正规式是(1)，与该NFA等价的DFA是(2)。

A．0*|(0|1)0

B．(0|10)*

C．0*((0|1)0)*

D．0*(10)*

正确答案：B

第8题：

对于以下编号为①、②、③的正规式，说法正确的是(28)。 ①(aa*|ab)*b ②(a|b*|aa)*b ③(a|b)*b

A．正规式①和③等价

B．正规式①和②等价

C．正规式②和③等价

D．正规式①、②和③互不等价

第9题：

已知∑={0,1}上的正规表达式0*1(0|10*1)*，它和下列哪个图的NFA等价，(27)。

A．

B．

C．

D．

正确答案：B
解析：对于任一正规表达式R，可按如下方法构造出与之等价的非确定的有限自动机。①对于正规式R，可用下图所示的拓广状态图表示。②通过对正规式R进行分裂并加入新的结点，逐步把图转变成每条弧上的标记是∑上的一个字符或ε，转换规则如下图所示。最后所得的图即为一个NFAM，x为初态结点，y为终态结点。显然，L(M)=L(R)。按照上述方法构造正规表达式0*1(0|10*1)*的非确定的有限自动机的过程如下所示。

第10题：

与正规式(a|b)*等价的正规式为(27)。

A．a*|b*

B．a*b*

C．(a*b*)*

D．(ab)*

正确答案：C
解析：正规式(a，b)*表示字符a和b的任意组合，A、B和D均不能表示a和b的任意组合，正确答案为C。

正规式MI和M2等价是指（）

题目

参考答案和解析

相似问题和答案

更多相关问题

相关内容