How to draw a DFA for complement of a regular language using a regular expression?

Question

How can I draw an FA for the complement of the language $L(r)$?

$L(r) = a^* (aba^*)^* b^* a^*$

I can draw an FA for $L(r)$ and convert to DFA and then take the complement, however it seems very long and I get stuck at the NFA to DFA conversion due to all the lambda transitions in my FA.

Answer 1

Well the general method is as you said. However, ad-hoc simplification may help:

$a^*(aba^*)^*b^*a^*$ = Has at most the last run of '$b$'s being of length more than $1$.

The complement would hence be:

$(a+b)^*bb^+(a+b)^*ab^+a^*$ = Has a run of '$b$'s that is not the last one and has length more than $1$.

You'd better check my reasoning, but I think you get the idea.

Answer 2

Hint. The minimal complete DFA of $L(r)$ has 5 states and four final states. A possible regular expression for its complement is $(a^+b)^*b^+a^+b(a+b)^*$.