Regular expression for strings containing a's in multiples of 3

Question

Can someone please tell me how to generate a regular expression for strings in which number of a's is a multiple of 3? The alphabet set is {a,b}.

I tried to construct a DFA for it first and then derive a RE from that. What I got was ((ba*)(ba*)(ba*))*.

Answer 1

For those asking the inverse DFA, i.e., accepts the language 𝐿={𝑤∈{𝑎,𝑏}^∗ ∣ prevents the number of '𝑎's to be a multiple of 3}

the answer would be
b^∗+(b^∗ab^∗ab^∗ab*)^∗a+(b^∗ab^∗ab^∗ab*)^∗aa

This regular expression matches strings over the alphabet {a, b} where:

• b* represents zero or more occurrences of 'b'.
• (b*ab*ab*ab*)*a represents zero or more occurrences of the pattern 'b', followed by one 'a', followed by zero or more 'b's, repeated three times, followed by one 'a'.
• (b*ab*ab*ab*)*aa represents zero or more occurrences of the pattern 'b', followed by one 'a', followed by zero or more 'b's, repeated three times, followed by two 'a's

, covering all possible combinations of non-multiple-of-3 'a's (3n+1,3n+2).

Answer 2

My answer would be ((b*)a(b*)a(b*)a(b*))*

Answer 3

I would write the pattern as:

^b*(?:(?:ab*){3})*$

This matches:

• ^ from the start of the string
• b* optional leading b zero or more times
• (?:
  • (?:ab*){3} match a followed by zero or more b 3 times
• )* match this group zero or more times
• $ end of the string

Demo