2

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

我认为表达方式比我的要容易得多，

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

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

我试过这样的事情：bb*(阿巴)*(aab)*(aa)*(aab)*(阿巴)*b*b

但我认为这并不完整。

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

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

4

2 回答 2

2

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

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

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

如果我们看到bin q0，我们需要一个新的状态来表示我们正在顺利看到符合标准的字符串这一事实。实际上，字符串b以 a 开头和结尾，b并且有偶数个a（零是偶数）；所以这个状态一定是接受的。打电话给这个q2。

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

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

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

如果 inq4并且我们看到一个a，我们又需要更多a的 s 并且可以返回到q3。另一方面，如果我们得到 a b，我们可以返回，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*
  1. 该bb*部分对任何字符串都是语言中的字符串这一事实进行编码b。
  2. 另一部分开始和结束于bb*which 编码任何字符串必须开始和结束的事实b
  3. 最外层的 s 编码语言中的任何字符串都必须有第一个和最后一个a的事实aa
  4. 这些aab*部分允许有连续的对a
  5. 该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*
于 2018-10-29T13:36:54.497 回答
1

晚上好 ！一探究竟

b(aa)*b

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

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

于 2019-03-03T19:07:36.220 回答