形式語言（formal language）

日常口語中，語言是一種溝通方式，但在這門理論裡，這個詞被精簡成更單純、更鋒利的東西：語言就是一個字串集合。挑一個字母表，看看用它能寫出的所有字串（那就是 Σ*），然後任意選出其中一個你喜歡的子集。那個被選出的集合就是一個語言。它是一份賓客名單，不是文法課：它只說哪些字串在裡面、哪些在外面，僅此而已。

形式上，字母表 Σ 上的語言 L 是 Σ* 的任意子集，寫作 L ⊆ Σ*（L 是 Sigma 星號的子集）。因為它只是一個集合，L 裡的字串不必共享任何明顯的樣式，雖然有趣的語言都有。在 Σ = {0, 1} 上的例子包括：所有以 0 結尾的字串的語言、所有含偶數個 1 的字串的語言，以及 { 0^n 1^n : n 至少為 0 }（同樣多的 0 後面接同樣多的 1）這個語言。語言可以是有限的（如 { ab, ba }）或無限的（如所有偶數長度的字串），而單一個語言可以包含 ε，也可以不包含。

這個定義是整門學科的大躍進。一旦語言只是一個字串集合，識別樣式、判定一個是非題、接受一個輸入，全都變成同一件事：測試某個給定字串是否屬於某個給定語言。這正是為什麼語言是自動機、文法與複雜度類別都拿來比較的共同基礎。誠實提醒：別把語言（字串集合）和描述它的裝置混淆。有限自動機、正規表示式、文法是描述語言的不同方式，但語言本身就只是那個集合。