Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Star-free decomposition of regular language given by regular expression

, ,
Problem Detail:

I was wondering: is there an algorithm to decompose any regular expression, provided it doesn't use complementation, into one or more regular expressions which don't use Kleene star (only catenation and union).

Right now I'm reading On the Decomposition of Finite Languages by A. Mateescu, A. Salomaa and S. Yu, but this paper doesn't seem to discuss this problem, but that's where I get the idea.

No. If the regular expression encodes an infinite language, then there is no way to decompose it that way. Without the Kleene star, regular expressions can only express finite languages.

I realize this is a rather trivial answer, and it begs the next question: what if we are promised that the language is finite? In that case, the answer is yes. Here are two ways to see that the answer is yes:

Approach #1: Since the language is regular, we can find a DFA that recognizes it -- let's choose the minimal DFA. Since the language is finite, this DFA will not have any loops in it. Now if you apply the standard algorithm for converting a DFA to a regular expression, the result is a star-free regular expression. In fact, you get out only a single regular expression.

Approach #2: If the language is finite, then you can enumerate all of the words in the language, say \$L=\{w_1,w_2,\dots,w_n\}\$. Therefore \$w_1 + w_2 + \dots + w_n\$ is a regular expression for \$L\$.

Credit: The answer for the case where the language is finite is due to @J.E. Pin.