為下列語言構造NFA，並使用演算法將其轉換為DFA - L = (aa+ (bb)c)

解答

上述語言的NFA將是：

從NFA到DFA的轉換：

ε-閉包(0) = {0, 1, 4} = A

對於狀態A

對於輸入符號a	對於輸入符號b	對於輸入符號c
∴ T_a = {2}	∴ T_b = {5}	T_c = ∅
∴ ε-閉包(T_a) = ε -閉包(2) = {2} = B	∴ ε-閉包(T_b) = ε -閉包(5) = {5, 6, 8, 9, 11, 12} = C	∴ ε-閉包(∅) = ∅ = D

對於狀態B

對於輸入符號a	對於輸入符號b	對於輸入符號c
∴ T_a = {3}	∴ T_b = {}	T_c = {}
∴ ε-閉包(3) = = {3, 12} = E	∴ ε-閉包(T_b) = { } = ∅ = D	∴ ε-閉包(T_c) = ∅ = D

對於狀態C

對於輸入符號a	對於輸入符號b	對於輸入符號c
∴ T_a = {}	∴ T_b = {7}	T_c = {10}
∴ ε-閉包(T_a) = ∅ = D	∴ ε-閉包(7) = { 7, 8, 6, 9, 11, 12} = F	∴ ε-閉包(10) = {10, 9, 11, 12} = G

對於狀態E

∴ T_a = ∅	∴ T_b = ∅	T_c = ∅
∴ ε-閉包(T_a) = ∅ = D	∴ ε-閉包(T_b) = ф = D	∴ ε-閉包(T_c) = ф = D

對於狀態F

∴ T_a = ∅	∴ T_b = {7}	T_c = {10}
∴ ε-閉包(T_a) = ∅ = D	∴ ε-閉包(T_b) = = ε-閉包(7) = {7,8,6,9,12} = F	∴ ε-閉包(10) = {10, 9, 11, 12} = G

對於狀態G

∴ T_a = ∅	∴ T_b = {7}	T_c = {10}
∴ ε-閉包(ф) = ф = D	∴ ε-閉包(ф) = ф = D	∴ ε-閉包(10) = G

對於狀態D

D = ∅

T_a = T_b = T_c = ∅

ε-閉包(T_a) = ε-閉包(T_b) = ε-閉包(T_c) = ф = D

DFA的狀態轉換表和圖將是：

(初始狀態)

Ginni

更新於：2021年10月29日

901 次瀏覽

透過完成課程獲得認證

為下列語言構造NFA，並使用演算法將其轉換為DFA - L = (aa+ (bb*)c*)