跳至內容

字符串運算

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

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

字符串的字母表

[編輯]

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