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

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

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

我的问题是 L = {w ∈ {a, b}*, Na(w) mod 2 = 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)*

我们可以观察到:

  1. a 的数量总是奇数,因为总是添加一个,并且第一个之后的任何一个都以匹配的对添加
  2. 这种语言中的字符串可以以任意数量的 b 开头,以任意数量的 b 结束,并且可以用任意数量的 b 分隔任何相邻的 a 对。