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