跳至內容

字串運算

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

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

字串的字母表

字串的字母表是在一個特定字串中出現的所有字母的列表。如果 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.)