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

解答

上述語言的NFA將是：

從NFA到DFA的轉換：

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

對於狀態A


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

對於狀態B


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

對於狀態C


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

對於狀態E


∴ Ta = ∅∴ Tb = ∅Tc = ∅
∴ ε-閉包(Ta) =
             ∅ = D		∴ ε-閉包(Tb) =
                ф = D		∴ ε-閉包(Tc) =
               ф = D

對於狀態F


∴ Ta = ∅∴ Tb = {7}Tc = {10}
∴ ε-閉包(Ta) =
        ∅ = D		∴ ε-閉包(Tb) =
 = ε-閉包(7)
= {7,8,6,9,12}
= F		∴ ε-閉包(10) =
    {10, 9, 11, 12} = G

對於狀態G


∴ Ta = ∅∴ Tb = {7}Tc = {10}
∴ ε-閉包(ф) = ф
= D		∴ ε-閉包(ф) = ф =
 D		∴ ε-閉包(10) =
 G

對於狀態D

D = ∅

Ta = Tb = Tc = ∅

ε-閉包(Ta) = ε-閉包(Tb) = ε-閉包(Tc) = ф = D

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

(初始狀態)



aBc這裡
ABCDA = {0,1,4}
BEDDB = {2}
CDFGC = {5,6,8,9,11,12}
DDDDD = ∅
EDDDE = {3, 12}
FDFGF = {7,8,6,9,11,12}
GDDGG = {10,9,11,12}










更新於：2021年10月29日

901 次瀏覽

啟動您的職業生涯

透過完成課程獲得認證

開始學習
廣告