Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers

up vote 10 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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.