绘制minmal DFA为给定的正则表达式(drawing minmal DFA for the g

2019-06-21 18:29发布

什么是直接和简单的方法来绘制最小DFA ,接受相同的语言给出的Regular Expression(RE)
我知道它可以这样做:

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

但是,有没有捷径呢? 像(a+b)*ab

Answer 1:

正则表达式DFA

虽然没有快捷方式的算法,从正则表达式(RE),但快捷的技术绘制DFA可以通过不通过推导分析,它可以节省您的时间来绘制一个最小DFA。 但场外的技术只能通过实践学习。 我把你的例子来说明我的方法:

(a + b)*ab   

首先,考虑正则表达式的语言。 如果其难度沙爹什么是第一次尝试的语言描述,然后查找可能是最小的字符串可以用语言来生成然后找到第二个最小.....

保留了一些基本的正则表达式的存储解决方案。 例如,我在这里写了一些基本的想法,直接从正则表达式写左线和右线语法。 同样,你可以写诠释最小DFA。

在RE (a + b)*ab ,最小可能的字符串是ab ,因为使用(a + b)*一个能生成NULL(^)字符串。 第二小的字符串可以是aabbab 。 现在,有一点我们很容易就注意到了语言的是,在这个RE的语言任何字符串总是以结束ab (后缀),而前缀可以是任何可能的字符串包括ab包括^

此外,如果当前符号是a ; 那么一个可能的机会就是下一个符号将是一个b和字符串结束。 因此,在DFA我们需要一个过渡,这样当永远的b符号来符号 a ,那么它应该是移动到一些DFA 最终状态的。

接下来,如果一个新的符号来对最终状态,那么我们应该转移到一些非最终状态,因为之后的任何符号b可能只在某些字符串的中间语言,因为所有的语言字符串后缀终止'ab'

因此,这方面的知识,在这个阶段,我们可以得出下面像一个不完整的转移图:

--►(Q 0)--- ---一个►(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 IN上述曲线图。 一个丢失的边缘是从Q 0的出向边沿用于符号b 。 而且必须有状态Q 0自我循环,因为我们再次需要的序列ab ,这样字符串可以接受的。 ( 从Q 0至Q F换档是可能的ab

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

现在,DFA就完成了!

场外的方法看起来可能很难在第一次试几次。 但是,如果你学画画这种方式,你会在你的分析能力观察改善。 而且你会发现这个方法是借助DFA快速和客观的方式。

*在我给出的链接,我描述了多个正则表达式,我会强烈建议您了解他们,并设法使DFA的那些正则表达式了。



文章来源: drawing minmal DFA for the given regular expression