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:
- 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).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10064
