字母表 (计算机科学)

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

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

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

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