regex - a 和 b 的数量相同，但从左到右阅读时，一个字母比另一个字母多三个

Question

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

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

例如：

• aaa不是有效的（因为有 3a个多于b's）
• aa无效（a's 和b's 的数量不同）
• aababb是有效的（a's 和's 的数量相同，并且's 或's 的b累积数量永远不会比另一个多三个）ab
• [空字符串] 有效
• bbaabbaa已验证

Answer 1

have the same number of a's and b's如果只有第一个约束 ( ) 是不可能的。由于第二个约束，您的问题有一个解决方案。

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

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