regex - 将调节表达式转换为 DFA

Question

一个多小时以来，我一直在尝试不同的方法来解决这个问题，但我感到非常沮丧。

问题是:给出以下每种语言在 Sigma = {0,1} 上的正则表达式和 DFA。

a). {w ∈ Σ* | w 包含偶数个 0 或奇数个 1}

如果有人可以提供提示或让我开始解决这个问题，我将非常感激!

我知道这与 DFA 的内容类似，但这个是针对

{w ∈ Σ* | w 包含偶数个 0 或正好两个 1}

所以有点不同，但我无法弄清楚。

Answer 1

你可以看到如下:你总是要记住两件事:

1. 0的数量是偶还是奇；和
2. 1的数量是偶数还是奇数。

现在，如果我们用 e 表示偶，用 o 表示奇，我们考虑四种状态:>ee(均为偶数)、eo(偶数个 0 和奇数个 1)、oe 和 oo。

现在，当我们读取零 (0) 时，我们只需交换第一个状态标记，因此这意味着我们引入了以下转换:

1. ee - 0 -> oe;
2. eo - 0 -> oo;
3. oe - 0 -> ee;和
4. oo - 0 -> eo。

对于 (1) 相同:

1. ee - 1 -> eo;
2. eo - 1 -> ee;
3. oe - 1 -> oo;和
4. oo - 1 -> oe。

现在我们只需要确定初始状态和接受状态。初始状态是 ee，因为此时我们没有考虑任何零和一。

此外，接受状态可以由条件确定:

w contains an even number of 0s or an odd number of 1s

这意味着接受状态是 ee、eo 和 oo。该DFA的图如下所示:

---

存在一种算法方法可以将DFA转换为等效的正则表达式，如here所述.

您可以通过将问题分成两个更简单的问题来构造正则表达式:

• 一个正则表达式，用于检查 0 的数量是否为偶数；和
• 检查 1 的数量是否为奇数的正则表达式。

首先，您可以使用正则表达式:

(1*01*0)*1*

确实:您首先有一个组(1*01*0)。该组确保有两个零，并且 1 可以出现在其间的任何位置。我们允许任意次数的重复，因为次数始终保持偶数。正则表达式以 1* 结尾，因为字符串中仍然可能存在其他表达式。

第二个问题可以用正则表达式解决:

0*1(0*10*1)*0*

解决方案或多或少是相同的。括号之间的表达式:(0*10*1) 确保这些均匀出现。通过在前面添加一个1，我们保证1的数量是奇数。

解决问题的正则表达式是:

(1*01*0)*1*|0*1(0*10*1)*0*

因为“管道”(|) 表示“或”。