NFA也是自动机的一种，与DFA对应。对于DFA来说，在指定状态，经过指定字母，会到达唯一确定的状态。对于NFA而言，在指定状态经过指定字母，到达的是一个状态的集合。换种说法，经过某个字母到达的状态不是唯一确定的，候选集合中的状态都存在可能。
特别的，NFA存在 ϵ 边，即不需任何字母即可从一个状态去往另一个状态。考虑仅由字母 {a,b} 构成的字符串。要求字母 b 必须连续出现，中间不能有其他字母分隔。其正规表达式写法可以为：a∗b∗a∗。
可以设计一个NFA，如下：
其中，状态1、2之间、状态2、3之间的边就是 ϵ 边。虽然状态1没有直接的出边标记为字母 b ，但是由于ϵ边的存在，状态1经过字母b仍然可以去到状态2。另一方面，考虑状态1，经过字母 a 以后，其可以到达的状态为{1,3}，不是唯一的，而是一个状态集合。这也是NFA区别于DFA的显著特征。
从编程的角度，使用NFA要明显难于DFA，因为NFA需要实现集合的操作。理论上，NFA有确定的算法转化为等价的DFA。所以可以先转为DFA再使用。
通常，在ACM竞赛中，我们不会设计NFA，而是会直接设计出DFA。例如上面的例子很容易设计出等价的DFA。
一般而言，形式化规则使用正规表达式描述最为“方便”，正规表达式有确定的方法转化为等价的NFA，NFA有确定的算法转化为等价的DFA，DFA有确定的方法转化为最小状态DFA（不计同构，最小状态DFA是唯一的）。
很多语言，例如C++（11标准以后）、Java在其标准库中都支持正规表达式。但是用于竞赛，一般都会超时（对于不会超时的题目，能用正规表达式解出的，几乎可以肯定不用工具照样能够解出）。而且，现成的正规表达式工具基本上只能做格式判断，不能完成更加复杂的任务。
在ACM常见的数据结构中，字典树就是一个典型的DFA。该DFA接收错误的状态并未画出。在这个DFA上能够运行到终态的字符串必然是字典树中的其中一个单词。
后缀自动机也是一个DFA，在这个DFA上能够运行到终态的是源串的后缀，能够运行到正常状态的是源串的子串。
而AC自动机则可以看做是具有 ϵ 边的NFA，其失败指针就是 ϵ 边。
当然根据应用的不同，这些FA在运行过程中，经过每一个状态时需要执行不同的动作。最简单的就是格式判断，途中的状态均不需要执行额外动作，只需判断最后落在何处即可。复杂的如AC自动机，为了实现多模式匹配，需要对途经的状态一一做出判断。