查看“︁字母表 (计算机科学)”︁的源代码

{{Request translation}}
{{NoteTA
|G1 = IT
}}
在[[计算机科学]]中，'''字母表'''是字符或数字的有限集合。<ref>{{cite book|last1=Ebbinghaus|first1=H.-D.|last2=Flum|first2=J.|last3=Thomas|first3=W.|date=1994|title=Mathematical Logic|edition=2nd|publisher=[[Springer Science+Business Media|Springer]]|location=[[New York City|New York]]|isbn=0-387-94258-0|page=11|quote=By an ''alphabet'' <math>\mathcal{A}</math> we mean a nonempty set of ''symbols''.|url=https://www.springer.com/mathematics/book/978-0-387-94258-2}}</ref>最常见的字母表是'''二元字母表'''{0,1}。有限[[字符串]]是来自字母表的字符的有限序列；<ref>{{cite book|last=Rautenberg|first=Wolfgang|year=2010|title=A Concise Introduction to Mathematical Logic|edition=Third|publisher=Springer|isbn=978-1-4419-1220-6|page=xx|url=https://link.springer.com/content/pdf/bfm%3A978-1-4419-1221-3%2F1.pdf|quote=If 𝗔 is an ''alphabet'', i.e., if the elements 𝐬 ∈ 𝗔 are symbols or at least named symbols, then the sequence (𝐬<sub>1</sub>,...,𝐬<sub>n</sub>)∈𝗔<sup>n</sup> is written as 𝐬<sub>1</sub>···𝐬<sub>n</sub> and called a ''string'' or a ''word'' over 𝗔.|access-date=2022-08-26|archive-date=2022-03-02|archive-url=https://web.archive.org/web/20220302234859/http://link.springer.com/content/pdf/bfm:978-1-4419-1221-3/1.pdf|dead-url=no}}</ref>例如二元字符串是来自字母表{0,1}的字符构成的字符串。字符的无限[[序列]]也可以用来自一个字母表的元素来构造。

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

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

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

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

给定一个字母表<math>\Sigma</math>，则字母表<math>\Sigma</math>上所有长度为<math>n</math>的字符串的集合由<math>\Sigma^n</math>表示。表示所有有限字符串（无论其长度如何）的集合<math display="inline">\bigcup_{i \in \mathbb{N}} \Sigma^i</math>被[[Kleene星号]]表示为<math>\Sigma^*</math>，也被称为<math>\Sigma</math>的Kleene闭包。符号<math>\Sigma^\omega</math>表示字母表<math>\Sigma</math>上所有无限序列的集合，而<math>\Sigma^\infty</math>表示所有有限或无限序列的集合<math>\Sigma^\ast \cup \Sigma^\omega</math>。

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

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

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

== 参见 ==
* [[形式语言]]
* [[语法]]
* [[语义]]

== 来源 ==
<references />

== 外部链接 ==

* {{Cite book|title=Introduction to Automata Theory, Languages, and Computation|last=John|first=E. Hopcroft|last2=Jeffrey|first2=D. Ullman|publisher=Addison-Wesley Publishing|year=1979|isbn=0-201-02988-X}}

[[Category:形式语言]]
[[Category:词语组合]]
{{logic-stub}}
{{计算机科学小作品}}