regular-language - 为给定的正则表达式绘制最小 DFA

Question

绘制最小DFA的直接且简单的方法是什么，它接受与给定正则表达式(RE)相同的语言。
我知道可以通过以下方式完成:

Regex ---to----► NFA ---to-----► DFA ---to-----► minimized DFA

但是有什么捷径吗？就像(a+b)*ab

Answer 1

正则表达式到 DFA

虽然没有从正则表达式 (RE) 绘制 DFA 的算法快捷方式，但可以通过分析而不是推导来实现快捷技术，它可以节省您绘制最小化 dfa 的时间。但当然，这项技术只能通过练习来学习。我以你的例子来展示我的方法:

(a + b)*ab   

首先，考虑一下正则表达式的语言。如果第一次尝试很难确定语言描述是什么，那么找到语言中可以生成的最小可能字符串是什么，然后找到第二小的......

记住一些基本正则表达式的解决方案。例如我有written here some basic idea to writing left-linear and right-linear grammars directly from regular expression.同样，您可以编写用于解释最小化 dfa 的代码。

在 RE (a + b)*ab 中，最小的可能字符串是 ab，因为使用 (a + b)* 可以生成 NULL(^) 字符串。第二小的字符串可以是 aab 或 bab。现在我们可以很容易注意到关于语言的一件事是，此 RE 语言中的任何字符串始终以 ab (后缀)结尾，而前缀可以是由 a 组成的任何可能的字符串和b，包括^。

此外，如果当前符号是a；那么一个可能的机会是下一个符号将是 b 和字符串结尾。因此，在 dfa 中，我们需要一个转换，以便当 b 符号出现在 a 后，那么它应该移动到某些DFA 中的最终状态。

接下来，如果新符号进入最终状态，那么我们应该移动到某个非最终状态，因为b之后的任何符号只能出现在某个字符串的中间在语言中，因为所有语言字符串都以后缀 'ab' 结尾。

所以有了这个阶段的知识，我们可以画出一个不完整的转换图，如下所示:

--►(Q₀)---a---►(Q₁)---b----►((Q_f))

现在你需要明白:每个状态都有一些含义，例如

(Q₀) means = Start state
(Q₁) means = Last symbol was 'a', and with one more 'b' we can shift to a final state
(Q_f) means = Last two symbols was 'ab'

现在想想如果符号a进入最终状态会发生什么。只是更多地说明 Q₁，因为该状态意味着最后一个符号是 a。 (更新了转换图)

--►(Q0)---a---►(Q1)---b----►((Qf))  
                ▲-----a--------|  

但是假设最终状态不是符号a而是符号b。然后我们应该从最终状态转移到某种非最终状态。在当前的转换图中，在这种情况下，我们应该从最终状态 Q_f 转移到初始状态。(我们再次需要字符串中的 ab 来接受)

--►(Q0)---a---►(Q1)---b----►((Qf))  
     ▲          ▲-----a--------|  
     |----------------b--------|  

该图仍然不完整!因为 Q₁ 中的符号 a 没有出边。对于状态 Q₁ 上的符号 a ，需要自循环，因为 Q₁ 意味着最后一个符号是 a 。

                a-  
                ||
                ▼|
--►(Q0)---a---►(Q1)---b----►((Qf))  
     ▲          ▲-----a--------|  
     |----------------b--------|     

现在我相信所有可能的传出边缘都存在于上图中的 Q₁ 和 Q_f 中。一个缺失的边是符号 b 的 Q₀ 的传出边。并且在状态 Q₀ 处必须有一个自循环，因为我们再次需要一个 ab 序列，以便可以接受字符串。 (使用 ab 可以从 Q₀ 转换到 Q_f)

    b-          a-  
    ||          ||
    ▼|          ▼|
--►(Q0)---a---►(Q1)---b----►((Qf))  
     ▲          ▲-----a--------|  
     |----------------b--------|      

现在 DFA 已完成!

当然，该方法在最初几次尝试时可能看起来很困难。但如果你学会用这种方式画画，你会发现你的分析能力有所提高。你会发现这种方法是快速、客观地绘制DFA的方法。

_{* 在我给出的链接中，我描述了更多正则表达式，我强烈鼓励您学习它们并尝试为这些正则表达式制作 DFA。}