常规语言 – 为给定的正则表达式绘制最小DFA

虽然没有算法快捷方式从正则表达式(RE)绘制DFA,但是通过分析而不是通过派生可以实现快捷方法,它可以节省您绘制最小化dfa的时间.但是,在课程中你只能通过练习来学习.我举个例子来展示我的方法：

(a + b)*ab

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

保留一些基本正则表达式的记忆解决方案.例如,我有written here some basic idea to writing left-linear and right-linear grammars directly from regular expression.同样你可以编写用于构造最小化的dfa.

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

另外,如果当前符号是a;那么一个可能的机会是下一个符号将是b和字符串结尾.因此,在dfa中,我们需要一个过渡,当b符号出现在符号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’

现在想想如果符号a出现在最终状态会发生什么.更多的是陈述Q1,因为这个状态意味着最后一个符号是a. (更新过渡图)

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

但是假设符号b代替符号b处于最终状态.然后我们应该从最终状态转变为非最终状态.在这种情况下的当前转换图中,我们应该从最终状态Qf转移到初始状态(同样我们需要ab in string for acceptation)

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

此图表仍然不完整！因为Q1的符号a没有外边缘.对于符号a on状态Q1,需要自循环,因为Q1表示最后一个符号是a.

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

现在我相信所有可能的外向边缘都出现在Q1& Qf在上图中.一个缺失的边缘是符号b的Q0的外出边缘.并且必须在状态Q0处存在自循环,因为我们再次需要一个ab序列以便字符串可以被接受. (从Q0到Qf的转换可以用ab)

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

现在DFA已经完成了！

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

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