时间戳

首页 > 解决方案 > L = {w ∈ {a, b}*, Na(w) mod 2 = 1} 的正则表达式

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

问题描述

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

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

标签： automata

解决方案

如果您在编写正则表达式时遇到困难，但知道如何制作 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 对。

推荐阅读