lowsfish

• 当一个机器在任意一个给定状态，并读入下一个输入符号时，到达的状态是确定的（且只有一个），那么这个机器就是确定型的。
• 非确定有限状态自动机（Nondeterministic Finite Automaton, NFA）。当这样一个机器读入一个符号，有可能会分割成多个机器（如果这个符号指向多个状态的话）。除此之外，当其什么也不读入的时候（即读入  ），也有可能会分割成多个机器。这几个机器会并行运行。当输入结束时，只要有其中一个处于接受态，整个NFA就算接受了这个输入（有点量子计算的感觉）。
• 当一个机器在一个状态，并读入了下一个符号，但机器这个符号没有对应的下一个状态，这个机器就死了（不再计算了）。
• 下图描述了一个NFA（我们叫它  ），它能接受所有包含101或11为子串的串。

• NFA的形式定义
  • 一个NFA是一个5元组 
    •  是一个有限的状态集合。
    •  是一个有限的符号集。
    •  是转移函数（其中  , 是  的幂集（Power Set））。
    •  是起始状态。
    •  是接受状态的集合。
• 重要定理：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》的时候，书里有很多次暗示了需要对于每个字符都能转移（具体在哪里已经忘了）。是否学术界对这个问题还存在争议？