需要有限自动机的正则表达式:偶数1和偶数0

Question

我的问题听起来可能与你有所不同.

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

任何人都可以帮我写上述机器的"有限自动机的正则表达式"

任何帮助将不胜感激

Answer 1

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

让我们来代替语言的符号0,1我们就? = {a, b}和下面是新的DFA.

通知开始状态为Q ₀

你还没有给出但在我的回答中,初始状态是Q ₀,其中最终状态也是Q ₀.

语言通过在DFA设置的所有字符串的接受由符号a和b地方符号的数量a和b甚至(含?).

一些示例字符串是{?, aa, bb, abba, babbab },没有顺序约束和符号出现的模式只是两者应该是偶数个时间.
注意:?是允许的,因为numberOf(a)和numberOf(b)是偶数的零.

正如我在回答中所说:如何为DFA编写正则表达式,每个州都存储一些信息.以下是上述DFA中每个州存储的信息.

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

(您可以通过更改最终状态集来为更多有趣的语言制作DFA)_应该阅读有条理
_{的答案,因为我在两个答案中对DFA的罚款RE的方法是不同的}

什么是正则表达式？
使用Arden的Therm解释下面的方法可以适用于转换图,其中存在单个启动状态并且没有定义空移动(我们的DFA采用这种形式).这种技术在书中解释:形式语言和自动机理论

记住4.2 ARDEN THEOREM:

设B和C是两个正则表达式了?.如果C不包含?,那么对于等式A = B + AC具有唯一的(一个且仅一个)解A = BC*.

[解]:

步骤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 _0的值将给出我们所需的正则表达式,因此我们的目标就是方程式 - (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)*

现在,从等式(5)到方程式(6) 的Q ₃值

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 ₀ conman:

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

你能理解这个等式,它是如何从Q ₀状态转到Q _1的？我们记得这个解决方案是等式 - (7)

如上所述,我们可以用状态Q ₀来评估Q _1的值,并且类似地,我们将评估状态Q _3的值.为此,我们可以简单地将状态Q _1的值 从等式(5)放入等式(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 _0的值. 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 ₁的值,我将Q _3的值从等式(5)推入等式 - (6),其给出了等式(7)如下:

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

类似地,为了用Q ₀来评估状态Q ₃的值,我们可以将Q _1的值从等式(6)中放入等式(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 _3的值放入等式 - (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)*