在计算机科学领域形式语言理论中，经常用到各种字符串函数；但是符号不同于计算机编程中所用到的，某些在理论领域中常用的函数，在编程中很少用到。本文定义其中一些基本术语。
字符串的字母表
字符串的字母表是在一个特定字符串中出现的所有字母的列表。如果 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))\ne 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 \ne 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 \ne 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.)
评论 (0)