regular-language - 将 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 但并不完全确定。

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

标签： regular-languagefinite-automatacomputation-theorydfa

Answer 1

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

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

其次，请注意，如果在初始状态中看到的第一个符号是1，那么您将转换到 stateB并保持在 statesB并D从那时起。你只有看到了才会离开B，0只要B你一直看到，你就会远离0。结束的唯一方法D是，如果您看到的最后一个符号是0. 因此，以 开头1的字符串当且仅当字符串不以 . 结尾时才被接受0。我们也可以1(0+1+2)*(1+2)在正则表达式中使用类似的术语来涵盖这些情况。

第三，请注意，如果在初始状态中看到的第一个符号是2，那么您将转换到 stateC并保持在 state 中C并E从那时起。C如果你看到任何东西，你就会离开状态2，B直到你2再次看到 a 为止。结束的唯一方法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

基本上，我们只是将空字符串附加到它上面，因为它还没有由聚合表达式的任何其他部分生成。