RE: 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.

I tried to create a DFA which accepts such strings. My idea was to use all the remainders mod 6 and mod 8 leading to a total of 48 remainders. Thus each state in DFA is a pair (r, s) where r varies from 0 to 6 and s varies from 0 to 7. Start state (as well as accepting state) is (0, 0) and by we can easily give transitions to states by noting that if we input "a" the state (r, s) transitions to (r + 1, s) and on input "b" it transitions to state (r, s + 1).

However it is too difficult to work with a DFA of 48 states and I am not sure if this can be minimized by using the DFA minimization algorithm by hand.

I am really not sure how then we can get to a regular expression representing such strings.

Answer 1

If you are allowed to use lookaheads:

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

Debuggex Demo

Example of matched string: bbaabbaabbaabb

Idea is simple: We know how to match string having number of as divisible by 6 - ^((b*ab*){6})+$, also we know how to match string having number of bs divisible by 8 - ^((a*ba*){8})+$. So we just put one regex to lookahead, and another one to matching part.

In case if you also need to match strings consisting only of as or only of bs, then the following regex will do:

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

Examples of matched strings: aaaaaa, bbbbbbbb, bbaabbaabbaabb

Debuggex Demo