關(guān)于語言的可交換性質(zhì)的研究.pdf

1、設(shè)A是一個字母表。如果語言X,Y(C)A*滿足XY=YX，則稱X，Y是可交換的。如果語言X，Y(C)A*滿足XY(C)YX或YX(C)XY，則稱X，Y是部分可交換的。目前已知:在自由半群A*上，若x，y∈A+，xy=yx，則存在t∈A+，m，n＞0，使得x=tm，y=tn。但上面的x,y換成可交換或部分可交換的語言（即A*的子集）時，情況就非常不同了。
　　本文首先對碼在可交換和部分可交換下的性質(zhì)進行了系統(tǒng)的研究。在碼的可交換性質(zhì)

2、和非模糊集的關(guān)系方面，證明了:對于任意一個碼，若它與一個語言可交換，則它們的積是非模糊的。在碼的可交換性質(zhì)和極大碼的關(guān)系方面，證明了:與A*可部分交換的碼是極大碼。并且證明了:若X(C)A+是碼，則X與A*可交換當且僅當存在正整數(shù)n，使得X=An。對于B.Ratoandromanana在上個世紀80年代末提出的猜想“任意一個碼都存在唯一的本原根”，本文運用碼的可交換性質(zhì)給出了一個等價刻劃，為解決該猜想提供了新的途徑。
　　本文還對

3、一般語言的可交換性質(zhì)進行了研究，著重分析和討論了與一個語言可交換的不包含空字的最大語言（即該語言的中心化子）的性質(zhì)。證明了中心化子為有限生成的界限確實存在，即存在一個正整數(shù)n，使得:基數(shù)不超過n的語言的中心化子都是有限生成的，而對于任何大于n的正整數(shù)m，總存在中心化子不是有限生成的m元語言。為了進一步討論中心化子為有限生成的界限問題，本文提出了二元奇異語言的概念，并且運用二元奇異語言的相關(guān)性質(zhì)給出了關(guān)于四元語言中心化子的若干結(jié)論，證明了