確定的有窮自動機和不確定的有窮自動機有什麼區別

1樓：匿名使用者

一、轉換狀態不同

1、確定的有窮自動機：當一個狀態面對一個輸入符號的時候，所轉換到的是一個唯一確定的狀態。

2、不確定的有窮自動機：當一個狀態面對一個輸入符號的時候，它所轉換到的可能不只一個狀態，可以是一個狀態集合。

二、特點不同

1、確定的有窮自動機：系統具有一系列離散的輸入輸出資訊和有窮數目的內部狀態。

2、不確定的有窮自動機：允許在每一步上讀頭的內部狀態可在幾個狀態中任取，即 δ 之值為內部狀態之集合。

三、對映不同

1、確定的有窮自動機：將s×σ對映到s的轉換函式。s∈s, a∈σ, δ(s,a)表示從狀態s出發，沿著標記為a的邊所能到達的狀態。

2、不確定的有窮自動機：將s×σ對映到2s的轉換函式。s∈s, a∈σ, δ(s,a)表示從狀態s出發，沿著標記為a的邊所能到達的狀態集合。

2樓：忘我之魚

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

編譯原理中確定的有窮自動機和不確定的有窮自動機有什麼區別

3樓：匿名使用者

有窮自動機，或有窮狀態的機器，是描述（或「機器」）特定型別演算法的數學方法。

特別地，有窮自動機可用作描述在輸入串中識別模式的過程，因此也能用作構造掃描程式。

當然有窮自動機與正規表示式之間有著很密切的關係。

正規表示式可在程式設計語言中給出識別符號模式的一般定義（假設已定義了letter 和digit）：identifier = letter （ letter | digit ） *，它代表以一個字母開頭且其後為任意字母和/ 或數字序列的串。

有窮自動機又分為確定型的有窮自動機（dfa）與非確定型的有窮自動機（nfa）兩種。

編譯原理有窮自動機的問題

4樓：匿名使用者

在i0->i3時，小圓點行移到了大b前面，大b是非終結符，會引發b開始的二個項。（這個情況同i0->i2)的情形。

而i0->i4時，小圓點移到小b後面，不會引發其它項。