Regular expression of string of a, b that doesn't contain aa

Question

Using only parenthesis and * symbol, one example that comes in my mind is

((a|b)(bb*))*

but I can have a string for example abba that the last letter is a, which is not included in this... Any ideas?

Answer 1

Here is the DFA:

Use the method described here to derive and solve the equation for R1 (the initial state):

R1 = bR1 + aR2 + λ
R2 = bR1 + λ

Substitute R2 to R1:

R1 = bR1 + abR1 + a + λ

Apply the Arden's theorem:

R1 = (b + ab)*(a + λ)

The rest is change the syntax a bit:

(b|ab)*(a|)

This can be rewritten to regex in Perl-syntax for testing:

^(a?b)*a?$