字母表 (計算機科學)

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

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

參見[編輯]