基于Σ={a,b}的正则表达式求解：两类语言的精确定义

(a) L1：包含恰好一个b且可包含任意数量a的语言 #

对应的正则表达式是：a*ba*

逻辑解释： #

• a*：匹配任意数量（包括0个）的a，对应b前面的所有a；
• b：必须且只能匹配一个b，严格保证字符串里恰好有一个b；
• 末尾的a*：匹配任意数量（包括0个）的a，对应b后面的所有a。

这个表达式能覆盖所有符合要求的字符串，比如b、ab、ba、aaabaaa等等。

(b) L2：包含偶数个a和偶数个b的语言 #

对应的正则表达式是：((aa|bb)|(ab|ba)(aa|bb)*(ab|ba))*

逻辑解释： #

这个表达式的核心是全程保持a和b的数量为偶数，拆解来看：

• (aa|bb)：直接添加两个相同的字符，a或b的数量增加2，奇偶性不变（偶数+2还是偶数）；
• (ab|ba)(aa|bb)*(ab|ba)：
  1. 先用(ab|ba)添加一对不同的字符，此时a和b的数量各加1，都变成奇数；
  2. 中间的(aa|bb)*可以添加任意数量的成对相同字符，保持a和b的奇偶性仍为奇数；
  3. 最后再用(ab|ba)添加一对不同的字符，让a和b的数量各再加1，回到偶数；
• 外层的*表示可以重复任意次上述两种操作，包括0次（对应空字符串，空字符串的a和b数量都是0，属于偶数）。

这个表达式能匹配所有符合要求的字符串，比如空串、aa、bb、abab、aabb、abba等等。

内容的提问来源于stack exchange，提问作者Sid