无限强码

设Σ~*是(有限)字母表Σ生成的自由么半群。Σ的元素称为字母,Σ~*的元素和子集分别称作Σ上的字和语言。Σ~*的恒等元称为空字,记作∧,且记Σ~+=Σ~*-{∧}。关于Σ上任何字x,用lg(x)表示x中出现的字母的个数,叫做x的长度。