重新編碼后語言和序列的性質.pdf

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

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