将DFA转换为RE

Question

我为由符号0、1和2（Σ= {0,1、2}）构成的所有字符串的语言L构造了一个有限自动机，其中最后一个符号不少于第一个符号。例如，字符串0、2012、01231和102用的是语言，但字符串10、2021和201则不是用的语言。

然后从那个GNFA，所以我可以转换为RE。

我的RE看起来像这样：

(0(0+1+2)* )(1(0(1+2)+1+2)* )(2((0+1)2+2))*)

我不知道这是否正确，因为我认为我理解RE，但并不完全确定。

有人可以告诉我它是否正确，如果不正确吗？

Answer 1

[general method可以将任何DFA转换为正则表达式，并且可能是解决该作业问题所应使用的。

对于您的具体尝试，您可以通过找到应该使用该语言但您的RE不接受的单词或不应该使用RE所使用的语言的单词来判断RE是否不正确接受。在这种情况下，字符串1002应该使用该语言，但是RE与之不匹配。

导致此字符串不匹配的两个主要原因。首先是在语言的三个主要部分之间应该存在联合而不是串联（分别以0，1和2开头的单词：

(0(0+1+2)*)   (1(0(1+2)+1+2)*)   (2((0+1)2+2))*) // wrong
(0(0+1+2)*) + (1(0(1+2)+1+2)*) + (2((0+1)2+2))*) // better

第二个问题是，在1和2情况下，小于起始数字的数字必须是可重复的：

(1(0 (1+2)+1+2)*) // wrong
(1(0*(1+2)+1+2)*) // better

如果您同时做这两件事，那么RE将是正确的。对于2案例，我将其留作练习，让您继续执行此步骤。

接下来您可以尝试的是找到一种使RE更紧凑的方法：

(1(0*(1+2)+1+2)*) // verbose
(1(0*(1+2))*) // equivalent, but more compact

这最后一步只是优先事项。您不需要尾随的+1+2，因为0*的长度可以为零，因此0*(1+2)涵盖了+1+2的情况。

Answer 2

您可以使用一种算法，但是此DFA可能很容易将其一次性转换。

[首先，请注意，如果在初始状态下看到的第一个符号是0，则您将转换到状态A并保留在那里。 A正在接受。这意味着可以接受以0开头的任何字符串。因此，我们的正则表达式中也可能包含0(0+1+2)*之类的术语。

[第二，请注意，如果在初始状态下看到的第一个符号是1，则从该点开始，您将转换到状态B，并保持在状态B和D。仅当您看到B时才离开0，并且只要您一直看到B就可以离开0。以D结尾的唯一方法是，如果您看到的最后一个符号是0。因此，当且仅当字符串不以1结尾时，才接受以0开头的字符串。我们也可以在正则表达式中使用类似1(0+1+2)*(1+2)的术语来覆盖这些情况。

[第三，请注意，如果在初始状态下看到的第一个符号是2，则您将转换到状态C，并从该点开始保持在状态C和E。如果除了C之外什么都看不到，请离开状态2，并保持在B之外，直到再次看到2。以C结尾的唯一方法是，如果您看到的最后一个符号是2。因此，当且仅当字符串以2结尾时，才接受以2开头的字符串。我们也可以在正则表达式中使用类似2(0+1+2)*(2)的术语来覆盖这些情况。

最后，我们看到没有其他情况需要考虑；我们的三个术语涵盖了所有情况，它们的结合充分描述了我们的语言：

0(0+1+2)* + 1(0+1+2)*(1+2) + 2(0+1+2)*2

在这里简单地写出答案很容易，因为此DFA有点像三个简单的DFA一起放入了起始状态。更复杂的DFA可能会使用不需要您了解或遵循DFA所做的算法而更容易转换为RE。

请注意，如果开始状态正在接受（在另一个答案的注释中提到），则RE的变化如下：

e + 0(0+1+2)* + 1(0+1+2)*(1+2) + 2(0+1+2)*2

[基本上，我们只是将空字符串附加到其上，因为聚合表达式的任何其他部分尚未生成该空字符串。