字母表

字母表决定“观察一次输入时，最小可见单位是什么”。同一份程序文本既可在字符层使用 ASCII 或 Unicode 码点，也可在词法层使用 IDENT、NUMBER、PLUS 等 token。更换字母表会改变模型看见输入的粒度；之后所谓一步转移、一个位置和一个前缀都随之改变，远非字体替换所能概括。

把符号称为原子，是相对于当前问题而言。网络包可以在链路模型中被当作不可分事件，在更低层模型中却是字节序列。形式语言理论不要求符号在物理上不可拆，只要求一旦 $\mathrm{\Sigma }$ 固定，理论中的连接、长度和读取动作都按这些符号计数。

有限性保证一张显式自动机转移表只有有限多列，也使“有限控制”真正成为有限对象。它并不限制由字母表生成的字有多长：只要 $\mathrm{\Sigma }\ne \varnothing$，集合 ${\mathrm{\Sigma }}^{\ast }$ 就包含任意有限长度的字，通常是无限集。

在二进制字母表 $\mathrm{\Sigma }=\{0,1\}$ 上，${\mathrm{\Sigma }}^2=\{00,01,10,11\}$，而 $\epsilon \in {\mathrm{\Sigma }}^{\ast }$ 且 $\epsilon \notin \mathrm{\Sigma }$。这一区分很实用：若把 ε 真的列为普通输入符号，读入它会消耗一个位置；自动机图中的 ε-转移则完全不消耗输入。

编译器扫描完源字符后，可以改用

作为语法分析器的字母表。源代码 total+1 在字符层有七个符号，在 token 层却是 IDENT PLUS NUMBER 三个符号；两个模型描述同一对象的不同阶段，长度不可混用。

补集说明了为什么字母表必须随语言一起固定。把 $L=\{w\in \{0,1{\}}^{\ast }:w\text{ 含偶数个 }1\}$ 看作二进制语言时，字 2 根本不在论域；若把 $L$ 嵌入 $\{0,1,2{\}}^{\ast }$，那么所有含 2 的字都落入新的补集。字符串集合没有变，补语言却变了。

有些代数文献允许空字母表，此时 ${\mathrm{\Sigma }}^{\ast }=\{\epsilon \}$。本库采用自动机教材常见的“有限且非空”约定。Unicode 码点集合虽然很大但仍有限，可以充当字母表；“任意字符串对象”已经是由符号组成的复合对象，不能充当这里的符号集合。

字母表确定字公理库字Word · String从某个有限位置集到字母表的函数，即有限符号序列。的取值范围，字再组成形式语言公理库形式语言Formal language · Language over an alphabet固定字母表上有限字的任意集合，是识别器、文法与判定问题共同描述的对象。。有限自动机的一次转移读取一个字母表符号，文法把终结符取自字母表，经典正则表达式则以这些符号作为基本表达式。先声明输入粒度，能够避免把字符级、token 级和事件级模型画在同一张状态图里。

任意有限字母表都能有效编码为二进制：给每个符号分配定长比特块，字的连接便对应编码块的连接。这样的编码把长度至多放大一个常数因子，因此通常不改变可判定性或渐近复杂度类别；但它不会自动保留逐字符一步的精确成本，讨论状态数或流式延迟时仍应注明编码层次。