题目
DFA只能有1个终态,而NFA可以有多个A. 错误B. 正确
DFA只能有1个终态,而NFA可以有多个
A. 错误
B. 正确
题目解答
答案
A
解析
考查要点:本题主要考查学生对确定性有限自动机(DFA)和非确定性有限自动机(NFA)基本概念的理解,特别是两者终态数量的差异。
解题核心思路:
- 明确DFA和NFA的定义:DFA的转移函数是确定的(每个状态对每个输入符号有且仅有一个转移),而NFA允许存在多条转移路径或空转移。
- 终态的定义:终态是自动机接受输入后所处的状态,DFA和NFA均可以有多个终态,题目中的说法错误在于对DFA终态数量的限制。
破题关键点:
- DFA的终态数量:DFA的定义中没有限制终态数量,多个终态是允许的。
- NFA的终态数量:NFA同样可以有多个终态,题目中关于NFA的部分正确,但整体命题因前半句错误而成立。
题目陈述:
“DFA只能有1个终态,而NFA可以有多个”是否正确?
分析过程:
-
DFA的终态数量:
- DFA的转移函数是确定的,但终态数量可以是任意个数。例如,一个DFA可以有两个终态$A$和$B$,当计算结束时处于$A$或$B$均可接受输入。
- 题目中“DFA只能有1个终态”的说法错误。
-
NFA的终态数量:
- NFA允许非确定性转移,但终态数量同样可以是多个。例如,NFA可以有终态$C$、$D$、$E$,满足接受条件。
- 题目中“NFA可以有多个终态”的说法正确。
结论:
题目前半句错误,后半句正确,整体命题不成立,因此答案为A(错误)。