Search code examples
algorithmparsingstring-matchingformal-languageskleene-star

When is the Kleene star of a finite language free?

I'm looking for references that give an algorithm to solve this problem:

Problem: Given a finite alphabet Σ and a finite language L ⊆ Σ* , determine whether L* is a free monoid.

Equivalently, the problem is to determine, given a finite set of strings, whether every concatenation of these strings is uniquely decomposable using the same strings. For example, any language whose strings are all the same size will satisfy this condition, as will the language L = {a, ba}, but the language L = {ab, ba, aba} does not satisfy the condition because the string ababa can be decomposed as either ab aba or aba ba.

Solution

  • This problem is equivalently stated as: when is L a code over Σ?

    The standard algorithm for determining this is the Sardinas-Patterson algorithm, published in 1953.

    There is an interesting discussion in the book review by Juhani Karhumäki (Bulletin of the AMS, vol. 17 no. 1, pp. 161-167, 1987) of Berstel and Perren's Theory of Codes (Pure and Applied Mathematics vol. 117, Academic Press, NY, 1985.)