從一條字串到全部字串：Sigma-star
在上一篇你已經確定了單一字串的意思：一段從字母表 Sigma（希臘字母 sigma，我們固定的允許符號袋）取出的、有限且有序的符號串。你也認識了字串長度、空字串 epsilon（長度為零的那條唯一字串），以及串接（把兩條字串首尾黏在一起）。現在我們踏出一個看似微小、卻會重整整門學科的一步：不再一次只看一條字串，而是去看字串的集合。
首先，替「最大的那個集合」取個名字。我們用 Sigma-star（常寫作 Σ*，那顆小星星叫做 Kleene 星號）來表示在 Sigma 上能造出的所有有限字串所成的集合——包含 epsilon 在內。若 Sigma = {a, b}，則 Sigma-star 從 epsilon、a、b、aa、ab、ba、bb、aaa、… 開始，永遠列不完。請誠實記住兩件事：Sigma-star 裡的每一條字串都是有限的，但 Sigma-star 這個集合本身卻是無限的（只要 Sigma 至少有一個符號）。沒有「最長的字串」，就如同沒有「最大的整數」一樣。
語言就只是一個字串的集合
接下來是後續整道階梯所立足的定義，而它樸素到令人吃驚。在 Sigma 上的一個（形式）語言 L，就是 Sigma-star 的任意一個子集合。就這樣而已：語言是一個集合，只不過它的成員恰好都是字串。它可以是有限的（像 {a, ab, abc}）、無限的（像「所有偶數長度的字串」），甚至可以是空的。這裡還沒有文法、沒有意義、也還沒有機器——就只是從 Sigma-star 這個巨大的池子裡，挑出來的一堆字串。
既然語言是一個集合，我們就用描述任何集合的方式來描述它。集合小的時候可以一一列舉，不小的時候就用集合建構式記法。舉例來說，在 Sigma = {a, b} 上，「a 的個數為偶數的字串」這個語言就是 { w 屬於 Sigma-star ：w 中 a 的個數為偶 }。這短短一句描述悄悄裝進了 epsilon（零個 a 也算偶數）、b、bb、aa、aba、baab，以及無窮多條其他字串。判斷哪些字串屬於、哪些不屬於，正是你在接下來整道階梯中要磨練的功夫。
空語言不是「只含空字串的語言」
接下來是一個幾乎每個人第一次都會被絆倒、值得放慢腳步看清楚的區別：空語言，與只含空字串的語言。空語言寫作 {} 或代表「空」的集合符號，它完全沒有任何成員——零條字串。而epsilon-語言 {epsilon} 恰好有一個成員，就是那條空字串。兩者在紙上看起來幾乎一模一樣，但一個是空盒子，另一個則是裝著一張長度為零的小紙條的盒子。
這個差別不是吹毛求疵——它會改變答案。空語言的大小是 0；epsilon-語言的大小是 1。問「這個語言接受空輸入嗎？」，空語言說不，而 {epsilon} 說是。等到機器登場時，空語言正是一台沒有任何接受狀態的 DFA 所識別的語言，而 {epsilon} 則由一台「只在還沒讀任何東西之前就接受」的機器所識別。紙上長得一樣，行為卻完全相反。
用舊語言造出新語言
既然語言是集合，所有常見的集合運算都原封不動適用：聯集（L1 聯集 L2 = 屬於任一者的字串）、交集（同時屬於兩者）、補集（在 Sigma-star 中而不在 L 內的字串）。但語言還繼承了一般集合所沒有的、帶字串味道的運算。其中最重要的是語言串接：L1 . L2 是「從 L1 取一條字串、把 L2 的一條字串黏在它尾端」所能造出的所有字串所成的集合。例如 {a, ab} . {c, d} = {ac, ad, abc, abd}。
皇冠上的明珠是作用在語言上的 Kleene 星號，寫作 L*。它的意思是：從 L 中取零條或多條字串，以任意組合、允許重複地串接起來。關鍵在於「取零條」是合法的，所以 epsilon 永遠在 L* 裡（即使 L 本身不含 epsilon）。若 L = {ab}，則 L* = {epsilon, ab, abab, ababab, …}。本級的下一篇會完整地專講 L* 與這些運算；這裡先感受它的樣貌就好。注意 Sigma-star 恰好就是把這個構造套在 L = Sigma 上：對字母表本身打星號。
Sigma = {a, b}
L1 = { a, ab } L2 = { c, d }
L1 union L2 = { a, ab, c, d }
L1 . L2 = { ac, ad, abc, abd }
L = { ab }
L* = { epsilon, ab, abab, ababab, ... } (zero or more copies; note epsilon)
L+ = { ab, abab, ababab, ... } (one or more copies; no epsilon)為何重要：一個問題「就是」一個語言
接下來是讓整套裝置師出有名的關鍵一步，它也回答了本級第 1 篇提出的「為什麼要抽象地研究計算？」。幾乎任何是非式的計算問題，都能被編碼成一個語言。先替輸入挑一種合理的字串編碼；接著把所有「答案為是」的已編碼輸入，恰好收集成一個語言 L。於是「輸入 w 的答案是不是『是』？」就變成了成員資格問題：字串 w 是不是 L 的成員？而把這個答案算出來，正是 L 的判定問題。
一個具體例子：「這個數是質數嗎？」變成語言 PRIMES = { w ：w 是某個質數的二進位編碼 }。那麼一台判定質數性的機器，恰好就是一台判定「是否屬於 PRIMES」的機器。這種重新框定是這個領域的看家本領：它把天差地遠的各種問題——排序、圖的連通性、定理檢查——統統化成「w 是否屬於 L？」這唯一一種統一的形狀。一旦每個問題都是一個語言，我們就能問：到底（若存在的話）是哪一台機器能識別它。
而這個問題有一張著名的地圖。語言會依「你需要多複雜的機器才能識別它」分層，排進喬姆斯基階層：正規語言（由有限自動機識別，下一級的主題）包在上下文無關語言（由下推自動機識別——一台有限機器再加一個堆疊）之中，又包在遞迴可枚舉語言（由圖靈機識別，最強大的模型）之中。每一層都嚴格地包在下一層裡面。攀爬之前先誠實提醒一句：「正規」不等於「有限」——無限的語言 Sigma-star 本身就是正規的。從某種意義上說，這道階梯接下來的全部內容，就是一層一層去探索這張地圖。