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

绘制最小的直接且简单的方法是什么DFA，接受与给定相同的语言Regular Expression(RE).
我知道可以通过以下方式完成：

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

但有没有什么捷径呢？像(a+b)*ab

正则表达式到 DFA

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

(a + b)*ab   

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

记住一些基本正则表达式的解决方案。例如，我有这里写了一些直接从正则表达式编写左线性和右线性语法的基本想法。 https://stackoverflow.com/questions/13816439/left-linear-and-right-linear-grammars/13945932#13945932同样，您可以编写用于解释最小化 dfa 的代码。

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

另外，如果当前符号是a;那么一个可能的机会是下一个符号将是b和弦尾。因此，在 dfa 中，我们需要一个转换，以便每当b符号来了after symbol 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'

Now think what happens if a symbol a comes on final state. Just more to state Q₁ because this state means last symbol was a. (updated transition diagram)

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

But suppose instead of symbol a a symbol b comes at final state. Then we should move from final state to some non-final state. In present transition graph in this situation we should make a move to initial state from final state Q_f.(as again we need ab in string for acceptation)

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

This graph is still incomplete! because there is no outgoing edge for symbol a from Q₁. And for symbol a on state Q₁ a self loop is required because Q₁ means last symbol was an a.

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

Now I believe all possible out-going edges are present from Q₁ & Q_f in above graph. One missing edge is an out-going edge from Q₀ for symbol b. And there must be a self loop at state Q₀ because again we need a sequence of ab so that string can be accept. (from Q₀ to Q_f shift is possible with ab)

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

现在 DFA 已完成！

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

_{* In the link I given, I described some more regular expressions, I would highly encourage you to learn them and try to make DFA for those regular expressions too.}