正则表达式 - 使其具有偶数个 b，我只能使用符号 + 和 *

Question

我正在尝试为字母表 {a,b} 编写以下语言的正则表达式。所有包含偶数个 b 的字符串

从我能使用的来看，我只能使用符号+和*

我尝试做

(a*(bb)*a*)*

看看这是否有效，但我不确定我是否正确？有人可以帮助我吗？

Answer 1

我不确定我是否正确？

这是不正确的，因为它只接受具有

b

的输入，当它们出现在相邻对中时。您应该允许这些配对的

b

字符之间有零个或多个

a

。

此外，您不应该有像

a*

一样重复

a*a*

的模式序列，这就是当您的外部组重复时会发生的情况。当您真正实现该正则表达式时，这可能会导致指数执行时间。

例如，这代表语言：

(a*(ba*b))*a*