正则表达式查找a和b的所有字符串,其中包含偶数个和偶数个b？

Question

是否可以使用正则表达式计算字符串中出现字符的次数？可以给出任何正则表达式来查找a和b的所有字符串,其中包含偶数个和偶数个b吗？

Answer 1

有一个足够简单的有限状态机:它有四种状态:s00,s01,s10和s11,具体取决于你是消耗了偶数还是奇数的as以及偶数或奇数个bs.开始状态(也是结束状态)是通过消耗偶数个as和bs 达到的状态.转换函数如下所示:

d(s00, a) = s10
d(s00, b) = s01
d(s10, a) = s00
d(s10, b) = s11
d(s01, a) = s11
d(s01, b) = s00
d(s11, a) = s01
d(s11, b) = s10

我们可以消除国家s11:

d(s00, a)  = s10
d(s00, b)  = s01
d(s10, a)  = s00
d(s10, ba) = s11
d(s10, bb) = s10
d(s01, b)  = s00
d(s01, aa) = s01
d(s01, ab) = s10

通过跟踪通过返回到开始状态的FSM的所有可能路径,我们可以开发一个没有前瞻的正则表达式,并重复:

( a (bb|ba(aa)*ab)* (a|ba(aa)*b) | b (aa|ab(bb)*ba)* (b|ab(bb)*a) )*

(插入无意义的空白以帮助我跟踪括号的嵌套.)这个想法是,如果第一个字符是a你到达s10; 然后你可以转换到s10和s01重复通过(bb|ba(aa)*ab)*,最后返回s00(不重复s10)via a或via ba(aa)*b.类似的模式(只是交换的发生a和b)让你从s00回到s00通过与开头的字符串b.你可以使尽可能多的行程并返回到s00你喜欢的开始无论是a或b.