给定正则表达式绘制最小DFA [英] drawing minmal DFA for the given regular expression

问题描述

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

What is the direct and easy approach to draw minimal DFA, that accepts the same language as of given Regular Expression(RE).
I know it can be done by:

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

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

But is there any shortcut way? like for (a+b)*ab

推荐答案

正则表达式转换为DFA

尽管没有从正则表达式(RE)提取DFA的算法快捷方式，但通过分析(而不是通过推导)可以使用快捷方式技术，但是它可以节省绘制最小化dfa的时间.但是偏离路线的技术只能通过实践来学习.我以您的例子来说明我的方法:

Regular Expression to DFA

Although there is NO algorithmic shortcut to draw DFA from a Regular Expression(RE) but a shortcut technique is possible by analysis not by derivation, it can save your time to draw a minimized dfa. But off-course the technique you can learn only by practice. I take your example to show my approach:

(a + b)*ab   

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

First, think about the language of the regular expression. If its difficult to sate what is the language description at first attempt, then find what is the smallest possible strings can be generate in language then find second smallest.....

保留一些基本正则表达式的记忆式解决方案.例如，我在这里写了一些基本的想法来编写左线性和直接来自正则表达式的右线性语法.同样，您可以编写以解释最小化dfa.

Keep memorized solution of some basic regular expressions. For example, I have written here some basic idea to writing left-linear and right-linear grammars directly from regular expression. Similarly you can write for construing minimized dfa.

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

In RE (a + b)*ab, the smallest possible string is ab because using (a + b)* one can generate NULL(^) string. Second smallest string can be either aab or bab. Now one thing we can easily notice about language is that any string in language of this RE always ends with ab (suffix), Whereas prefix can be any possible string consist of a and b including ^.

此外，如果当前符号为a；那么一个可能的机会是下一个符号将是b并以字符串结尾.因此，在dfa中，我们需要进行转换，以使当b符号出现在 符号a之后时，应将其移至某些最终状态 dfa.

Also, if current symbol is a; then one possible chance is that next symbol would be a b and string end. Thus in dfa we required, a transition such that when ever a b symbol comes after symbol a, then it should be move to some of the final state in dfa.

接下来，如果一个新符号进入了最终状态，那么我们应该进入某些 non-final 状态，因为b之后的任何符号都只能在某种字符串的中间出现，因为所有语言字符串以后缀'ab'结尾.

Next, if a new symbol comes on final state then we should move to some non-final state because any symbol after b is possible only in middle of some string in language as all language string terminates with suffix 'ab'.

因此，基于此知识，我们可以绘制出如下所示的不完整过渡图:

So with this knowledge at this stage we can draw an incomplete transition diagram like below:

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

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

现在您需要了解:每个州都有一些含义，例如

Now at this point you need to understand: every state has some meaning for example

(Q ₀ )表示=起始状态
(Q ₁ )的意思是=最后一个符号是'a'，再加上一个'b'，我们可以转换到最终状态
(Q _f )的意思是=最后两个符号是'ab'

(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. (更新的过渡图)

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--------|  

但是假设符号b代替符号a处于最终状态.然后，我们应该从最终状态转变为某些非最终状态.在这种情况下的当前过渡图中，我们应该从最终状态Q _f 移至初始状态.(同样，我们需要字符串中的ab来接受)

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--------|  

此图仍不完整！因为没有Q ₁ 中符号a的传出边.对于状态Q ₁ 上的符号a，需要一个自循环，因为Q ₁ 表示最后一个符号是a.

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--------|     

现在，我相信Q ₁ &中存在所有可能的向外边缘上图中的Q _f .一个丢失的边是符号b从Q ₀ 的输出边.并且必须在状态Q ₀ 处存在一个自循环，因为再次需要一个ab序列，以便字符串可以被接受.

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的快速而客观的方法.

Off-course the method might look difficult at first few tries. But if you learn to draw this way you will observe improvement in your analytically skills. And you will find this method is quick and objective way to draw DFA.

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

这篇关于给定正则表达式绘制最小DFA的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！