形式陈述

字母表 $\Sigma$$\mathrm{\Sigma }$ 是用于构造有限字的有限非空集合，其元素称符号。符号只需彼此可区分，不必是自然语言字母；例如

$$ \Sigma=\{0,1\},\qquad \Sigma=\{a,b,(,)\} $$$$\mathrm{\Sigma }=\{0,1\},\mathrm{\Sigma }=\{a,b,(,)\}$$

都可作为字母表。形式语言理论通常把字母表视为模型的一部分，因为同一有限符号序列只有在指定 $\Sigma$$\mathrm{\Sigma }$ 后才确定属于哪个自由幺半群 $\Sigma^*$${\mathrm{\Sigma }}^{\ast }$。某些代数约定允许空字母表，此时 $\Sigma^*=\{\varepsilon\}$${\mathrm{\Sigma }}^{\ast }=\{\epsilon \}$；本库采用计算理论中常见的非空约定。

直觉

字母表规定可用的原子记号，像编程语言的字符集或通信协议的消息类型；它不规定这些符号怎样组合才有意义。

例子与边界

二进制字母表有两个符号，而字符串“01”不是一个符号而是长度二的字。符号可以本身写成多个印刷字符，例如把 TOKEN_ID 视为单个词法符号；数学上只关心集合元素的原子身份。有限性是经典有限自动机与形式语言的标准假设；研究无限字母自动机时需额外表示和可判定性结构。字母表与语言不同：字母表给原料，语言是由这些原料形成的字集合。

推论与应用

字母表是字符串、语言、自动机、编码和语法的底层载体；明确它能避免补集、正则表达式和复杂度中“输入域”含糊。

参考资料

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