问正则表达式之间的等价性

EN

(2)在一般情况下，需要大量的重写和等价规则来保证这一点。当然，如果您只是尝试为这两个特定的正则表达式执行此操作，那么您可以即席工作。

然而，(1)是“真正”的方法。我很惊讶你知道如何使用Arden引理，但不知道相反的方向，这是更常见的(在教科书和实践中)，也更容易。从字面上讲，任何正式的语言书籍或编译器书籍都会为您提供至少一种将正则表达式映射到DFA并最小化DFA的算法。如果您无法访问这类书籍，请参阅我多年前写的两篇文章，每篇文章都提供了算法的分类(当时是全面的)，一篇用于将正则表达式映射到DFA，另一篇用于最小化DFA：http://www.kornai.com/EFS/OnlineSupportMaterial/Watson/Papers/constax.600dpi.ps https://www.researchgate.net/publication/2247379_A_Taxonomy_of_Finite_Automata_Minimization_Algorithms

最后，更全面的工作是我自己的博士学位，名为“分类法和常规语言算法工具包”，从1995年开始。

顺便说一句，我还应该提到，有许多工具包以各种语言实现了这些算法。

致以最好的问候，布鲁斯

选项1对我来说似乎更好，可能是因为我不知道如何可行地完成选项2。我建议这样做：

构造一个DFA M1使得L(M1) = ($ + b)a*(b + bba*)*

• construct a DFA M2使得L( M12 ) = b*(a + bb +a DFA M21使得L(M12) = L(M1) \ bbb)b

1. construct a DFA M21使得L(M21) = L(M2) \L(M1)
2. 正则表达式描述相同的语言当且仅当L(M12)和L()都为空

要查看DFA M是否接受空语言，您可以：

通过最小化M来构造M‘

• 通过检查初始状态是否为空来查看M’是否接受空语言，并且在初始状态中发起的所有转换都终止于初始状态

要最小化DFA，可以从列出DFA的每一对状态开始。然后，划掉其中一个状态正在接受而另一个状态不接受的任何对。然后，迭代地划掉任意对(q，q')，其中q在符号s上到达某个状态p，q‘在符号s上到达某个状态p’，并且(q，q')已经被划掉。继续，直到不能再划掉更多的状态对。在这一点上，任何没有被划掉的对表示输入自动机中的等价状态，并且可以被组合在最小自动机中。这只是一种方法。其他方法也是可用的。

q    s    q'
q0   a    q1
q0   b    q2
q1   a    q1
q1   b    q3
q2   a    q2
q2   b    q3
q3   a    q3
q3   b    q0

这里，q0是初始的，q3是接受的。我们尝试第一种算法：

    q0    q0    q0    q1    q1    q2
    q1    q2    q3    q2    q3    q3
#   --    --    --    --    --    --
1               XX          XX    XX   // q0,q1,q2 are not accepting; q3 is
2   XX    XX                           // on input b these go to q2,q3
3                                      // can't cross out q1,q2 by any rule

我们发现q1和q2是等价的，可以组合起来得到以下等价的DFA：

q    s    q'
q0   a    q12
q0   b    q12
q12  a    q12
q12  b    q3
q3   a    q3
q3   b    q0

从正则表达式构造自动机的方法如下：

1. 如果r= x，其中x是语言字母表上的某个字符串，则可以通过为x的每个符号添加一个初始状态和一个附加状态来构造r的NFA；然后，使这些状态中的最后一个状态可接受；
2. 如果r= st，并且M和M‘是s和t的NFA，则r的NFA可以通过将M的所有接受状态改变为非接受，同时向不再是初始的M’的以前的初始状态添加λ转换来构造。
3. 如果r= s+t并且M和M‘是s和t的NFA，则可以通过将具有λ转换的新的初始状态添加到不再是初始的M和M’的以前的初始状态来构造r的NFA；
4. 如果r= s*并且M是s的NFA，则可以通过将具有λ转换的新的接受初始状态添加到M的以前的初始状态，同时添加从M的以前的接受状态到这个新的初始状态的λ转换，来构造r的NFA。

一旦有了正则表达式的NFA，就可以使用powerset或subset构造来确定它。为此，创建一个DFA，它为NFA的状态集的每个子集创建一个状态。然后，如果输入符号s将NFA从状态x带到状态y，则添加从子集X到子集Y的转换。注意:如果它有助于您思考，则可以首先删除λ转换，或者使用以下约定:如果s将NFA从Q带到q‘，并且存在从q’到Q‘的λ转换，则s也将NFA从Q带到Q’。初始状态是只包含NFA的初始状态的状态；所有包含接受状态的状态都是接受状态。

这将引导您完成步骤1和2。在这一点上，根据步骤5给出的建议进行最小化可能会有所帮助。接下来，使用笛卡尔乘积机构造来查找差异的DFA(或者只构造一台用于对称差异的机器，并节省一个步骤)。产品机器中的每个状态将对应于一对状态，一个状态取自第一个输入机，另一个取自第二个输入机。然后，在产品机器中添加转换，将DFA从状态(x，y)转换到状态( x‘，y')，在第一台机器中同时存在从x到x’的转换，在第二台机器中从y转换到y‘。初始状态是与输入机中的初始状态对相对应的状态；接受状态是那些(对于差异)具有x接受和y不接受的状态(对于对称差异，它们是具有x接受或y接受但不是两者的状态)。