确定的自动机以及不确定的自动机都能正确地识别正规集。

题目

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

相似问题和答案

第1题：

● 有限自动机（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

第2题：

Chomsky定义的四种形式语言文法中，2型语言可由()识别。

A、短语结构文法

B、前后文无关文法

C、前后文有关文法

D、正规文法

E、图灵机

F、有限自动机

G、下推自动机

参考答案：G

第3题：

下图所示的有限自动机中，0是初始状态，3是终止状态，该自动机可以识别(22)。

A．abab

B．aaaa

C．bbbb

D．abba

正确答案：B
解析：A选项中到达状态3后输入a再次回到状态3，但输入b后无法被识别。c选项中经过的状态为0→1→2→3，在状态3时输入b无法被识别。D选项中在第二次输入b后即不能被识别。

第4题：

某一确定有限自动机(DFA)的状态转换图如下图，与该自动机等价的正规表达式是(28)，图中(29)是可以合并的状态。

(56)

A．ab*a

B．ablab*a

C．a*b*a

D．aa*lb*a

正确答案：A

第5题：

下图所示的有限自动机中，s0是初始状态，s1为终止状态，该自动机不能识别( )。

A．abab

B．aaaa

C．babb

D．abba

正确答案：A
解析：要判断一个字符串能否被指定的自动机识别，就看在该自动机的状态图中能否找到一条从开始状态到终止状态的路径，且路径上的字符串等于要识别的字符串。对于字符串“abab”，识别路径为s0→s1→s2→s1→s2，字符串结束时的状态不是终止状态，所以该自动机不能识别“abab”。字符串“aaaa”的识别路径为s0→s1→s3→s3→s3，字符串“babb”的识别路径为s0→s2→s1→s2→s3，字符串“abba”的识别路径为s0→sl→s2→s3→s3，它们结束时的状态都是终止状态，所以都能被自动机识别。

第6题：

不确定的自动机不能正确地识别正规集。()

参考答案：错误

第7题：

已知一不确定的有限自动机(NFA)如图2-8所示，采用子集法将其确定化为DFA的过程如表2-1所示。

状态集T1中不包括编号为(23)的状态；状态集T2中的成员有(24)：状态集T3等于(25)；该自动机所识别的语言可以用正规式(26)表示。

A．2

B．4

C．3

D．5

正确答案：A

第8题：

下图所示为两个有限自动机M1和M2(A是初态、C是终态)，(48)。

A．M1和M2都是确定的有限自动机

B．M1和M2都是不确定的有限自动机

C．M1是确定的有限自动机，M2是不确定的有限自动机

D．M1是不确定的有限自动机，M2是确定的有限自动机

正确答案：D
解析：在计算理论中，非确定有限状态自动机或非确定有限自动机(NFA)是对每个状态和输入符号对可以有多个可能的下一个状态的有限状态自动机。这区别于确定有限状态自动机(DFA)，它的下一个可能状态是唯一确定的。图中，M1的状态A中当输入0时，既可以转为状态A也可以转为状态B，M2中的每个状态在一种输入的情况下，下一个状态始终是确定的。所以，M1为不确定的，M2为确定的。

第9题：

某一确定有限自动机(DFA)的状态转换图如下，与该自动机等价的正规表达式是(28)，图中(29)是可以合并的状态。

(42)

A．(a|ba)*bb(a*b*)*

B．(a|ba)*bba*|b*

C．(a*|b*)bb(a|b)*

D．(a|b*)*bb(a*|b*)

正确答案：A

第10题：

●下图所示为一个有限自动机（其中，A是初态、C是终态），该自动机识别的语言可用正规式(48)表示。

(48)

A. (0|1)*01

B．1*0*10*1

C．1*(0)*01

D.1*(0|10)*1*

正确答案：A

确定的自动机以及不确定的自动机都能正确地识别正规集。

题目

相似问题和答案

更多相关问题

相关内容