字母表 (電腦科學)

在電腦科學中，字母表是字元或數字的有限集合。^[1]最常見的字母表是二元字母表{0,1}。有限字串是來自字母表的字元的有限序列；^[2]例如二元字串是來自字母表{0,1}的字元構成的字串。字元的無限序列也可以用來自一個字母表的元素來構造。

給定一個字母表 $\Sigma$ ，我們寫 $\Sigma ^{*}$ 來指示在字母表 $\Sigma$ 上的所有有限字串的集合。這裡的 ${}^{*}$ 指示Kleene星號算子。我們寫 $\Sigma ^{\infty }$ (偶爾 $\Sigma ^{\mathbb {N} }$ 或 $\Sigma ^{\omega }$ ）來指示在字母表 $\Sigma$ 上的所有無限序列的集合。

例如，如果我們使用二元字母表{0,1}，則字串ε, 0, 1, 00, 01, 10, 11, 000等都將在這個字母表的Kleene閉包中（這裡的ε表示空字串）。

字母表在形式語言、自動機和半自動機理論中相當重要。自動機如確定有限狀態自動機（DFA）要求在形式定義中有字母表。

符號表示[編輯]

如果L是一種形式化語言，即一個（可能是無限的）有限長度字串的集合，那麼L的字母表就是L的任何字串中出現的所有符號的集合。例如，如果L是C程式語言中所有變數識別碼的集合，那麼L』的字母表就是集合{ a, b, c, ..., x, y, z, A, B, C, ..., X, Y, Z, 0, 1, 2, ..., 7, 8, 9, _ }。

給定一個字母表 $\Sigma$ ，則字母表 $\Sigma$ 上所有長度為 $n$ 的字串的集合由 $\Sigma ^{n}$ 表示。表示所有有限字串（無論其長度如何）的集合 ${\textstyle \bigcup _{i\in \mathbb {N} }\Sigma ^{i}}$ 被Kleene星號表示為 $\Sigma ^{*}$ ，也被稱為 $\Sigma$ 的Kleene閉包。符號 $\Sigma ^{\omega }$ 表示字母表 $\Sigma$ 上所有無限序列的集合，而 $\Sigma ^{\infty }$ 表示所有有限或無限序列的集合 $\Sigma ^{\ast }\cup \Sigma ^{\omega }$ 。

例如，使用二進位字母表{0,1}，字串ε、0、1、00、01、10、11、000等都在字母表的Kleene閉包中（其中ε代表空字串）。

應用[編輯]

字母表在形式語言、自動機和半自動機的使用中很重要。在大多數情況下，為了定義自動機實例，如確定有限狀態自動機（DFA），需要指定一個字母表，從這個字母表建立自動機的輸入字串。在這些應用中，通常要求字母表是一個有限集，但沒有其他限制。

當使用自動機、正規表示式或形式語法，作為字串處理演算法的一部分時，可以假定字母表是這些演算法要處理的文字的字元集，或者是字元集中可允許的字元的子集。

參見[編輯]

來源[編輯]

^ Ebbinghaus, H.-D.; Flum, J.; Thomas, W. Mathematical Logic 2nd. New York: Springer. 1994: 11. ISBN 0-387-94258-0. By an alphabet ${\mathcal {A}}$ we mean a nonempty set of symbols.
^ 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 (𝐬₁,...,𝐬_n)∈𝗔ⁿ is written as 𝐬₁···𝐬_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.

這是一篇與邏輯學相關的小作品。你可以透過編輯或修訂擴充其內容。

這是一篇電腦科學小作品。你可以透過編輯或修訂擴充其內容。

[1] Ebbinghaus, H.-D.; Flum, J.; Thomas, W. Mathematical Logic 2nd. New York: Springer. 1994: 11. ISBN 0-387-94258-0. By an alphabet ${\mathcal {A}}$ 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 (𝐬₁,...,𝐬_n)∈𝗔ⁿ is written as 𝐬₁···𝐬_n and called a string or a word over 𝗔.

[1]

[2]