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

Question

绘制minimal的直接简单方法是什么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(^)字符串可以生成字符串.第二个最小的字符串可以是aab或bab.现在,我们可以轻松注意到语言的一个问题是,此RE语言中的任何字符串始终以ab(后缀)结尾,而前缀可以是包含a和b包含的任何可能的字符串^.

此外,如果当前符号是a; 那么一个可能的机会是下一个符号将是一个 b字符串结尾.因此,在dfa中,我们需要一个过渡,当 b符号出现在符号之后a,它应该移动到dfa中的某个最终状态.

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

因此,在这个阶段我们可以使用以下知识绘制一个不完整的转换图:

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

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

(Q ₀)表示=开始状态
(Q ₁)表示=最后一个符号是'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--------|  

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

                a-  
                ||
                ?|
--?(Q0)---a---?(Q1)---b----?((Qf))  
     ?          ?-----a--------|  
     |----------------b--------|     

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

    b-          a-  
    ||          ||
    ?|          ?|
--?(Q0)---a---?(Q1)---b----?((Qf))  
     ?          ?-----a--------|  
     |----------------b--------|      

现在DFA已经完成了!

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

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