咨询判定X、Y两种给定语言是否属于正则语言的相关问题

语言X #

X是正则语言，你的猜测正确：含奇数个a的字符串集合确实属于正则语言。

• 可以通过双状态DFA直接识别：
  • 初始状态q0：表示已读取到偶数个a，为非接受态
  • 接受状态q1：表示已读取到奇数个a
  • 转移规则：读取到字符a时在两个状态间切换，读取到其他字符时保持当前状态不变
• 也可写出对应的正则表达式：^([^a]*a[^a]*a)*[^a]*a[^a]*$，完全匹配所有符合要求的字符串

语言Y #

你通过泵引理得到的Y为非正则语言的结论成立，这类需要对等计数的语言超出了正则语言的表达能力边界，有限自动机无法存储任意长度的计数信息，无法识别这类结构。

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