說明DFA和NFA中語言的最壞情況狀態數。

確定性有限自動機（DFA）是一個五元組

M=(Q, ∑, δ,q0,F)

其中，

• Q - 有限狀態集。

• ∑ - 有限字母表集。

• δ - Q × ∑ → Q 是轉移函式。

• q0 ∈ Q 是起始狀態或初始狀態。

• F - 結束狀態或接受狀態。

讓我們看看語言A∩B 和 A*的DFA中狀態的最壞情況數量。

假設A和B是兩個狀態，

|A| = 狀態數 = nA

|B| = 狀態數 = nB

DFA = |A∩B|

   =nA.nB

|A ∪ B| =nA.nB

|A*|=3/4 2^nA

|AB| = nA (2^nB-2^nB-1)

NFA

非確定性有限自動機（NFA）也與DFA具有五個相同的狀態，但轉移函式不同，如下所示：

δ: Q X ∑ -> 2^Q

其中，

• Q - 有限狀態集。

• ∑ - 輸入符號的有限集。

• q0 - 初始狀態。

• F - 結束狀態。

• δ - 轉移函式。

讓我們看看語言A∩B 和 A*的NFA中狀態的最壞情況數量。

假設A和B是兩個狀態，

|A| = 狀態數 = nA

|B|= 狀態數 = nB

NFA

|AUB| = nA+nB+1

|A*| = nA+1

|AB| = nA+nB

|A∩B| = nA.nB

Bhanu Priya

更新於：2021年6月16日

430 次檢視

啟動你的職業生涯

透過完成課程獲得認證

開始