重新編碼后語(yǔ)言和序列的性質(zhì).pdf

1、本文主要研究了重新編碼后的正則語(yǔ)言和序列的一些性質(zhì)。語(yǔ)言是定義在一個(gè)字母表上的字符串的集合。所謂對(duì)語(yǔ)言和序列進(jìn)行重新編碼是指按照一定的規(guī)則改變它們所依賴的字母表。正則語(yǔ)言是有限自動(dòng)機(jī)能夠識(shí)別的語(yǔ)言，也可定義為由正則文法產(chǎn)生的語(yǔ)言，這類語(yǔ)言在理論計(jì)算機(jī)領(lǐng)域有重要的應(yīng)用。Sturmian序列是定義在二元字母表上的具有最小復(fù)雜度的非最終周期序列，最早對(duì)Sturmian序列進(jìn)行研究的是Hedlund和Morse，現(xiàn)在的定義是1973年由Cove

2、n和Hedlend 給出的，這類序列在很多領(lǐng)域有著廣泛的應(yīng)用，例如：博弈論、自動(dòng)機(jī)、動(dòng)力系統(tǒng)、丟番圖逼近以及計(jì)算機(jī)圖形學(xué)等等。
　　 本文探討了把Sturmian序列從二元字母表轉(zhuǎn)換到三元字母表上的復(fù)雜度函數(shù)，還試著討論了把Tribonacci序列從三元字母表轉(zhuǎn)換到二元字母表上的復(fù)雜度函數(shù)。給出了經(jīng)過(guò)數(shù)制轉(zhuǎn)換后語(yǔ)言的正則性能否保持的一些條件。
　　 在預(yù)備章節(jié)里，我們介紹了語(yǔ)言、自動(dòng)機(jī)、正則語(yǔ)言和Sturmian序列的定