2. 计算机
  3. 有限自动机可分为确定的有限自动机和不确定的有限自动机。那么确定的有限自动机A与不确定的有限自动机B等价，则( )。

有限自动机可分为确定的有限自动机和不确定的有限自动机。那么确定的有限自动机A与不确定的有限自动机B等价，则( )。

admin2019-06-12  12
问题 有限自动机可分为确定的有限自动机和不确定的有限自动机。那么确定的有限自动机A与不确定的有限自动机B等价，则(    )。
选项 A、A与B的状态个数相等
B、A与B可识别的记号完全相同
C、B能识别的正规集是A所识别正规集的真子集
D、A能识别的正规集是B所识别正规集的真子集
答案B
解析 本题考查程序设计语言的有限自动机，是常考的知识点。
有限状态自动机由3部分组成：
    (1)一根输入带：输入带可以理解成由一系列带块组成，每个带块上只含有一个输入符号(终结符号)，输入带上输入符号串由特殊符号“⊥”结束，⊥!∈T。
    (2)一个输入头：初始时，输入头指向第一个带块(即指向输入带最左端的带块)，输入头每次将输入头下方带块上的输入符号读入，然后输入头向右移动一个带块，准备读入下一个带块上的输入符号。
    (3)一个有限状态控制器：有限状态控制器所能处于的状态的全体组成状态集合Q，Q中有若干特殊状态：一个初始状态q0和若干最终状态qf。开始时有限状态控制器处于初始状态，以后有限状态控制器所处状态由状态转换函数d决定。
    下面给出有限状态自动机M的形式描述：
非确定有限状态自动机M是一个五元组，M=(VT，Q，d,q0,Qf)。其中：
    VT：有限非空终结符集合。
    Q：有限非空状态集合。
    d：从Q×VT到Q的幂集2Q上的状态转换函数。
    q0：初始状态，q0∈Q。
    Qf：最终状态集，Qf∈Q ｜Qf｜≥1。
    有限状态自动机M被称为确定性的，当且仅当转换函数d对于任何q∈Q，ai∈VT，d(q,ai)至多只有一个元素q’。对于任一个非确定性的有限状态自动机M，存在一个确定的有限状态自动机M’，使M，所接受的语言L(M’)就是L(M)。
    有限自动机的确定化：对于任一个非确定性的有限状态自动机M，都可以构造其对应的确定性有限自动机M’，使这两个自动机接受相同的字符串集合L(M’)=L(M)。
    所以若某DFA D与某NFA M等价，则DFA D与NFA M可识别的记号相同。
转载请注明原文地址:https://kaotiyun.com/show/ldRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)