2. 非确定性

    • 当一个机器在任意一个给定状态,并读入下一个输入符号时,到达的状态是确定的(且只有一个),那么这个机器就是确定型的。
    • 非确定有限状态自动机(Nondeterministic Finite Automaton, NFA)。当这样一个机器读入一个符号,有可能会分割成多个机器(如果这个符号指向多个状态的话)。除此之外,当其什么也不读入的时候(即读入 \varepsilon ),也有可能会分割成多个机器。这几个机器会并行运行。当输入结束时,只要有其中一个处于接受态,整个NFA就算接受了这个输入(有点量子计算的感觉)。
    • 当一个机器在一个状态,并读入了下一个符号,但机器这个符号没有对应的下一个状态,这个机器就死了(不再计算了)。
    • 下图描述了一个NFA(我们叫它 N_1 ),它能接受所有包含101或11为子串的串。
    图1 一个NFA
    • NFA的形式定义
      • 一个NFA是一个5元组 (Q,\Sigma,\delta,q_0,F)
        • Q 是一个有限的状态集合。
        • \Sigma 是一个有限的符号集。
        • \delta:Q\times \Sigma_\varepsilon \rightarrow \mathcal{P}(Q) 是转移函数(其中 \Sigma_\varepsilon=\Sigma\cup \{\varepsilon\} ,\mathcal{P}(Q) 是 Q 的幂集(Power Set))。
        • q_0\in Q 是起始状态。
        • F\subseteq Q 是接受状态的集合。
    • 重要定理:NFA和DFA识别同一类语言。每个NFA都有一个对应的DFA(DFA是一种特殊的NFA)。
    • 一个语言是正则(Regular)的,当且仅当有NFA能识别这种语言。

     

  • 讨论:对于DFA来说,是否对于每一个状态,读入任何一个字符集里的字符都能转移(即DFA会不会“死掉”)。以下是关于这个问题的一个讨论。

    https://cs.stackexchange.com/questions/12587/in-a-dfa-does-every-state-have-a-transition-on-every-symbol-of-the-alphabet

    根据里面的回答的说法,是不需要的。但在我读这本《Introduction to the Theory of Computing》的时候,书里有很多次暗示了需要对于每个字符都能转移(具体在哪里已经忘了)。是否学术界对这个问题还存在争议?

2 条思考于 “2. 非确定性

发表评论

电子邮件地址不会被公开。

*