regular-language - 需要有限自动机的正则表达式 : Even number of 1s and Even number of 0s

Question

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

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

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

任何帮助将不胜感激

Answer 1

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

让我们代替语言符号 0 , 1我们拿 Σ = {a, b}以下是新的 DFA。

Notice start state is Q₀

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

DFA 接受的语言是由符号 a 组成的所有字符串的集合。和 b其中符号数 a和 b是偶数(包括 Λ )。

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

正如我在我的回答中所说: How to write regular expression for a DFA每个状态存储一些信息。下面是上面 DFA 中每个状态存储的信息。

Q₀: Even number of a and even number of b
Q₁: Odd number of a and even number of b
Q₂: Odd number of a and odd number of b
Q₃: Even number of a and odd number of b

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

什么是正则表达式？
下面使用 Arden's Theorem 解释该方法。 ，适用于只有一个起始状态且没有定义空移动的转移图(我们的 DFA 就是这种形式)。该技术在一本书中进行了解释: Formal Languages And Automata Theory

记住 4.2 ARDEN THEOREM :

Let B and C be are two Regular Expressions over Σ. If C does not contain Λ, then for the equation A = B + AC has a unique (one and only one) solution A = BC*.

【解决方法】:

第一步 : 写出初始方程，一个方程对应于 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) 中额外 Λ是因为 Q0 是初始状态，无需任何输入即可到达(起点)。
因为 Q0 也只是一个最终状态，所以一个字符串由 a, b 组成。如果它在 Q0 结束是可以接受的。 Q0 的值将为我们提供所需的正则表达式，因此我们的目标是根据 a, b 简化方程-(1) .

第 2 步:使用来自其他方程的状态值并使用 Arden 的简化方程来简化方程。

让我们首先采用等式-(4) 并从等式-(3) 中替换 Q2 的值。

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 是 Q3，B = Q0b + Q1ba 和 C = aa .所以根据 Arden's therm，方程 Q3 = Q0b + Q1ba + Q3aa 有一个唯一的解:

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

或者可以这样写:

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

从逻辑上讲，您可以检查/理解 eq-(5) 表示 Q3 可以通过应用 + 以两种方式 ( b ) 达到。在 Q0 上有一个带有标签 aa 的循环在第三季度，第二种方式是从第一季度开始，申请 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)*

现在 Q3 的值从等式-(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)* )*

拿 Q0 骗子:

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

你能理解这个等式，它如何从状态 Q0 到 Q1？我们将这个解记为方程-(7)

如上所述，我们可以根据状态 Q0 和 a, b 评估 Q1 的值。 , 类似地，我们将评估状态 Q3 的值。为此，我们可以简单地将等式(5)中的状态 Q1 的值放入等式(7)中。

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) 中接受状态 Q3 和 Q1 的值。

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 解决方案以符号 a 的形式找到状态 Q0 的值和 b .

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) 之后阅读我的评论)

为了根据 Q0 评估状态 Q1 的值，我将等式 (5) 中 Q3 的值放入等式 (6) 中，得出等式 (7) 如下:

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

类似地，为了根据 Q0 评估状态 Q3 的值，我们可以将等式(6)中的 Q1 值代入等式(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)* )*

现在将状态 Q1 和 Q3 的值代入方程-(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)*