字母表 (计算机科学)

如果L是一种形式化语言，即一个（可能是无限的）有限长度字符串的集合，那么L的字母表就是L的任何字符串中出现的所有符号的集合。例如，如果L是C编程语言中所有变量标识符的集合，那么L’的字母表就是集合{ a, b, c, ..., x, y, z, A, B, C, ..., X, Y, Z, 0, 1, 2, ..., 7, 8, 9, _ }。

给定一个字母表${\displaystyle \Sigma }$ ，则字母表${\displaystyle \Sigma }$ 上所有长度为${\displaystyle n}$ 的字符串的集合由${\displaystyle \Sigma ^{n}}$ 表示。表示所有有限字符串（无论其长度如何）的集合${\textstyle \bigcup _{i\in \mathbb {N} }\Sigma ^{i}}$ 被Kleene星号表示为${\displaystyle \Sigma ^{*}}$ ，也被称为${\displaystyle \Sigma }$ 的Kleene闭包。符号${\displaystyle \Sigma ^{\omega }}$ 表示字母表${\displaystyle \Sigma }$ 上所有无限序列的集合，而${\displaystyle \Sigma ^{\infty }}$ 表示所有有限或无限序列的集合${\displaystyle \Sigma ^{\ast }\cup \Sigma ^{\omega }}$ 。

例如，使用二进制字母表{0,1}，字符串ε、0、1、00、01、10、11、000等都在字母表的Kleene闭包中（其中ε代表空字符串）。

字母表在形式语言、自动机和半自动机的使用中很重要。在大多数情况下，为了定义自动机实例，如确定有限状态自动机（DFA），需要指定一个字母表，从这个字母表创建自动机的输入字符串。在这些应用中，通常要求字母表是一个有限集，但没有其他限制。

当使用自动机、正则表达式或形式语法，作为字符串处理算法的一部分时，可以假定字母表是这些算法要处理的文本的字符集，或者是字符集中可允许的字符的子集。

• 形式语言
• 语法
• 语义

1. ^ Ebbinghaus, H.-D.; Flum, J.; Thomas, W. Mathematical Logic 2nd. New York: Springer. 1994: 11. ISBN 0-387-94258-0. By an alphabet ${\displaystyle {\mathcal {A}}}$  we mean a nonempty set of symbols. 
2. ^ Rautenberg, Wolfgang. A Concise Introduction to Mathematical Logic (PDF) Third. Springer. 2010: xx [2022-08-26]. ISBN 978-1-4419-1220-6. （原始内容存档 (PDF)于2022-03-02）. If 𝗔 is an alphabet, i.e., if the elements 𝐬 ∈ 𝗔 are symbols or at least named symbols, then the sequence (𝐬₁,...,𝐬_n)∈𝗔ⁿ is written as 𝐬₁···𝐬_n and called a string or a word over 𝗔. 

• John, E. Hopcroft; Jeffrey, D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing. 1979. ISBN 0-201-02988-X.