regex - 奇数个 a 的正则表达式

Question

我在解决以下练习时遇到问题，希望得到任何帮助。

设 Σ = {a,b}。我需要为包含奇数 a 的所有字符串提供一个正则表达式。

感谢您的时间

Answer 1

b*(ab*ab*)*ab*

它的主要部分是 (ab*ab*)* , 列举了 a 偶数的所有可能性s。最后，一个额外的 a必须存在才能使它变得奇怪。

请注意，此正则表达式等效于:

b*a(b*ab*a)*b*

这两个结构采用泵引理定义的形式:

http://en.wikipedia.org/wiki/Pumping_lemma

更新:

@MahanteshMAmbi 表达了他对匹配大小写的正则表达式的担忧 aaabaaa .事实上，事实并非如此。如果我们运行 grep ，我们将清楚地看到匹配的内容。

$ echo aaabaaa | grep -P -o 'b*(ab*ab*)*ab*'
aaabaa
a

-o grep 的选项将在每一行打印每个匹配的实例。在这种情况下，正如我们所看到的，正则表达式被匹配了两次。 1 匹配 5 a s, 一个匹配 1 a .我下面评论中的看似错误是由不正确的测试用例引起的，而不是正则表达式中的错误。

如果我们想让它在现实生活中严格使用，那么在表达式中使用 anchor 来强制完整的字符串匹配可能会更好:

^b*(ab*ab*)*ab*$

所以:

$ echo aaabaaa | grep -P -q '^b*(ab*ab*)*ab*$'
$ echo $?
1