2

这是一个研究项目的 DFA。我们手动创建了 DFA。我们对什么是与 DFA 对应的正则表达式感兴趣。当然，可以有多个正则表达式与之对应；我们更喜欢更简单的。

在此处输入图像描述

4

4 回答 4

1

您在 B 和 E 的自循环上错过了 DFA 中的标签。但是因为您说对于给定的 DFA，所以标签的唯一选择是0在两个循环上。

DFA 的正确正则表达式是：

(00* 10*1)* (1(0 + 10)* 1 1) ( 0 + 1 (00* 10*1)* 1  ( 0 + 10)* 1 1)*

简要说明：

  1. 您只有一个最终状态，即D。因此，如果字符串以D. 你是否注意到传入的边缘D被标记1并且D有一个标记为自循环0。

  2. 开始状态是A这样的字符串可以以0或以开头1。实际上，A 上有两个循环。一个从上图开始0 并穿过上图。
    上层循环的 RE 是： 00* 10*1

    要理解这一点：

      0     0*           1      0*            1  

 A-E   loop on E     E-F    loop on F     F-A

  3. 在下图中从A到。DRE 是1 (0 + 10)* 1 1
    为了理解这一点：

     1        (0 + 10)*    1     1
 A - B    loop on B    B-C   C-D

  4. DFA 的完整 RE 是：（答案） 

    (00* 10*1)* (1(0 + 10)* 1 1) ( 0 + 1 (00* 10*1)* 1  ( 0 + 10)* 1 1)*

    要理解这一点：

    (00* 10*1)*  (1(0 + 10)* 1 1) ( 0 + 1 (00* 10*1)* 1 ( 0 + 10)* 1 1)*

^             ^                                                    ^   
upper loop    A to D           loop on D              * for loop on D    


                      ( 0 +  1    (00* 10*1)* 1    (0 + 10)*   1  1  )*
                        ^    D-A   A-A        A-B  loop on B, B-c c-D       
                     self loop on D

按照@RedBaron 的评论编辑01110100110此正则表达式是否生成字符串：

首先检查它是否被 DFA 接受：

A--0--> E--1---> F--1---> A---1---> B--0---> B---1--->C ---0--- ->B---0---> B--1-->C---1---> D---0--->D‌​</p>

是的字符串被 DFA 接受。

如何从我在答案中给出的 RE 生成，下面我已经对齐了 RE 和字符串。

(00* 10*1)*    (1(0 + 10)* 1 1) ( 0 + 1 (00* 10*1)* 1 ( 0 + 10)* 1 1)*

 0^  1^ 1      1  0100     1  1   0

只有您可能必须了解的困难：如何(0 + 10)*生成0100？对于以下检查：

(0 + 10)*重复三遍：

(0 + 10)(0 + 10)(0 + 10)
 0           10  0
于 2013-03-29T16:39:07.360 回答
0

此处描述了您需要使用的算法。如果您对该主题更感兴趣，我强烈建议您阅读 Michael Sipser 的计算理论导论。

对于您的特定 DFA，按照您获得此正则表达式的算法：

[(010*1)*1(10*)110*1]*(010*1)*1(10)*110*
于 2013-03-29T05:54:23.770 回答
0

杰克，这个 DFA 基本上可以有两个正则表达式。第一个可以是 AB*CD*A，第二个可以是 AE*F*

于 2013-03-29T05:28:21.933 回答
0

10*110*用于从 ABCD 转换而没有 cB 中的循环

1(0*(10)*)*110*我认为也涵盖了 C 和 B 之间的循环

0+10*1是来自 AEF 的循环。所以你可以在这两个表达式前面加上前缀

你得到(0+10*1)*10*110*没有循环和(0+10*1)*1(0*(10)*)*110*它

因此最终的表达式是

(0+10*1)*1(0*(10)*)*110*

用于从 A 到 D 的过渡

最后到达状态 D 你可以得到 a 1，达到A并重复整个事情

((0+10*1)*1(0*(10)*)*110*)(1((0+10*1)*1(0*(10)*)*110*))*

查看此 DFA 的一些有效和无效字符串的实际操作

澄清- 此正则表达式基于 PCRE 接受的正则表达式。So+表示字符串出现 1 次或多次，*表示出现 0 次或多次，而|表示OR

编辑(0*(10)*)*可以写得更好（(0|(10))*感谢@grijesh-chauhan 为我指明了那个方向）。所以RE（基于PCRE）将是

((0+10*1)*1(0|(10))*110*)(1((0+10*1)*1(0|(10))*110*))*
于 2013-03-29T05:35:36.723 回答