nfa转化成dfa简单例题

NFA（非确定有限状态自动机）和DFA（确定有限状态自动机）是计算机科学中常见的用于识别语言的有限状态自动机。二者的区别主要在于：NFA在状态转移时，可以有多种选择，而DFA在状态转移时只有一种选择。

在实际编程中，我们通常使用NFA来描述语言，但在编译器或解释器中，我们需要将其转化为DFA，便于程序识别语言。那么，如何将NFA转化为DFA呢？下面将从多个角度分析。

一、NFA转化为DFA的步骤

NFA转化为DFA的步骤主要包括以下几个：

1. 删除NFA中的ε转移。将NFA中所有的ε转移去掉。

2. 对每个状态，找出其所有可能的子集。例如，假设一个状态有两个转移（a和b），那么在DFA中这个状态需要拆分成两个状态，分别代表a和b两种转移的结果。

3. 将每个子集看作一个DFA中的状态。例如，若有两个子集，一个包含状态1和状态2，另一个子集只包含状态2，则这两个子集分别表示DFA中的两个状态。

4. 在DFA中，对于每个状态和每个输入符号，找出状态转移的结果。例如，在某个状态下，若对于输入符号a，其所有包含状态的转移结果包含DFA中的状态2和状态3，则在DFA中这个状态对于输入符号a的转移结果是状态2和状态3。

5. 最后，在DFA中标记每个包含NFA的接受状态的子集。若某个包含NFA中的接受状态的子集被标记为DFA中的接受状态，则这个子集表示的状态也是DFA中的接受状态。

二、示例

以下是一个简单的例题，将其NFA转化为DFA。

给定正则表达式：(ab)*+a(a|b)*

对应的NFA如下所示：


我们可以看到，NFA中有ε转移。我们需要将其去掉。去掉ε转移后，NFA变为：


接着，我们对于每个状态，找出其所有可能的子集。

对于状态1，它能够到达状态2，所以对于输入a，它的后继状态是{2}。对于输入b，它没有后继状态，所以对于输入b，它的后继状态是{}。

对于状态2，它能够到达状态3和状态5，所以对于输入a，它的后继状态是{3,5}。对于输入b，它没有后继状态，所以对于输入b，它的后继状态是{}。

对于状态3，它能够到达状态4，所以对于输入a，它的后继状态是{4}。对于输入b，它没有后继状态，所以对于输入b，它的后继状态是{}。

对于状态4，它没有后继状态，对于输入a，它的后继状态是{}。对于输入b，它也没有后继状态，所以对于输入b，它的后继状态是{}。

对于状态5，它能够到达状态6，所以对于输入a，它的后继状态是{6}。对于输入b，它没有后继状态，所以对于输入b，它的后继状态是{}。

对于状态6，它没有后继状态，对于输入a，它的后继状态是{}。对于输入b，它也没有后继状态，所以对于输入b，它的后继状态是{}。

因此，得到DFA如下所示：


三、NFA转化为DFA的局限性

尽管在某些情况下，NFA转化为DFA能极大地提高程序的效率，但在一些特殊的情况下，这种转换也有其局限性。

例如，对于某些含有“回溯”特性的正则表达式，转换后的DFA会非常大，甚至超出程序的处理能力。此外，由于NFA和DFA在表达能力上是等价的，因此有时候我们关注的是算法的表达能力而非效率，此时NFA会更好一些。

尽管有这些局限性，将NFA转换为DFA仍然是程序员们最经常使用的技术之一。在实践中，我们需要根据具体情况进行选择。