regex - 回复 : Number of a's is divisible by 6 and Number of b's is divisible by 8

Question

Find a regular expression which represents strings made of {a, b}, where number of a's is divisible by 6 and number of b's is divisible by 8.

我试图创建一个接受此类字符串的 DFA。我的想法是使用所有余数模 6 和模 8 导致总共 48 个余数。因此，DFA 中的每个状态都是一对 (r, s)，其中 r 从 0 到 6 变化，s 从 0 到 7 变化。开始状态(以及接受状态)是 (0, 0) 并且通过注意如果我们输入 "a" 状态 ，我们可以很容易地转换到状态>(r, s) 转换为 (r + 1, s) 并在输入 "b" 时转换为状态 (r, s + 1)。

但是，使用 48 个状态的 DFA 太难了，我不确定是否可以通过手动使用 DFA 最小化算法将其最小化。

我真的不确定我们如何才能得到表示此类字符串的正则表达式。

Answer 1

如果您被允许使用前瞻:

^(?=b*((ab*){6})+$)a*((ba*){8})+$

Debuggex Demo

匹配字符串示例:bbaabbaabbaabb

想法很简单:我们知道如何匹配 a 数可被 6 整除的字符串 - ^((b*ab*){6})+$ ，我们也知道如何匹配 b 数可被 8 整除的字符串 - ^((a*ba*){8})+$。所以我们只是将一个正则表达式用于前瞻，将另一个正则表达式用于匹配部分。

如果您还需要匹配仅由 a 或仅由 b 组成的字符串，则以下正则表达式即可:

^(?=b*((ab*){6})*$)a*((ba*){8})*$

匹配字符串的例子:aaaaaa, bbbbbbbb, bbaabbaabbaabb

Debuggex Demo