regex - 从左到右阅读时，a 和 b 的数量相同，但一个字母的数量不得超过另一个字母的三个以上

Question

我能否获得有关如何为字母表 {a, b} 构造正则表达式的提示，该表达式接受以下所有字符串:

1. 具有相同数量的 a 和 b。
2. 从左到右读取字符串，a 和 b 的数量之差永远不会大于 2。

例如:

• aaa 无效(因为 a 比 b 多 3 个)
• aa 无效(a 和 b 的数量不同)
• aabbab 有效(a 和 b 的数量相同，且 a 的累计数量>'s 或 b's 永远不会比另一个多三个)
• [空字符串]有效
• bbaabbaa 有效

Answer 1

如果只有第一个约束(具有相同数量的 a 和 b)，这是不可能的。由于第二个约束，您的问题有一个解决方案。

首先考虑完成您的工作的有限自动机(我将其留给您作为练习)然后将其转换为正则表达式会更容易。

转换后的正则表达式将是: [ (((a | (aab) (ab)*) b)* (((b | bba) (ba)*) a)* ]* (也许可以简化，也可以留下作为练习)。