字符串運算

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

字符串的字母表

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

$\operatorname {Alph} (s)$

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

字符串代換

設 L 是一個語言，並設 $\Sigma$ 是它的字母表。字符串代換或簡稱代換是映射 f，它把 $\Sigma$ 中的字母映射到(可能有不同的字母表的)語言。比如，給定一個字母 $a\in \Sigma$，有 $f(a)=L_{a}$ 這裡的 $L_{a}\subset \Delta ^{*}$ 是其字母表為 $\Delta$ 的某個語言。這個定義可被擴展到字符串為

$f(\varepsilon )=\varepsilon$

對於空串 $\varepsilon$，和

$f(sa)=f(s)f(a)$

對於字符串 $s\in L$。字符串代換可以被擴展到整個語言為

$f(L)=\bigcup _{s\in L}f(s)$

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

字符串同態

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

$f^{-1}(s)=\{w\vert f(w)=s\}$

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

$f^{-1}(L)=\{s\vert f(s)\in L\}$

注意一般的說 $f(f^{-1}(L))\neq L$，然而確實有

$f(f^{-1}(L))\subseteq L$

和

$L\subseteq f^{-1}(f(L))$

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

字符串投影

如果 s 是字符串，而 $\Sigma$ 是字母表，s 的字符串投影是通過刪除不在 $\Sigma$ 中的所有字母結果的字符串。它被寫為 $\pi _{\Sigma }(s)\,$。它通過從右手端切除字母來得出形式定義:

$\pi _{\Sigma }(s)={\begin{cases}\varepsilon &{\mbox{if }}s=\varepsilon {\mbox{ the empty string}}\\\pi _{\Sigma }(t)&{\mbox{if }}s=ta{\mbox{ and }}a\notin \Sigma \\\pi _{\Sigma }(t)a&{\mbox{if }}s=ta{\mbox{ and }}a\in \Sigma \end{cases}}$

這裡的 $\varepsilon$ 指示空串。字符串的投影本質上同於關係代數中的投影。

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

$\pi _{\Sigma }(L)=\{\pi _{\Sigma }(s)\vert s\in L\}$

右商

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

$(sa)/b={\begin{cases}s&{\mbox{if }}a=b\\\varepsilon &{\mbox{if }}a\neq b\end{cases}}$

空串的右商可以是:

$\varepsilon /a=\varepsilon$

類似的，給出幺半群 $M$ 的子集 $S\subset M$，可以定義商子集為

$S/a=\{s\in M\vert sa\in S\}$

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

語法關係

幺半群 $M$ 的子集 $S\subset M$ 的右商定義了一個等價關係，叫做 S 的右語法關係。它給出為

$\sim _{S}\;\,=\,\{(s,t)\in M\times M\vert S/s=S/t\}$

關係明顯是有有限索引的(有有限數目個等價類)，當且僅當右商族有限的；就是說如果

$\{S/m\vert m\in M\}$

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

右取消

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

$(sa)\div b={\begin{cases}s&{\mbox{if }}a=b\\(s\div b)a&{\mbox{if }}a\neq b\end{cases}}$

空串總是可取消的:

$\varepsilon \div a=\varepsilon$

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

$\pi _{\Sigma }(s)\div a=\pi _{\Sigma }(s\div a)$

前綴

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

$\operatorname {Pref} _{L}(s)=\{t\vert s=tu{\mbox{ for }}u\in L\}$

語言的前綴閉包是

$\operatorname {Pref} (L)=\bigcup _{s\in L}\operatorname {Pref} _{L}(s)$

一個語言叫做前綴閉合的，如果 $\operatorname {Pref} (L)=L$。明顯的，前綴閉包算子是冪等的:

$\operatorname {Pref} (\operatorname {Pref} (L))=\operatorname {Pref} (L)$

前綴關係是二元關係 $\sqsubseteq$，有着 $s\sqsubseteq t$ 當且僅當 $s\in \operatorname {Pref} _{L}(t)$。

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

參見

• 字符串函數（C 語言）
• 字符串函數（C++）
• Levi引理

引用

• 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.)