正则表达式转nfa例题

正则表达式是一种用于描述文本模式的语言。然而，计算机并不直接理解正则表达式，它们需要转换为一种称为NFA（非确定有限状态自动机）的形式。在本文中，我们将以一个例子为基础来说明如何将正则表达式转换为NFA。

首先，我们需要有一个正则表达式。我们将从一个简单的例子开始。我们将使用以下正则表达式：

`(a|b)*abb`

该正则表达式表示一个由字符a或b组成的字符串，以字符序列“abb”结尾，字符序列可以重复0次或多次。

接下来，我们将根据以下步骤将其转换为NFA：

1.将每个字符作为单独的状态添加到NFA中。这个过程叫做“构建NFA表”。

我们得到以下NFA表：

| | a | b | ε |

|---|---|---|---|

| 0 | 1 | 2 | |

| 1 | | | 3 |

| 2 | | | 3 |

| 3 | | | |

左侧第一列为状态，上方为输入字符和ε。

其中，0-3为状态编号，分别表示：起始状态，匹配a的状态，匹配b的状态和匹配abb的状态。ε表示空字符，即NFA可以在没有输入字符的情况下从一个状态转移到另一个状态。

2.将正则表达式转换为NFA。我们将从表达式的左侧开始，并将每个字符和操作符转换为一个或多个状态，直到我们到达表达式的右侧。这个过程叫做“转换”。

我们的正则表达式以“（”开始，表示我们需要将其转换为一个新的状态。我们将从左到右遍历正则表达式，将每个字符和操作符转换为一个或多个状态。在这个例子中，我们需要注意以下内容：

- “a”和“b”表示单个字符，因此我们需要为每个字符添加一个状态。

- “|”表示或，因此我们需要创建一个新状态来表示分支。

- “*”表示零个或多个重复，因此我们需要创建一个循环。

我们将得到以下NFA：


我们从左到右遍历正则表达式。我们将“a”和“b”表示为单个状态。我们将“|”表示为一个分支状态（状态4）和两个不确定的转移（由前一个状态指向状态4，由状态4指向其他状态），表示可以在两种方式之间进行选择。我们用一个循环状态（由状态5指向状态5）表示“*” 的重复（请注意，这里使用一个ε状态，表示我们可以在单个输入字符之间跳转）。最后，我们用三个状态（由状态5指向状态6、状态6指向状态7、状态7指向状态8）表示结尾字符串“abb”。

现在我们已经转换了正则表达式，我们可以验证它是否工作，检查FA是否接受字符串“abb”。

如果我们开始在起始状态0中，并将字符序列“abb”输入到NFA中，我们将得到以下状态转换：

| 输入 | 状态0 | 状态1 | 状态2 | 状态3 | 状态4 | 状态5 | 状态6 | 状态7 | 状态8 |

|-----|------|------|------|------|------|------|------|------|------|

| | ✔ | | | | | | | | |

| a | | ✔ | | | | ✔ | | | |

| b | | | ✔ | | ✔ | ✔ | | | |

| b | | | | ✔ | | | ✔ | | ✔ |

我们可以注意到，我们的NFA接受字符串“abb”，因为我们到达了最后一个状态8，并且我们使用了所有输入字符。