字母表 (计算机科学)

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

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

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

参见[编辑]