语言 C={a,b} 上的正则表达式

Question

大家晚上好，我被下面的正则表达式卡住了，

我认为表达方式比我的更简单，

我不得不写下正则表达式和 dfa，从字母表 {a,b} 接受所有以 b 开头和结尾且 a 为偶数的字符串。

我的尝试是进入案件，但结果不是很好:

我试过这样的事情： b b* (aba)* (aab)* (aa)* (aab)* (aba)* b*b

但我认为这还不完整。

我应该遵循一些一般规则来完成这项任务吗？或者我只需要练习正则表达式？

谢谢，任何提示或帮助将不胜感激。

Answer 1

DFA 在这里似乎更容易制作，所以我们可以从那里开始并从那里推导出正则表达式。

我们至少需要一个初始状态。此状态无法接受，因为空字符串不以 b 开头和结尾。我们称之为 q0.

如果我们在这种状态下看到一个a，我们正在查看一个不以b开头的字符串，所以无论接下来是什么我们都不能接受它。我们可以用一个新的、死的状态来表示它。我们称之为 q1.

如果我们在 q0 中看到 b，我们需要一个新的状态来表示我们即将看到符合条件的字符串这一事实。事实上，字符串 b 以 b 开始和结束，并且有偶数个 a （零是偶数）；所以这个状态一定是在接受。调用此 q2.

如果我们在 q2 中看到一个 a 那么我们有奇数个 a 并且没有最后看到一个 b，所以我们不能接受细绳。但是，仍然可以通过看到奇数个 a 后跟至少一个 b 来接受来自该状态的字符串。调用状态来表示这个q3.

如果我们在 q2 中看到一个 b，我们的情况和以前一样（偶数个 a 最后看到一个 b，所以我们可以接受）。留在q2.

如果在 q3 中我们看到一个 a，我们现在又得到偶数个 a，只需要一个 b。称这个新状态为 q4。如果我们看到一个 b，我们仍然需要一个 a，所以我们还不如留在 q3。

如果在 q4 中我们看到一个 a，我们再次需要更多 a 并且可以 return 到 q3。另一方面，如果我们得到 b，我们可以从 return 到 q2，因为字符串是我们的语言。

DFA 看起来像这样：

 q     s    q'
--    --    --
q0     a    q1        q0: initial state
q0     b    q2        q1: dead state, did not begin with b
q1     a    q1        q2: accepting state, even #a and start/stop with b
q1     b    q2        q3: start with b, odd #a
q2     a    q3        q4: start with b, even #a, stop with a
q2     b    q2
q3     a    q4
q3     b    q3
q4     a    q3
q4     b    q2

为了得到正则表达式，我们可以迭代地找到通向每个状态的正则表达式，然后取接受状态的正则表达式的并集。在这种情况下，只有 q2 接受，所以我们需要的只是该状态的正则表达式。我们迭代进行，在每个阶段进行替换。

round 0
(q0): e
(q1): (q0)a + (q1)(a+b)
(q2): (q0)b + (q2)b + (q4)b
(q3): (q2)a + (q3)b + (q4)a
(q4): (q3)a

round 1
(q0): e
(q1): a + (q1)(a+b) = a(a+b)*
(q2): b + (q2)b + (q4)b = (b+(q4)b)b*
(q3): (q2)a + (q3)b + (q4)a = ((q2)+(q4))ab*
(q4): (q3)a

round 2
(q0): e
(q1): a(a+b)*
(q2): (b+(q3)ab)b*
(q3): ((q2)+(q3)a)ab* = (q2)ab* + (q3)aab* = (q2)ab*(aab*)*
(q4): (q3)a

round3:
(q0): e
(q1): a(a+b)*
(q2): (b+(q3)ab)b*
(q3): (b+(q3)ab)b*ab*(aab*)* = bb*ab*(aab*)*+(q3)abb*ab*(aab*)* = bb*ab*(aab*)*(abb*ab*(aab*)*)*
(q4): (q3)a

round4:
(q0): e
(q1): a(a+b)*
(q2): (b+bb*ab*(aab*)*(abb*ab*(aab*)*)*ab)b*
(q3): bb*ab*(aab*)*(abb*ab*(aab*)*)*
(q4): bb*ab*(aab*)*(abb*ab*(aab*)*)*a

因此，正则表达式是这样的：

r = (b+bb*ab*(aab*)*(abb*ab*(aab*)*)*ab)b*
  = bb* + bb*ab*(aab*)*(abb*ab*(aab*)*)*abb*

bb* 部分编码了这样一个事实，即 b 的任何字符串都是该语言中的字符串。
另一部分以 bb* 开头和结尾，它编码了任何字符串必须以 b
最外层的 a 编码这样一个事实，即语言中带有 a 的任何字符串都必须同时具有第一个和最后一个 a
aab* 部分允许有连续的 a
abb*ab* 部分允许存在不连续的 a

最后一点，上面的表达式替换规则如下：

A: r       r is an expression
B: As      s is an expression
=
A: r
B: rs


A: r + As  r, s are expressions
=
A = rs*

Answer 2

晚上好！看看

b(aa)*b

这导致生成的字符串开始和结束于 b

并且包含偶数块 a 如果有的话以 2 的倍数产生 a 即偶数

语言 C={a,b} 上的正则表达式

Regular expression over the language C={a,b}

automata

dfa

regular-language

automata-theory

nsregularexpression