Confusion about the generating function for a regular expression

Question

Given a regex A = (a*b)*, I want to compute the Generating Function that enumerate this regex.

The formula for the GF of that regex is 1/(1-z/(1-z)) = (1-z)/(1-2z). Then I can compute the sequence that this GF represents is a(n) = 2^n - 2^(n-1). Based on that, I can compute that the number of 3-character strings that match regex A is a(3) = 4. However, I can only list 2 of them which are aab, bbb. I tried with 4 and 5-character strings and that does not feel right as well.

So my question is, am I misunderstanding anything here? If yes, I would be happy if you point it out.

Thank you,

Answer 1

Hint:

• Let $A = (a^*b)^*$ and $A' = \Sigma^* \setminus A$ (i.e. the complement of $A$).
• Observe that any word $w$ that ends with the letter $b$ belongs to $A$.
• Observe that $A' = \Sigma^*a$.

I hope this helps $\ddot\smile$