字母表 (计算机科学)

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

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

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

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

符号表示

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

给定一个字母表 ,则字母表 上所有长度为 的字符串的集合由 表示。表示所有有限字符串(无论其长度如何)的集合 Kleene星号表示为 ,也被称为 的Kleene闭包。符号 表示字母表 上所有无限序列的集合,而 表示所有有限或无限序列的集合 

例如,使用二进制字母表{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   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 (𝐬1,...,𝐬n)∈𝗔n is written as 𝐬1···𝐬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.