将规则表达式转换为 DFA

Question

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

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

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

如果有人能提供提示或帮助我开始解决这个问题，将不胜感激！

我知道它与此 DFA 类似，但此 DFA 适用于

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

所以有点不同，但我想不通。

Answer 1

想一想您可能处于的状态。

现在让我们看看您的语言接受哪些组合：

因此，您的 DFA 将需要 4 个状态，其中 3 个是接受状态，1 个是拒绝状态。每个状态都会有 2 个转换导致不同的状态。由于空字符串中有偶数个0和偶数个1，所以第一个状态就是初始状态。

将其变成正则表达式：想想你如何匹配偶数个 0，然后你如何匹配奇数个 1。语言就是这两者的结合。

或者，，您可以使用算法将 any NFA 转换为正则表达式。它的优点是非常通用，但也更具技术性。无论哪种方式，它都应该导致等效的正则表达式。

有偶数个 0 的数字是什么样的？它可能以任意数量的 1 开头，但当我们确实找到一个 0 时，我们最好再找到一个！中间可以有任意数量的 1，但我们只关心 0。于是，我们想出了下面的正则表达式：

1*(01*01*)*

您应该能够应用类似的逻辑来匹配奇数个 1。最后将两个表达式或运算得到请求的正则表达式。

Answer 2

你可以这样看：你永远要记住两件事：

现在，如果我们用 e 表示 even，用 表示 odd o，我们考虑四种状态：ee（均为偶数），eo（偶数个0和奇数个1） , oe 和 oo.

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

相同的 (1):

现在我们只需要确定初始状态和接受状态。初始状态是ee，因为在那一刻我们已经考虑了没有零和没有。

此外接受状态可以由条件决定：

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

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

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

您可以通过将问题拆分为两个更简单的问题来构建正则表达式：

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

(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*

因为 "pipe" (|) 表示 "or".

Convert a regulation expression to DFA