不確定型有窮自動機

有窮自動機的每一步操作都是確定的，因此可稱為確定型有窮自動機。如果允許在每一步上讀頭的內部狀態可在幾個狀態中任取，即 δ 之值為內部狀態之集合（而不是一個內部狀態），這樣便得到非確定型有窮自動機。

基本介紹

• 中文名：不確定型有窮自動機
• 外文名：non-deterministic finite automata
• 適用範圍：數理科學
• 類型：有窮級數模型

簡介

引入

有窮自動機是一種有窮級數模型。它由一個讀頭和一條有窮長的紙帶所組成，紙帶被分割成有限個同樣大小的單元，每個單元中可以是空的，或寫有取自有窮字母表上的一個字母，讀頭在每一時刻都對準一個單元，並具有一個確定的內部狀態，這些內部狀態構成一個有窮集。其中指定一個（比如 q₁）為初始狀態，另外，指定一個作為終止狀態（或接受狀態）集。

讀頭每次只能向右移動一單元（而不能寫或抹），並且每次都必須向右移動。讀頭所取的內部狀態將由一個轉換函式 δ 所確定。具體地說，在一個有窮自動機 𝒜 工作時，當讀頭所指單元內符號為 a_i，內部狀態為 q_i時，讀頭將向右移一單元並取新的內部狀態於是，有窮自動機𝒜 可以形式地看成右字母表 A，內部狀態集 Q、開始狀態 q₁、終止狀態集 F 及轉換函式 δ 所組成的一個五元組 𝒜=<A,Q,q₁,F,δ> 。在紙帶上給定 A 上的一個字 δ，如約定讀頭指向 σ 最左邊的符號且以 q₁為開始狀態，𝒜 便可開始運行，當 𝒜 讀完 σ 的讀頭所取的內部狀態為接受狀態，則稱 𝒜 接受 σ ，否則便拒絕 σ 。所有被 𝒜 所接受的字組成的 𝒜 接受的語言 L(𝒜)={σ∈A*|𝒜 接受σ}。

美國邏輯學家、數學家克林(Kleene,S.C.)證明了一個語言可被某有窮自動機接受，若且唯若它為正規的，這個結論成為克林刻畫。

圖1.有窮自動機

定義

有窮自動機的每一步操作都是確定的，因此可稱為確定型有窮自動機。如果允許在每一步上讀頭的內部狀態可在幾個狀態中任取，即 δ 之值為內部狀態之集合（而不是一個內部狀態），這樣便得到非確定型有窮自動機。但是這兩類自動機接受的語言類時一致的。

辨析

確定有窮自動機就是說當一個狀態面對一個輸入符號的時候，它所轉換到的是一個唯一確定的狀態；

不確定有窮自動機是說當一個狀態面對一個輸入符號的時候，它所轉換到的可能不只一個狀態，可以是一個狀態集合。這就是兩者的主要區別。還有就是 DFA 的開始狀態是唯一的，而 NFA 的開始狀態是一個開始狀態集。