字符串运算

Template:TA 在计算机科学领域形式语言理论中，经常用到各种字符串函数；但是符号不同于计算机编程中所用到的，某些在理论领域中常用的函数，在编程中很少用到。本文定义其中一些基本术语。

字符串的字母表

字符串的字母表是在一个特定字符串中出现的所有字母的列表。如果 s 是字符串，则它的字母表指示为

$\mathrm{Alph}(s)$

这可以等价地认为是先把字符串中的所有字母按照给定的顺序排好，再去掉其中重复者。

字符串代换

设 L 是一个语言，并设 $\mathrm{\Sigma }$ 是它的字母表。字符串代换或简称代换是映射 f，它把 $\mathrm{\Sigma }$ 中的字母映射到(可能有不同的字母表的)语言。比如，给定一个字母 $a\in \mathrm{\Sigma }$，有 $f(a)=L_a$ 这里的 $L_a\subset {\mathrm{\Delta }}^{*}$ 是其字母表为 $\mathrm{\Delta }$ 的某个语言。这个定义可被扩展到字符串为

$f(\epsilon )=\epsilon$

对于空串 $\epsilon$，和

$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|f(w)=s\}$

而语言 L 的逆同态像被定义为

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

注意一般的说 $f(f^{-1}(L))\ne L$，然而确实有

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

和

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

对于任何语言 L。简单单一字母置换密码是字符串代换的例子。

字符串投影

如果 s 是字符串，而 $\mathrm{\Sigma }$ 是字母表，s 的字符串投影是通过删除不在 $\mathrm{\Sigma }$ 中的所有字母结果的字符串。它被写为 ${\pi }_{\mathrm{\Sigma }}(s)$。它通过从右手端切除字母来得出形式定义:

${\pi }_{\mathrm{\Sigma }}(s)=\{\begin{array}{cc}\epsilon & \text{if }s=\epsilon \text{ the empty string}\\ {\pi }_{\mathrm{\Sigma }}(t)& \text{if }s=ta\text{ and }a\notin \mathrm{\Sigma }\\ {\pi }_{\mathrm{\Sigma }}(t)a& \text{if }s=ta\text{ and }a\in \mathrm{\Sigma }\end{array}$

这里的 $\epsilon$ 指示空串。字符串的投影本质上同于关系代数中的投影。

字符串投影可以提升为语言的投影。给定形式语言 L，它的投影给出自

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

右商

字符串 s 与字母 a 的右商是在字符串 s 中切断右手端字母 a 得到的字符串。它被指示为 $s/a$。如果字符串在右手端没有 a，则结果是空串。就是:

$(sa)/b=\{\begin{array}{cc}s& \text{if }a=b\\ \epsilon & \text{if }a\ne b\end{array}$

空串的右商可以是:

$\epsilon /a=\epsilon$

类似的，给出幺半群 $M$ 的子集 $S\subset M$，可以定义商子集为

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

左商可以类似的定义，运算发生在字符串的左端。

语法关系

幺半群 $M$ 的子集 $S\subset M$ 的右商定义了一个等价关系，叫做 S 的右语法关系。它给出为

${\sim }_S=\{(s,t)\in M\times M|S/s=S/t\}$

关系明显是有有限索引的(有有限数目个等价类)，当且仅当右商族有限的；就是说如果

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

是有限的。在这种情况下，S 是可识别语言，就是说可被有限状态自动机识别的语言。这个在语法幺半群中详细讨论。

右取消

字符串 s 与字母 a 的右取消是切除字符串 s 右手端的字母 a 的首次出现得到的字符串。它被指示为 $s÷a$ 并被递归的定义为

$(sa)÷b=\{\begin{array}{cc}s& \text{if }a=b\\ (s÷b)a& \text{if }a\ne b\end{array}$

空串总是可取消的:

$\epsilon ÷a=\epsilon$

明显的，右取消和投影可交换:

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

前缀

字符串的前缀是关于给定语言一个字符串的所有前缀的集合:

${\mathrm{Pref}}_L(s)=\{t|s=tu\text{ for }u\in L\}$

语言的前缀闭包是

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

一个语言叫做前缀闭合的，如果 $\mathrm{Pref}(L)=L$。明显的，前缀闭包算子是幂等的:

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

前缀关系是二元关系 $⊑$，有着 $s⊑t$ 当且仅当 $s\in {\mathrm{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.)