非確定型有限自動機（NFA）
三種模型的等價（the equivalence of the three models）
我們已經見過三種風味的有限自動機：確定型的 DFA、非確定型的 NFA，以及還能在空字串上移動的 ε-NFA。它們看起來一個比一個有彈性，你或許會期待每一個都比前一個更強。本章的頭條結論是：這三者辨識的「恰好」是同一族語言——正規語言。它們的差別在便利，從不在能力。
一連串的轉換把這個圈閉合起來。每個 DFA 本來就是 NFA（其轉移集合恰好都是單元素集），每個 NFA 本來就是 ε-NFA（它只是不用 ε-移動而已）。反方向走：ε-消除把任何 ε-NFA 變成辨識同一語言的普通 NFA，子集構造法又把任何 NFA 變成辨識同一語言的 DFA。既然你能在這三者之間雙向往返且保持語言不變，那麼這三類「可辨識語言」就必然重合。
這正是為什麼「正規語言」是一個穩健、與模型無關的概念：用這三台機器中的哪一台來定義它都無所謂。（很快你會遇到第四種定義——正規表示式——而 Kleene 定理會證明它捕捉的正是同一族。）更深的教訓是理論中反覆出現的主題：加入一個看似強大的功能，有時什麼也沒加。在這裡它是一個乾淨、正面的驚喜；但稍後，在確定型對非確定型「下推」自動機那裡，類比的功能就「真的」增加了能力，所以等價性絕不可一概假設——每次都必須重新證明。
用三種方式定義語言「含有 aa」：一台 3 狀態的 DFA、一台猜 aa 在哪的小 NFA，以及一台用 ε-移動把子機器黏起來的 ε-NFA。把其中任一台轉成另一台，被接受的字串都不會改變——三者辨識的是同一個正規語言。
三台機器、三種便利、同一個類別：正規語言。
這裡的等價是有限自動機才有的特例，不可在別處一概假設：確定型與非確定型「下推」自動機在能力上是真的不相等。
又稱
另見