跳至內容

字母表 (電腦科學)

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

電腦科學中,字母表是字元或數字的有限集合。[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.