正規語言（a regular language）

用一句話說，正規語言就是某個 DFA 所辨識的語言。如果你能造出一部有限狀態機，其所接受的字串恰好是該語言的字串、別無其他，那麼這個語言就是正規的。這是整道語言類別階梯的第一階、也是最簡單的一階，而它正好就是「有界的有限記憶」所能檢查的那組模式。

此處最重要的一點誠實：正規「不」等於有限。一個正規語言可以包含無限多個字串——語言 a*（任意多個 a，包含零個）就是正規且無限的，由一部在 a 上自迴圈的單狀態機器辨識。「正規」意味「可由有限自動機辨識」，這是關於機器記憶的陳述，而非關於語言裝了多少個字串。等價地（你日後會遇到的一個事實），正規語言恰好是那些能用正規表示式描述的語言，這也是為何這個名稱與 regex 的概念能對上。

正規語言極為乖巧：你可以用單趟、常數記憶判定成員資格；它們在聯集、交集、補集等運算下封閉；而且每個正規語言都有唯一最小的 DFA。它們的極限就只是定義它們之機器的有限記憶極限——正規語言不能要求去計數一個無界的量（所以 { a^n b^n : n >= 0 }，這個「個數相等」的語言，不是正規的），但那個證明屬於正規語言性質的主題，不在此處。