Sigma 星號（Sigma-star，Σ*）

Sigma 星號，寫作 Σ*，是用你的字母表所能寫出的「每一個字串」的集合，無論多長，連那個空白的也算。若 Σ = {a, b}，則 Σ* 包含 ε，再來是 a 和 b，再來是 aa、ab、ba、bb，再來是所有三符號字串，如此永無止盡。它是所有可能輸入的宇宙，是接下來每個語言被當成「子集」雕刻出來的那個巨大袋子。

形式上，Σ* 是 Σ 上所有有限字串的集合，而且關鍵是它包含空字串 ε。你可以把它想成依長度一層層堆起來：長度 0 只給 ε，長度 1 給 Σ 的符號，長度 2 給所有成對的，依此類推，而 Σ* 就是所有這些層的聯集。還有一個密切相關的集合 Sigma 加號（Σ+），就是去掉 ε 的 Σ*，也就是所有非空字串；所以 Σ* = Σ+ 再加上 {ε}。

一個真正重要的事實：儘管 Σ* 裡的每一個字串都有限，集合 Σ* 本身卻是無限的。而且它是最溫和的那種無限，稱為可數無限，意思是原則上你可以把它的成員一個接一個列在一張無盡的清單上（先按長度，每個長度內再按字母順序），使每個字串最終都會出現。這在日後極為重要：因為 Σ* 只是可數無限，而所有語言（Σ* 的子集）的集合卻是不可數無限，所以一定存在沒有任何程式能識別的語言——這個計數論證悄悄保證了不可解問題的存在。