簡介
引入
不確定型有窮自動機
不確定型有窮自動機
不確定型有窮自動機有窮自動機是一種有窮級數模型。它由一個讀頭和一條有窮長的紙帶所組成，紙帶被分割成有限個同樣大小的單元，每個單元中可以是空的，或寫有取自有窮字母表上的一個字母，讀頭在每一時刻都對準一個單元，並具有一個確定的內部狀態，這些內部狀態構成一個有窮集。其中指定一個（比如 q）為初始狀態，另外，指定一個作為終止狀態（或接受狀態）集。
不確定型有窮自動機讀頭每次只能向右移動一單元（而不能寫或抹），並且每次都必須向右移動。讀頭所取的內部狀態將由一個轉換函式 δ 所確定。具體地說，在一個有窮自動機 工作時，當讀頭所指單元內符號為 a，內部狀態為 q時，讀頭將向右移一單元並取新的內部狀態於是，有窮自動機 可以形式地看成右字母表 A，內部狀態集 Q、開始狀態 q、終止狀態集 F 及轉換函式 δ 所組成的一個五元組 =<A,Q,q,F,δ> 。在紙帶上給定 A 上的一個字 δ，如約定讀頭指向 σ 最左邊的符號且以 q為開始狀態， 便可開始運行，當 讀完 σ 的讀頭所取的內部狀態為接受狀態，則稱 接受 σ ，否則便拒絕 σ 。所有被 所接受的字組成的 接受的語言 L()={σ∈A*| 接受σ}。
圖1.有窮自動機美國邏輯學家、數學家克林(Kleene,S.C.)證明了一個語言可被某有窮自動機接受，若且唯若它為正規的，這個結論成為克林刻畫。
定義
有窮自動機的每一步操作都是確定的，因此可稱為確定型有窮自動機。如果允許在每一步上讀頭的內部狀態可在幾個狀態中任取，即 δ 之值為內部狀態之集合（而不是一個內部狀態），這樣便得到非確定型有窮自動機。但是這兩類自動機接受的語言類時一致的。
辨析
確定有窮自動機就是說當一個狀態面對一個輸入符號的時候，它所轉換到的是一個唯一確定的狀態；
不確定有窮自動機是說當一個狀態面對一個輸入符號的時候，它所轉換到的可能不只一個狀態，可以是一個狀態集合。這就是兩者的主要區別。還有就是 DFA 的開始狀態是唯一的，而 NFA 的開始狀態是一個開始狀態集。
