{a,b}上含等量a、b的语言正则性判断：为何选项C不正确？

设L是字母表{a,b}上包含相同数量a和b的语言，以下是各选项的正则性判断及选项C的错误原因：

正确选项：D. L ∪ (a*b*)* #

(a*b*)*其实就是字母表{a,b}上的所有字符串——因为a*b*能生成任意先a后b的字符串，再取闭包就覆盖了所有由a、b组成的串。所以L ∪ (a*b*)*等价于所有字符串的集合，而所有字符串的集合是正则语言，只需要一个简单的有限自动机就能识别：不管输入什么字符，都停留在接受状态就行。

其他选项分析 #

• 选项A：L ∩ a*b*
  这个语言里的字符串都是先全是a、后全是b，而且a和b的数量相等，也就是形如a^n b^n（n≥0）的串。要识别这种串，必须记录a的数量，再匹配对应的b的数量，但有限自动机的状态数是有限的，没法存下无限多的计数，所以它不是正则语言。

• 选项B：L ∪ a*b*
  这个语言包含两类串：一类是先a后b的任意串（a*b*），另一类是a和b数量相等的任意串（L）。要判断一个串是否属于这个语言，要么看它是不是先a后b，要么看它的a、b数量是否相等——但后者需要计数，有限自动机做不到，所以这个语言不是正则语言。

• 选项C：L ∩ (a*b*)*
  前面说了(a*b*)*是所有字符串的集合，所以这个交集其实就是L本身。而L是需要统计a和b数量是否相等的语言，有限自动机没法完成这种无限计数的任务，因此L不是正则语言，选项C对应的语言自然也不是正则语言。

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