-
- 当一个机器在任意一个给定状态,并读入下一个输入符号时,到达的状态是确定的(且只有一个),那么这个机器就是确定型的。
- 非确定有限状态自动机(Nondeterministic Finite Automaton, NFA)。当这样一个机器读入一个符号,有可能会分割成多个机器(如果这个符号指向多个状态的话)。除此之外,当其什么也不读入的时候(即读入
),也有可能会分割成多个机器。这几个机器会并行运行。当输入结束时,只要有其中一个处于接受态,整个NFA就算接受了这个输入(有点量子计算的感觉)。
- 当一个机器在一个状态,并读入了下一个符号,但机器这个符号没有对应的下一个状态,这个机器就死了(不再计算了)。
- 下图描述了一个NFA(我们叫它
),它能接受所有包含101或11为子串的串。
图1 一个NFA - NFA的形式定义
- 一个NFA是一个5元组
是一个有限的状态集合。
是一个有限的符号集。
是转移函数(其中
,
是
的幂集(Power Set))。
是起始状态。
是接受状态的集合。
- 一个NFA是一个5元组
- 重要定理: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》的时候,书里有很多次暗示了需要对于每个字符都能转移(具体在哪里已经忘了)。是否学术界对这个问题还存在争议?
tql
tql(商业互吹?