5

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

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

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

4

1 回答 1

13

正则表达式到 DFA

虽然没有从正则表达式（RE）中绘制 DFA 的算法捷径，但是通过分析而不是推导可以使用捷径技术，它可以节省您绘制最小化 dfa 的时间。但是偏离了你只能通​​过练习才能学习的技术。我以你的例子来展示我的方法： 

(a + b)*ab

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

记住一些基本正则表达式的解决方案。例如，我在这里写了一些直接从正则表达式编写左线性和右线性语法的基本思想。同样，您可以编写用于解释最小化的 dfa。

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

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

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

所以在这个阶段有了这些知识，我们可以绘制一个不完整的转换图，如下所示：

--►(Q 0 )---a---►(Q 1 )---b----►((Q f ))

现在在这一点上您需要了解：例如，每个状态都有一些含义

(Q 0 ) 表示 = 起始状态
(Q 1 ) 表示 = 最后一个符号是“a”，再加一个“b”，我们可以转换到最终状态
(Q f ) 表示 = 最后两个符号是“ab”

现在想想如果符号a进入最终状态会发生什么。更多地说明 Q 1因为这个状态意味着最后一个符号是a。（更新的转换图） 

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

但是假设符号不是符号a，而是b最终状态。然后我们应该从最终状态转移到某个非最终状态。在这种情况下的当前转换图中，我们应该从最终状态 Q f移动到初始状态。（同样我们需要ab在字符串中接受） 

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

这张图还是不完整的！因为没有a来自 Q 1的符号的出边。对于a状态 Q 1上的符号， 需要自循环，因为 Q 1表示最后一个符号是a. 

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

现在我相信上图中的 Q 1和 Q f都存在所有可能的出边。一个缺失边是符号的 Q 0b的出边。并且在状态 Q 0必须有一个自循环，因为我们再次需要一个序列，ab以便字符串可以被接受。（从 Q 0到 Q f的转变是可能的ab） 

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

现在 DFA 完成了！

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

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

于 2012-12-24T17:35:54.653 回答