L = {w ∈ {a, b}*, Na(w) mod 2 = 1} 的正则表达式

Question

我无法解决这个问题，如果有人能解决这个问题。

我的问题是 L = {w ∈ {a, b}*, Na(w) mod 2 = 1}

Answer 1

如果您在编写正则表达式时遇到困难，但知道如何制作 DFA，请先执行此操作，然后编写一些方程式并求解正则表达式。 DFA 在这里似乎很容易：

     /---a---\
     |       |
     V       |
---->q0--a-->q1
    / ^     / ^
   /  |    /  |
   \--/    \--/
     b       b

在这里，q1 正在接受。我们从中得到一些方程式：

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

我们想求解 (q1)。让我们删除 (q0) 方程中的自引用：

(q0) = e + (q0)b + (q1)a
     = (e + (q1)a) + (q0)b
     = (e + (q1)a)b*

现在我们可以代入 (q1) 的等式：

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

分发和重新排列：

(q1) = [(e + (q1)a)b*]a + (q1)b
     = (e + (q1)a)b*a + (q1)b
     = b*a + (q1)ab*a + (q1)b
     = b*a + (q1)(ab*a + b)

现在我们可以轻松地从这个等式中删除自引用：

(q1) = b*a + (q1)(ab*a + b)
     = b*a(ab*a + b)*

我们可以观察到：

regular expression for L = {w ∈ {a, b}*, Na(w) mod 2 = 1}