regular-language - 有限自动机需要正则表达式：偶数个 1 和偶数个 0

Question

我的问题对你来说可能听起来不同。

我是初学者，我正在学习有限自动机。我正在互联网上查找下面给定机器的有限自动机的正则表达式。

谁能帮我写上面机器的“有限自动机的正则表达式”

任何帮助将不胜感激

Answer 1

如何使用 Arden 定理为 DFA 编写正则表达式

让我们代替语言符号0，1我们采用Σ = {a, b}新的 DFA。

注意开始状态为 Q ₀

你没有给出，但在我的回答中，初始状态是 Q ₀，最终状态也是 Q ₀。

is DFA 接受的语言是由所有字符串组成的集合，由符号a和符号数组成，b其中符号数为偶数（包括）。abΛ

一些示例字符串是{Λ, aa, bb, abba, babbab }，没有符号出现的顺序和模式的限制，只是两者都应该是偶数次。
注意：Λ是允许的，因为 numberOf( a) 和 numberOf( b) 为零即偶数。

正如我在我的直线回答中所说：如何为 DFA 编写正则表达式，每个州都存储一些信息。下面是上面 DFA 中每个状态存储的信息。

Q ₀：偶数a和偶数 Q ₁：奇数 和偶数 Q ₂：奇数 和奇数 Q ₃：偶数 和奇数b
ab
ab
ab

（您可以通过更改最终状态集为更有趣的语言制作 DFA）
_{人们应该阅读划线的答案，因为我在两个答案中对 DFA 罚款 RE 的方法是不同的}

什么是正则表达式？
下面使用Arden 定理解释该方法，适用于有单个开始状态且未定义空移动的转换图（我们的 DFA 就是这种形式）。该技术在一本书中进行了解释：形式语言和自动机理论

记住4.2 雅顿定理：

LetB和Cbe 是两个正则表达式Σ。如果C不包含Λ，则方程 A = B + AC 有唯一的（一个且只有一个）解 A = BC*。

[解决方案]：

Step-1：写出初始方程，一个方程对应于DFA中的每个状态。这个等式意味着如何一步达到一个状态

因此，根据我们的 DFA，以下 4 个方程是可能的：

1. Q ₀ = Λ+ Q ₁ a + Q ₃ b
2. Q ₁ = Q ₀ a + Q ₂ b
3. Q ₂ = Q ₁ b + Q ₃ a
4. Q ₃ = Q ₀ b + Q ₂ a

在等式（1）中，额外Λ是因为Q ₀是初始状态，无需任何输入（起点）即可到达。因为 Q ₀也只是一个最终状态，所以如果字符串a, b以 Q ₀结尾，那么它是可以接受的。Q ₀的值将为我们提供所需的正则表达式，因此我们的目标是简单的方程-(1) a, b。

步骤 2：通过将其他方程的状态值和使用 Arden 的简化方程来简化方程。

让我们首先取方程-(4) 并从方程-(3)中替换 Q _2的值。

Q ₃ = Q ₀ b + Q ₂ a
Q ₃ = Q ₀ b + (Q ₁ b + Q ₃ a) a
Q ₃ = Q ₀ b + Q ₁ ba + Q ₃ aa

最后一个方程可以用 Arden 方程的形式来查看A = B + AC。其中 A 是 Q ₃，B = Q ₀ b + Q ₁ ba 和 C = aa。所以根据 Arden 的 therm，方程 Q ₃ = Q ₀ b + Q ₁ ba + Q ₃ aa 有一个唯一解，即：

Q ₃ = (Q ₀ b + Q ₁ ba)(aa)*

或者可以这样写：

5. Q ₃ = Q ₀ b(aa)* + Q ₁ ba(aa)*

从逻辑上讲，您可以检查/理解 eq-(5) 意味着可以通过两种方式到达Q ₃+ ( ) 首先通过应用bQ ₀aa然后在 Q ₃上有一个带有标签的循环，第二种方式是从 Q ₁应用ba。

以类似的方式，我们可以简化方程-(2)

Q ₁ = Q ₀ a + Q ₂ b
Q ₁ = Q ₀ a + (Q ₁ b + Q ₃ a)b
Q ₁ = Q ₀ a + Q ₁ bb + Q ₃ ab

在这里使用 Arden 的简化规则。

Q ₁ = (Q ₀ a + Q ₃ ab)(bb)*

进一步简化

6. Q ₁ = Q ₀ a(bb)* + Q ₃ ab(bb)*

现在 Q ₃的值从方程-(5) 到方程-(6)

Q ₁ = Q ₀ a(bb)* + (Q ₀ b(aa)* + Q ₁ ba(aa)* )ab(bb)*
Q ₁ = Q ₀ a(bb)* + Q ₀ b(aa) * ab(bb)* + Q ₁ ba(aa)* ab(bb)*

再次使用 Arden 简化定律改进最后一个方程。

Q ₁ = (Q ₀ a(bb)* + Q ₀ b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*

以 Q ₀骗子：

7. Q ₁ = Q ₀ (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*

你能理解这个方程，它是如何从状态 Q _{0到 Q 1}的吗？我们将此解记为等式-(7)

如上所述，我们可以根据状态 Q ₀和来评估 Q ₁的值，同样我们要评估状态 Q ₃的值。为此，我们可以简单地将方程-(5) 中的状态 Q ₁ 的值放入方程-(7)。 a, b

5. Q ₃ = Q ₀ b(aa)* + Q ₁ ba(aa)*
. Q ₃ = Q ₀ b(aa)* + Q ₀ (a(bb)* + b(aa)* ab(bb)* ) ( ba(aa)* ab(bb)* )* ba(aa)*
8. Q ₃ = Q ₀ ( b(aa)* + (a(bb)* + b(aa)* ab(bb)* ) (ba( aa)* ab(bb)* )* ba(aa)* )

现在，在方程编号 (1) 中，从方程编号 (8) 和 (7) 接受 状态 Q ₃和 Q _1的值。

Q ₀ = Λ+ Q ₁ a + Q ₃ b
Q ₀ = Λ+ Q ₀ (a(bb)* + (aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* a + Q ₀ ( b(aa)* + (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* ba(aa)* ) b

现在，上次应用 Arden 解决方案以符号和的形式找到状态 Q ₀的值。 ab

Q ₀ = Λ+ ( (a(bb)* + (aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* a + ( b(aa)* + (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* ba(aa)* ) b )*

这与（我们可以Λ 在这里丢弃）RE 相同：

( (a(bb)* + (aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* a + ( b(aa)* + (a(bb)* + b(aa) )* ab(bb)* ) (ba(aa)* ab(bb)* )* ba(aa)* ) b )*

这就是您要寻找的 RE。

我不确定它是否可以进一步简化。我把它留给你作为练习。

在链接的问题中，我提出了一种非形式化的分析方法，但很难为这个 DFA 应用和找到 RE，这个问题展示了 Arden 定理的力量和逐步解决方案。

编辑：

我以前的正则表达式是正确的，但由于不对称的形式，很难葡萄。下面我正在写更对称的新形式的 RE。

我们有方程-（5），（6）如下：

5. Q ₃ = Q ₀ b(aa)* + Q ₁ ba(aa)*
6. Q ₁ = Q ₀ a(bb)* + Q ₃ ab(bb)*

两者结构对称，易于学习。（在上面的 eq-(5) 之后阅读我的评论）

为了根据 Q ₀评估状态 Q ₁的值，我将方程-(5) 中的 Q ₃值放入方程-(6)，得到方程-(7)，如下所示：

7. Q ₁ = Q ₀ (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*

类似地，要根据 Q ₀评估状态 Q ₃的值，我们可以将方程-(6) 中的 Q ₁值放入方程-(5)，这将给出方程-(8) 的新形式，如下所示：

Q ₃ = Q ₀ b(aa)* + Q ₁ ba(aa)*
Q ₃ = Q ₀ b(aa)* + (Q ₀ a(bb)* + Q ₃ ab(bb)* ) ba(aa) *
Q ₃ = Q ₀ b(aa)* + Q ₀ a(bb)* ba(aa)* + Q ₃ ab(bb)* ba(aa)*

现在，我们可以得到我们想要的形式的方程-(8)：

8. Q ₃ = Q ₀ (b(aa)* + a(bb)* ba(aa)* )(ab(bb)* ba(aa)* )*

现在，我们有等式-(1)、(7)、(8)：

1. Q ₀ = Λ+ Q ₁ a + Q ₃ b
7. Q ₁ = Q ₀ (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*
8. Q ₃ = Q ₀ (b(aa)* + a(bb)* ba(aa)* ) (ab(bb)* ba(aa)* )*

现在，我们可以得到我们想要的形式的方程-(8)：

8. Q ₃ = Q ₀ (b(aa)* + a(bb)* ba(aa)* )(ab(bb)* ba(aa)* )*

现在，我们有等式-(1)、(7)、(8)：

1. Q ₀ = Λ+ Q ₁ a + Q ₃ b
7. Q ₁ = Q ₀ (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*
8. Q ₃ = Q ₀ (b(aa)* + a(bb)* ba(aa)* ) (ab(bb)* ba(aa)* )*

现在将状态 Q ₁和 Q ₃的值代入方程-(1)：

Q ₀ = Λ+ Q ₀ (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* a + Q ₀ (b(aa)* + a( bb)* ba(aa)* ) (ab(bb)* ba(aa)* )* b

也可以写成：

Q ₀ = Λ+ Q ₀ ( (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* a + (b(aa)* + a(bb )* ba(aa)* ) (ab(bb)* ba(aa)* )* b )

接下来，在这个方程上应用 Arden 定理，我们得到最终的 RE：

偶数个'a'和偶数个'b' 的正则表达式：

( (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* a + (b(aa)* + a(bb)* ba(aa) * ) (ab(bb)* ba(aa)* )* b )*

可以进一步简化如下：

((a + b(aa)*ab)(bb)*(ba(aa)*ab(bb)*)*a + (b + a(bb)*ba)(aa)*(ab(bb)*ba(aa)*)*b)*

Answer 2

设 E 是 a 和 b 的偶数个的语言，下面是语言 E 的正则表达式。

[00 + 11 + (01+10)(11+00) (01+10)]

00 = 类型 1

11 = 类型 2

(01+10)(00+11)*(01+10) = type3

假设我们正在扫描 E 语言中的一个单词，从左到右一次读取两个字母。首先是双 0（type1），然后是双 1（type2），然后是另一个双 0（再次输入 1）。然后也许我们遇到了一对不一样的字母。例如，假设接下来的两个字母是 10。这必须以 type3 的子字符串开头。它以一个未加倍的对（01 或 10）开始，然后是一段加倍的字母（00 或 11 的多次重复），最后以另一个未加倍的对（01 或 10 再次）结束。这部分单词的一个特性是它有偶数个 0 和偶数个 1。如果该部分以 10 开头，则它可以以 01 结尾，但在结尾处仍然给出两个 0 和两个 1，中间只有两个字母。如果它以 10 开头并以 01 结尾，同样，它将给出偶数个 0 和偶数个 1。在 type3 的这一部分之后，我们可以继续处理更多的 type 或 type2 部分，直到我们遇到另一个未加倍的对，开始另一个 type3 部分。我们知道另一对未加倍的对将出现以平衡最初的一对。总的效果是 E 语言的每个单词都包含偶数个 0 和偶数个 1

Answer 3

这是包含偶数个 0 和 1 的偶数语言的 DFA

它的 RE 将是这个

(00 + 11 + (01+10)(01+10) (00 + 11)*)*

在这里，它将接受甚至是 0 和 1 nmber 的 lemda

或将接受 (00) 甚至 0 的 nmbr 并且没有 1 表示此处 1 的 nmber 是偶数。或者 (11) 在这种情况下 (0) 的 nmber 是偶数 .. 所以您可以检查它是否会生成包含偶数的字符串数字 0 和 1 ..

希望它能解决你的问题