為什麼從三個小小的詞開始
在前一篇導覽中，我們看到了整門學科的那個核心大想法：計算理論把每一個計算問題都轉化成關於「符號字串」的問句。但唯有我們對「字串到底是什麼」鋒利到位，這個轉化才划算。所以這篇導覽要做一件看起來小到幾乎不重要的事——仔細定義三個名詞：字母表、符號、字串。它們是磚塊；你日後要蓋的所有更重的東西（機器、文法、那整座語言類別的高塔）都只是把這些磚塊巧妙堆疊起來的方法。
費這番工夫，有個誠實的理由。初學者日後幾乎每一個困惑的時刻——epsilon 是符號還是字串？空語言和空字串是同一回事嗎？為什麼 a^n b^n 會難倒一台有限記憶體的機器？——都可以追溯到對這三個詞掌握得模糊不清。現在花十分鐘仔細弄懂，等於替自己換來好幾個月的清明。即使這些定義看起來理所當然，這份回報是真實的。
字母表 Sigma 與它的符號
字母表就是你被允許使用的「組件」集合——想想拼字遊戲盒裡的字母牌。在談論「字」之前，你得先約定有哪些牌存在。形式上，字母表是一個有限且非空的集合，依長久的慣例，我們用希臘大寫字母 Σ（Sigma，寫起來像一個側躺的大寫 E）來命名它。兩個日常的例子：二進位字母表 Σ = {0, 1}，以及小型字母表 Σ = {a, b}。
這兩個要求都不是白擺的。有限表示只有有限多個不同的牌；不能有無限多種不同字母。非空表示至少要有一個牌——一個牌都沒有，就永遠寫不出任何東西。Σ 的成員稱為符號（或字母），而理論把每一個符號都當成不可分割的原子：它從不去窺看符號的內部。'a' 用哪種字體印出來、'0' 代表零還是關閉，都無所謂。重要的只有：不同的符號彼此可以區分。
字串：鐵絲上的珠子
Σ 上的字串（也稱為字／詞）是一個由 Σ 中符號構成的有限、有序的序列——想像依固定次序串在鐵絲上的珠子。若 Σ = {a, b}，那麼 aab 就是一個字串：先一個 a、再一個 a、再一個 b。順序重要，所以 aab 和 aba 是不同的字串，即使它們用的是一模一樣的符號。重複是可以的：aaa 是完全合格的字串。我們通常用 w、x、y 這類字母來命名字串。關鍵在於：字串是有限的——它有最後一顆珠子，即使非常長。
字串的長度就是它有多少顆珠子，從第一顆數到最後一顆，連重複的也算。我們用一對直線符號來寫：|ab| = 2、|aaa| = 3、|b| = 1。還有一個非常特別、完全沒有珠子的字串，叫空字串，寫作 ε（epsilon，一個彎彎的小寫希臘 'e'）。它的長度為零：|ε| = 0。它感覺像「什麼都沒有」，但它是一個真實、定義明確的物件——正如數字 0 是一個真實的數，即使它什麼也數不到。我們永遠需要替「寫下零個符號的結果」取個名字。
黏合字串：串接與次方
我們怎麼用較短的字串造出較長的字串？靠串接——把兩個字串首尾相接黏起來，正像把兩列樂高火車拼成一列。x 與 y 的串接寫作 xy：先依序排完 x 的全部，再依序接上 y 的全部。所以若 x = ab、y = ba，則 xy = abba。兩條乾淨的規則永遠成立。長度相加：|xy| = |x| + |y|。空字串什麼也不改變：εw = wε = w，正如加 0 不改變一個數。
串接具有結合律——(xy)z = x(yz)，所以我們可以自由地寫 xyz 而不必擔心括號分組——但它不具交換律：xy 與 yx 通常不同（abba 不等於 baab）。重複串接就得到字串的次方：w^k 表示把 w 與自己黏 k 次。所以若 w = ab，則 w^2 = abab、w^3 = ababab，而 w^0 = ε（零份就是空字串，是自然的起點）。次方讓我們能簡潔地命名整個無限的家族——著名的樣式 a^n b^n 就表示 n 個 a 後面接 n 個 b。
這個小小的樣式 a^n b^n 值得標記出來，因為它預示了後續整齣戲。要檢查一個字串是否真的是 a^n b^n 的形式，你必須記住自己看過多少個 a，才能要求剛好一樣多的 b——而 n 可以任意大。一台記憶體固定、有限的機器無法保住這個計數，這正是為什麼 a^n b^n 恰好落在你即將認識的最簡單機器（有限自動機）的能力之外，而需要一台稍強一點的機器。再往上爬幾階，你就會親手追蹤這個例子；今天，只要注意到：一行用次方寫成的樣式，就已經能把弱的機器和強的機器區分開來。
Sigma 星號：所有字串的宇宙
現在把你用一個字母表所能寫出的一切，全部收進一個集合裡。那個集合就是 Sigma 星號，寫作 Σ（那個星號就是 Kleene 星號——單一顆星，絕不寫成兩顆）。Σ 是 Σ 上所有有限字串的集合，包含 ε。你可以把它想成依長度一層層堆起來：長度 0 只給 ε；長度 1 給 Σ 的符號；長度 2 給所有成對的；如此永無止盡。Σ* 是裝著一切可能輸入的巨大袋子——在下一篇導覽中，每個語言都將從這個宇宙中被當成「子集」雕刻出來。
Sigma = {a, b}. Layer Sigma* by length:
length 0 : epsilon
length 1 : a b
length 2 : aa ab ba bb
length 3 : aaa aab aba abb baa bab bba bbb
... ... and on forever ...
Sigma* = every row, unioned together (includes epsilon)
Sigma+ = Sigma* with the epsilon row removed (non-empty strings only)這裡有個看似微小、卻暗藏深意的事實：Σ* 裡的每一個字串都有限，但集合 Σ* 本身卻是無限的。這並不矛盾——圖中的每一列都有限，但列有無限多。（如果你哪天只想要所有非空字串，那個集合有自己的名字，叫 Sigma 加號，寫作 Σ+——它就是把 ε 那一列去掉的 Σ。）而且 Σ 是最溫和的那種無限：原則上你可以把它的成員一個接一個列出來——先按長度，每個長度內再按字母順序——使每個字串最終都會出現。這種有序的「可列性」稱為可數，它正是這門學科最深刻的結果之一所仰賴的那道靜默樞紐：因為可能的程式只有可數多個，可能的語言卻有不可數多個，所以有些問題必定根本沒有任何程式可解。
這些磚塊要通往何方
你現在已掌握地面層的完整詞彙：一個由符號組成的字母表、用串接與次方造出的字串、空字串 ε，以及所有有限字串的宇宙 Σ。下一篇導覽就要跨出整門學科賴以建立的那一步——它從 Σ 裡挑出有趣的子集，把每一個都稱為一個語言。然後，學習階梯的其餘部分就是一道長長的問句：哪一種機器能識別哪些子集？
把終點放在眼前會很有幫助。從最簡單排到最強大，這些機器與它們的字串集合構成了喬姆斯基階層：有限自動機識別正規語言；加上一個堆疊，下推自動機就能觸及上下文無關語言（a^n b^n 正是在這裡終於變得可被識別）；而全能的圖靈機則能觸及遞迴可枚舉語言，並定義了「演算法」究竟是什麼。這些宏大的想法，說到底，每一個都是關於你剛剛建好的那個 Σ* 的子集的陳述。把這些磚塊弄對，它們之上的那座大教堂就會說得通。