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

Problem Detail: 

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?

Asked By : badjr

Answered By : Dan

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:

1. Convert the regular expression to a nondeterministic finite automaton.
2. Convert the nondeterministic automaton into a deterministic one.
3. Use a breadth first search until you encounter the first nonfinal state (if there is one at all).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10064