形式陈述

字母表 $\Sigma$$\mathrm{\Sigma }$ 上长度为 $n$$n$ 的字（字符串）是有限序列

$$ w=w_1w_2\cdots w_n, \qquad w_i\in\Sigma, $$$$w=w_1{w}_2\cdots w_n,w_i\in \mathrm{\Sigma },$$

等价地是函数 $w:\{1,\ldots,n\}\to\Sigma$$w:\{1,\dots ,n\}\to \mathrm{\Sigma }$。其长度记 $|w|=n$$|w|=n$。长度为零时位置集为空，存在唯一空函数，对应空字 $\varepsilon$$\epsilon$。所有有限字构成

$$ \Sigma^*=\bigcup_{n\ge0}\Sigma^n, $$$${\mathrm{\Sigma }}^{\ast }=\bigcup _{n\ge 0}{\mathrm{\Sigma }}^n,$$

长度正的字构成 $\Sigma^+=\bigcup_{n\ge1}\Sigma^n$${\mathrm{\Sigma }}^{+}=\bigcup _{n\ge 1}{\mathrm{\Sigma }}^n$。

直觉

字是按顺序排好的有限符号，而不是符号集合：重复次数和位置都保留。空字是“没有符号的唯一序列”，仍是合法对象。

例子与边界

在 $\Sigma=\{0,1\}$$\mathrm{\Sigma }=\{0,1\}$ 上，$001$$001$ 与 $010$$010$ 不同，且 $|001|=3$$|001|=3$。空字 $\varepsilon$$\epsilon$ 不属于字母表，除非有人刻意把一个同名印刷符号加入 $\Sigma$$\mathrm{\Sigma }$；作为空序列时它长度为零。字与自然语言中的“单词”无关，可包含任意有限数量符号。无限序列属于 $\Sigma^\omega$${\mathrm{\Sigma }}^{\omega }$ 等另一类对象，不在 $\Sigma^*$${\mathrm{\Sigma }}^{\ast }$ 中。集合表示会丢失顺序和重数，因此不能把字定义成字母表的有限子集。

推论与应用

字是自动机输入、编码对象和形式语言元素；长度提供归纳、运行时间和泵引理中的基本规模参数。

参考资料

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Ch. 0, strings, length and the empty string。
• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，Ch. 1, strings and Kleene closure。