如何将生成0、1计数不等字符串的CFG转换为等价正则表达式

核心结论 #

你给出的CFG属于上下文无关文法，不是左/右线性的正则文法，它生成的是所有「0全在左侧、1全在右侧，且0的数量不等于1的数量」的非空01串，这类语言不存在等价的标准正则表达式（即对应有限状态自动机的正则表达式），因为有限状态机无法存储0和1的数量计数来做对比。

问题分析 #

1. 你推导的A、B的正则是正确的：
   • A → 0A | 0 等价于 0+（至少1个0）
   • B → 1B | 1 等价于 1+（至少1个1）
2. 产生式S → 0S1的作用是：每次递归可以在串的头部加1个0、尾部加1个1，展开后等价于可以套任意层0...1的配对，即最终S生成的串可以表示为0^n (0+ | 1+) 1^n，其中n ≥ 0：
   • 如果取括号内的0+分支，最终串为0^{n+m} 1^n（m≥1），也就是0的数量比1多至少1个
   • 如果取括号内的1+分支，最终串为0^n 1^{n+m}（m≥1），也就是1的数量比0多至少1个
3. 你之前写的正则0+0+1|0+1+1|1+|0+的问题是：只覆盖了0更多时1的数量为0或1、1更多时0的数量为0或1的情况，漏掉了类似0000111（0有4个、1有3个，0更多但1的数量大于1）这类场景。

扩展正则解决方案（PCRE/Perl 支持） #

如果使用支持代码断言的扩展正则引擎，可以实现匹配需求：

^(?!$|(0+)(1+)$(?{length $1 == length $2}))0*1*$

说明：

• ^(?!$) 排除空串
• (?!(0+)(1+)$(?{length $1 == length $2})) 排除0和1数量相等的串
• 0*1* 限定所有0在前、所有1在后

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