为下列语言构造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 次浏览

启动您的职业生涯

通过完成课程获得认证

开始学习
广告
© . All rights reserved.