字母表 (計算機科學)

維基百科,自由的百科全書
前往: 導覽搜尋

計算機科學中,字母表是字元或數字的有限集合。最常見的字母表是二元字母表 {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) 要求在形式定義中有字母表。

參見[編輯]