Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 11 down vote accepted

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).
share|cite|improve this answer

your answers look good.

To do this properly, it might helpful to convert the expression into the equivalent language (i.e., using English words to describe it), however, for certain expressions this language will be very complicated.

Another "algorithmic" way is to convert it to a DFA/NFA, and then check all the strings lexicographically, until you find one which is not accepted. The same can be done directly using the regular expression, but this might be somewhat more tricky at times.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.