字母表 (计算机科学)

Template:Request translation Template:NoteTA 在计算机科学中，字母表是字符或数字的有限集合。最常见的字母表是二元字母表{0,1}。有限字符串是来自字母表的字符的有限序列；例如二元字符串是来自字母表{0,1}的字符构成的字符串。字符的无限序列也可以用来自一个字母表的元素来构造。

给定一个字母表$\mathrm{\Sigma }$，我们写${\mathrm{\Sigma }}^{*}$来指示在字母表$\mathrm{\Sigma }$上的所有有限字符串的集合。这里的${}^{*}$指示Kleene星号算子。我们写${\mathrm{\Sigma }}^{\mathrm{\infty }}$(偶尔${\mathrm{\Sigma }}^{\mathbb{N}}$或${\mathrm{\Sigma }}^{\omega }$）来指示在字母表$\mathrm{\Sigma }$上的所有无限序列的集合。

例如，如果我们使用二元字母表{0,1}，则字符串ε, 0, 1, 00, 01, 10, 11, 000等都将在这个字母表的Kleene闭包中（这里的ε表示空串）。

字母表在形式语言、自动机和半自动机理论中相當重要。自动机如确定有限状态自动机（DFA）要求在形式定义中有字母表。

符号表示

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

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

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

应用

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

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

参见

• 形式语言
• 语法
• 语义

外部链接

• Template:Cite book