将 RE 转换为 FA

为了将 RE 转换为 FA，我们将使用一种称为子集方法的方法。该方法用于从给定的正则表达式中获取 FA。该方法如下所示：

步骤 1： 使用带有 ε 移动的 NFA，为给定的正则表达式设计一个转换图。

步骤 2： 将此带有 ε 的 NFA 转换为没有 ε 的 NFA。

步骤 3： 将获得的 NFA 转换为等效的 DFA。

示例 1

从给定的正则表达式 10 + (0 + 11)0* 1 设计一个 FA。

解： 首先，我们将为给定的正则表达式构建转换图。

步骤 1

步骤 2

步骤 3

步骤 4

步骤 5

现在我们得到了没有 ε 的 NFA。现在我们将把它转换为所需的 DFA，为此，我们首先要写一个这个 NFA 的转移表。

等效的 DFA 将是

示例 2

从给定的正则表达式 1 (1* 01* 01*)* 设计一个 NFA。

解： 给定正则表达式的 NFA 如下所示

步骤 1

步骤 2

步骤 3

示例 3

为正则表达式 0*1 + 10 构建 FA。

解决方案

我们将首先构建 R = 0*1 + 10 的 FA，如下所示

步骤 1

步骤 2

步骤 3

步骤 4