String of minimum length in $\{a, b\}^*$ not in a regular expression

I'm doing an exercise in my book, the question is to find a string of minimum length in $\{a, b\}^*$ not in the language corresponding to the given regular expression.

a. $b^(ab)^a^*$

My answer: $aab$

b. $(a^ + b^)(a^ + b^)(a^ + b^)$

My answer: $abab$

c. $a^(baa^)^b^$

My answer: $bba$

d. $b^(a + ba)^b^*$

My answer: $abba$

I came up with my answers by trial and error. I don't know for sure if these are the shortest possible strings. Is the best method trial and error, or would there be some better algorithmic way?

First, the string of minimum length might not be defined properly since it might not be unique.

Here is a way to find a string of minimum length:

• Convert the regular expression to a nondeterministic finite automaton.

• Convert the nondeterministic automaton into a deterministic one.

• Use a breadth first search until you encounter the first nonfinal state (if there is one at all).

StackExchange Computer Science Q#10064, answer score: 11