電腦科學領域形式語言理論中,經常用到各種字串函數;但是符號不同於電腦編程中所用到的,某些在理論領域中常用的函數,在編程中很少用到。本文定義其中一些基本術語。

字串的字母表

編輯

字串的字母表是在一個特定字串中出現的所有字母的列表。如果 s 是字串,則它的字母表指示為

 

這可以等價地認為是先把字串中的所有字母按照給定的順序排好,再去掉其中重複者。

字串代換

編輯

L 是一個語言,並設   是它的字母表。字串代換或簡稱代換是對映 f,它把   中的字母對映到(可能有不同的字母表的)語言。比如,給定一個字母  ,有   這裏的   是其字母表為   的某個語言。這個定義可被擴充到字串為

 

對於空字串  ,和

 

對於字串  。字串代換可以被擴充到整個語言為

 

字串代換的一個例子出現在正則語言中,它閉合於字串代換之下。就是說,如果一個正規語言的字母被另一個正規語言所代換,結果仍是正規語言。

字串同態

編輯

字串同態是使得每個字母被替代為一個單一字串的字串代換。就是說, ,這裏的 s 是字串,對於每個字母 a。字串同態是保持字串連接二元運算同態。給定一個語言 L  的集合叫做 L同態像。字串 s逆同態像被定義為

 

而語言 L 的逆同態像被定義為

 

注意一般的說  ,然而確實有

 

 

對於任何語言 L。簡單單一字母置換密碼是字串代換的例子。

字串投影

編輯

如果 s 是字串,而   是字母表,s字串投影是通過刪除不在   中的所有字母結果的字串。它被寫為  。它通過從右手端切除字母來得出形式定義:

 

這裏的   指示空字串。字串的投影本質上同於關係代數中的投影。

字串投影可以提升為語言的投影。給定形式語言 L,它的投影給出自

 

右商

編輯

字串 s 與字母 a右商是在字串 s 中切斷右手端字母 a 得到的字串。它被指示為  。如果字串在右手端沒有 a,則結果是空字串。就是:

 

空字串的右商可以是:

 

類似的,給出么半群   的子集  ,可以定義商子集為

 

左商可以類似的定義,運算發生在字串的左端。

語法關係

編輯

么半群   的子集   的右商定義了一個等價關係,叫做 S語法關係。它給出為

 

關係明顯是有有限索引的(有有限數目個等價類),若且唯若右商族有限的;就是說如果

 

是有限的。在這種情況下,S可辨識語言,就是說可被有限狀態自動機辨識的語言。這個在語法么半群中詳細討論。

右取消

編輯

字串 s 與字母 a右取消是切除字串 s 右手端的字母 a 的首次出現得到的字串。它被指示為   並被遞歸的定義為

 

空字串總是可取消的:

 

明顯的,右取消和投影可交換:

 

字首

編輯

字串的字首是關於給定語言一個字串的所有字首的集合:

 

語言的字首閉包

 

一個語言叫做字首閉合的,如果  。明顯的,字首閉包算子是冪等的:

 

字首關係二元關係  ,有着   若且唯若  

字首文法生成(關於這個文法)字首閉合的語言。

參見

編輯

參照

編輯
  • John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 3.)