两个正规集相等的必要条件是他们对应的正规式等价。

题目

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

相似问题和答案

第1题：

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

A．正规式①和③等价

B．正规式①和②等价

C．正规式②和③等价

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

第2题：

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

A、a*|b*

B、a*b*

C、(a*b*)*

D、(ab)*

参考答案：C

第3题：

两个串相等的充分必要条件是__________。

A、串长相等且各对应位置字符相等

B、所含字符集合相同

C、所含字符个数相同

D、串值相等

正确答案：AD

第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题：

正规式和正规集之间是否有一一对应的关系()。

A、存在

B、不存在

C、描述

D、无法确定

参考答案：B

第6题：

● 有限自动机（FA）可用于识别高级语言源程序中的记号（单词），FA 可分为确定的有限自动机（DFA）和不确定的有限自动机（NFA）。若某DFA D 与某NFA M等价，则（48）。

（48）

A. DFA D 与NFA M的状态数一定相等

B. DFA D 与NFA M可识别的记号相同

C. NFA M能识别的正规集是DFA D 所识别正规集的真子集

D. DFA D 能识别的正规集是NFA M所识别正规集的真子集

正确答案：B

第7题：

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

参考答案：正确

第8题：

对于以下编号为①、②、③的正规式，正确的说法是(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是等价的。

第9题：

两个串相等的充分必要条件是两个串的长度相等且对应位置的字符相同。()

此题为判断题(对，错)。

正确答案：正确

第10题：

两个函数依赖集等价是指(43)。

A．函数依赖个数相等

B．函数依赖集的闭包相等

C．函数依赖集相互包含

D．同一关系上的函数依赖集

正确答案：B
解析：本题考查函数依赖的基本概念。函数依赖集的等价是指两个函数依赖集包含的依赖信息等价，即函数依赖集的闭包相等。

两个正规集相等的必要条件是他们对应的正规式等价。

题目

相似问题和答案

更多相关问题

相关内容