查看“字符串运算”的源代码

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

==字符串的字母表==
'''字符串的字母表'''是在一个特定字符串中出现的所有字母的列表。如果 ''s'' 是字符串，则它的[[字母表 (计算机科学)|字母表]]指示为

:<math>\operatorname{Alph}(s)</math>

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

==字符串代换==

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

:<math>f(\varepsilon)=\varepsilon</math>

对于[[空串]] <math>\varepsilon</math>，和

:<math>f(sa)=f(s)f(a)</math>

对于字符串 <math>s\in L</math>。字符串代换可以被扩展到整个语言为

:<math>f(L)=\bigcup_{s\in L} f(s)</math>

字符串代换的一个例子出现在[[正则语言]]中，它闭合于字符串代换之下。就是说，如果一个正规语言的字母被另一个正规语言所代换，结果仍是正规语言。

==字符串同态==

'''字符串同态'''是使得每个字母被替代为一个单一字符串的字符串代换。就是说，<math>f(a)=s</math>，这里的 ''s'' 是字符串，对于每个字母 ''a''。字符串同态是保持[[串接|字符串连接]][[二元运算]]的[[同态]]。给定一个语言 ''L''，<math>f(L)</math> 的集合叫做 ''L'' 的'''同态像'''。字符串 ''s'' 的'''逆同态像'''被定义为 

:<math>f^{-1}(s)=\{w\vert f(w)=s\}</math>

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

:<math>f^{-1}(L)=\{s\vert f(s)\in L\}</math>

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

:<math>f(f^{-1}(L)) \subseteq L</math> 

和 

:<math>L \subseteq f^{-1}(f(L))</math>

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

==字符串投影==

如果 ''s'' 是字符串，而 <math>\Sigma</math> 是字母表，''s'' 的'''字符串投影'''是通过删除不在 <math>\Sigma</math> 中的所有字母结果的字符串。它被写为 <math>\pi_\Sigma(s)\,</math>。它通过从右手端切除字母来得出形式定义:

:<math>\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}</math>

这里的 <math>\varepsilon</math> 指示[[空串]]。字符串的投影本质上同于[[关系代数 (数据库)|关系代数]]中的投影。

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

:<math>\pi_\Sigma (L)=\{\pi_\Sigma(s) \vert s\in L \}</math>

==右商==

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

:<math>(sa)/ b = \begin{cases} 
s & \mbox{if } a=b \\
\varepsilon & \mbox{if } a \ne b
\end{cases}</math>

空串的右商可以是:

:<math>\varepsilon / a = \varepsilon</math>

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

:<math>S/a=\{s\in M \vert sa\in S\}</math>

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

==语法关系==

幺半群 <math>M</math> 的子集 <math>S\subset M</math> 的右商定义了一个[[等价关系]]，叫做 ''S'' 的'''右[[语法关系]]'''。它给出为

:<math>\sim_S \;\,=\, \{(s,t)\in M\times M \vert S/s = S/t \}</math>

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

:<math>\{S/m \vert m\in M\}</math>

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

==右取消==

字符串 ''s'' 与字母 ''a'' 的'''右取消'''是切除字符串 ''s'' 右手端的字母 ''a'' 的首次出现得到的字符串。它被指示为 <math>s\div a</math> 并被递归的定义为

:<math>(sa)\div b = \begin{cases} 
s & \mbox{if } a=b \\
(s\div b)a & \mbox{if } a \ne b
\end{cases}</math>

空串总是可取消的:

:<math>\varepsilon \div a = \varepsilon</math>

明显的，右取消和投影[[交换律|可交换]]:

:<math>\pi_\Sigma(s)\div a = \pi_\Sigma(s \div a )</math>

==前缀==

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

:<math>\operatorname{Pref}_L(s) = \{t \vert s=tu \mbox { for } u\in L\}</math>

'''语言的前缀闭包'''是 

:<math>\operatorname{Pref} (L) = \bigcup_{s\in L} \operatorname{Pref}_L(s)</math>

一个语言叫做'''前缀闭合'''的，如果 <math>\operatorname{Pref} (L) = L</math>。明显的，前缀闭包算子是[[幂等律|幂等]]的:

:<math>\operatorname{Pref} (\operatorname{Pref} (L)) =\operatorname{Pref} (L)</math>

'''前缀关系'''是[[二元关系]] <math>\sqsubseteq</math>，有着 <math>s\sqsubseteq t </math> 当且仅当 <math>s \in \operatorname{Pref}_L(t)</math>。 

[[前缀文法]]生成(关于这个文法)前缀闭合的语言。

==参见 ==
* [[string.h|字符串函数（C 语言）]]
* [[string (C++标准库)|字符串函数（C++）]]
* [[Levi引理]]

== 引用 ==
<references/>
* 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.)''

[[Category:形式语言|Z]]
[[Category:关系代数|Z]]
[[Category:字符串]]