假定一个输入符号(symbol)，可以得到2个或者2个以上的可能状态，那么这个finite automaton就是不确定的，反之就是确定的。例如：

　　这就是一个不确定的无限自动机，在symbol a输入的时候，无法确定状态应该转向0，还是1

　　不论是确定的finite automaton还是非确定的finite automaton，它们都可以精确的描述正规集(regular sets)

　　我们可以很方便的把正规表达式(regular expressions)转换成为不确定 finite automaton

　　2. NFA(Nondeterministic Finite Automaton)

　　非确定的无限自动机，我们用NFA这个术语表示，它是一个数学模型(model)：

　　1.　　　　　　 一个关于状态的集合S

　　2.　　　　　　 一个关于输入符号(input symbols)的集合Σ

　　3.　　　　　　 函数 move : (状态, 符号) -> P(S)

　　4.　　　　　　 一个开始状态s0，是一个唯一的状态

　　5.　　　　　　 一个结束(接受)状态集合F

　　注意，P(S)，表示S的幂集。在NFA中，input symbol可以为 ε

　　转换函数(transition function)的含义就是，一个确定的状态已经从这个状态出发的一条边的标签(符号symbol)，可以确定它的下一个状态组成的集合，比如上图(这个转换图就是NFA的一种表示方式)，0状态，a符号，确定了一个状态的集合{0,1}

　　3. 转换图(transition graph)的表示

　　我们知道，计算机是无法直接表示一个图，我们应该如何来表示一个转换图？使用表格就是一个最简单的方法，每行表示一个状态，每列表示一个input symbol，这种表格被叫做 transtion table(转换表)

　　可以说使用表格是最简单的表示方式，但是我们可以注意到在这个图中状态1和input symbol a，是没有下一个状态的(空集合)，也就是，对于一个大的状态图，我们可能花费大量的空间，而其中空集合会消耗不少空间，但是这种消耗又不是必须的，所以，作为最简单的一种实现方式，却不是最优的

　　语言(language)被NFA定义成为一个input string的集合，而这个集合中的元素则是被NFA受接受的所有的字符串(那些可以从开始状态到某接受状态的input string)

　　至于存储的方式，可以试试邻接表。注意，使用什么样的数据结构来保存NFA按情况不同而不同，在一些特殊情况下，某些数据结构会变得很方便使用，而换入其他情况，则不可以使用了。

编缉推荐阅读以下文章

• 词法分析(6)---DFA的化简
• 词法分析(5)---从正规式到NFA
• 词法分析(4)---NFA与DFA的转化
• 词法分析(3)---DFA
• 词法分析(1)---词法分析的有关概念以及转换图
• 一个小语言的词法分析程序