我正在寻找提供解决此问题的算法的参考资料：
问题：给定一个有限字母 Σ 和一个有限语言 L ⊆ Σ *，确定 L *是否是一个自由幺半群。
等效地，问题是确定给定一组有限的字符串，这些字符串的每个连接是否可以使用相同的字符串唯一地分解。例如，任何字符串大小相同的语言都会满足这个条件，语言 L = {a, ba} 也会满足这个条件，但是语言 L = {ab, ba, aba} 不满足条件，因为字符串ababa可以被分解为ab aba或aba ba。
问问题
481 次
1 回答
3
这个问题等价地表述为：什么时候L是Σ上的代码？
确定这一点的标准算法是 1953 年发布的Sardinas-Patterson 算法。
Berstel and Perren's Theory of Codes (Pure and Applied Mathematics vol. 117, Academic纽约出版社，1985 年。）
于 2015-03-11T07:29:41.013 回答