automata - 来自这个 dfa 的正则表达式

Question

任何人的这个转换图的正则表达式是什么？可以制作并解释一下，我将非常感谢他。

标签： automatafinite-automata

Answer 1

我们可以为此写一些方程式：

(q0) = e + (q1)a + (q3)b
(q1) = (q0)a + (q2)b
(q2) = (q1)b + (q3)a
(q3) = (q0)b + (q2)a

您可以像这样阅读这些等式：“导致我进入状态 X 的字符串集是导致我进入状态 Y 后跟符号 c 的字符串集，或者是导致我进入状态 Z 后跟符号 d 的字符串集， 或者...”

我们现在可以使用替换和消除自引用的规则来求解这些方程，即：

if (q) = (q)x + y, then (q) = y(x*)

我们可以通过消除 (q3) 开始求解系统：

(q0) = e + (q1)a + [(q0)b + (q2)a]b
(q1) = (q0)a + (q2)b
(q2) = (q1)b + [(q0)b + (q2)a]a

分发：

(q0) = e + (q1)a + (q0)bb + (q2)ab
(q1) = (q0)a + (q2)b
(q2) = (q1)b + (q0)ba + (q2)aa

我们现在可以摆脱 (q1) ：

(q0) = e + [(q0)a + (q2)b]a + (q0)bb + (q2)ab
(q2) = [(q0)a + (q2)b]b + (q0)ba + (q2)aa

分发：

(q0) = e + (q0)aa + (q2)ba + (q0)bb + (q2)ab
(q2) = (q0)ab + (q2)bb + (q0)ba + (q2)aa

对类似术语进行分组：

(q0) = e + (q0)(aa + bb) + (q2)(ab + ba)
(q2) = (q0)(ab + ba) + (q2)(aa + bb)

使用规则删除自引用：

(q0) = (aa + bb)* + (q2)(ab + ba)(aa + bb)*
(q2) = (q0)(ab + ba)(aa + bb)*

代入去掉 (q2)：

(q0) = (aa + bb)* + [(q0)(ab + ba)(aa + bb)*](ab + ba)(aa + bb)*

分发：

(q0) = (aa + bb)* + (q0)(ab + ba)(aa + bb)*(ab + ba)(aa + bb)*

使用自引用规则：

(q0) = (aa + bb)*[(ab + ba)(aa + bb)*(ab + ba)(aa + bb)*]*