字串運算

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

字串的字母表

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