147038069_s2tic
DESCRIPTION
sd mdTRANSCRIPT
ԑ
NAMA : FAUZIAH NURNIM : 147038069KELAS : KOM C/S2TIMATKUL : DESAIN KOMPILER
Tugas 02
1. Diberikan RE : a*(a | b)aaa) Bangunlah NFA yang ekivalen.b) Konversikan NFA ini menjadi sebuah DFA menggunakan Algoritma Subset
Construction.Jawab:
1. NFA ekivalen:
State awal DFA:S0’ = {1,2}Move (S0’,a) = ԑ-closure({t | sԑ{1,2} dan sat ԑ T
= ԑ-closure({1,3})= {3,1,2}= S1’
Move (S0’,b) = ԑ-closure({t | sԑ{1,2} dan sbt ԑ T= ԑ-closure({3})= {3,1,2}= S1’
Move (S1’,a) = ԑ-closure({t | sԑ{3,1,2} dan sat ԑ T= ԑ-closure({4})= {4,3,1,2}= S2’
Move (S1’,b) = ԑ-closure({t | sԑ{3,1,2} dan sbt ԑ T= ԑ-closure({})= {} (tidak ada transisi dari S1’ pada b)
1
2
3 4 5
a
a
b
a a
ԑ
ԑ
Move (S2’,a) = ԑ-closure({t | sԑ{4,3,1,2} dan sat ԑ T= ԑ-closure({5})= {5,4,3,1,2}= S3’
Move (S2’,b) = ԑ-closure({t | sԑ{4,3,1,2} dan sbt ԑ T= ԑ-closure({})= {} (tidak ada transisi dari S2’ pada b)
Move (S3’,a) = ԑ-closure({t | sԑ{5,4,3,1,2} dan sat ԑ T= ԑ-closure({})= {} (tidak ada transisi dari S3’ pada a)
Move (S3’,b) = ԑ-closure({t | sԑ{5,4,3,1,2} dan sbt ԑ T= ԑ-closure({})= {} (tidak ada transisi dari S3’ pada b)
DFA yang dihasilkan:
2. Diberikan RE: ((a | b)(a | bb))*a) Bangunlah NFA yang ekivalen.b) Konversikan NFA ini menjadi sebuah DFA menggunakan Algoritma Subset
Construction.Jawab:
2. NFA ekivalen:
S1’a
S0’ S2’ S3’
b
a
a
1 2 3
41
5 6ԑ
ԑ
ԑ
a
b
a
bb
ԑ
ԑ
State awal DFA:S0’ = {1,2}Move (S0’,a) = ԑ-closure({t | sԑ{1,2} dan sat ԑ T
= ԑ-closure({3})= {3,1,2}= S1’
Move (S0’,b) = ԑ-closure({t | sԑ{1,2} dan sbt ԑ T= ԑ-closure({3})= {3,1,2}= S1’
Move (S1’,a) = ԑ-closure({t | sԑ{3,1,2} dan sat ԑ T= ԑ-closure({5})= {5,3,1,2}= S2’
Move (S1’,b) = ԑ-closure({t | sԑ{3,1,2} dan sbt ԑ T= ԑ-closure({4})= {4,3,1,2}= S3’
Move (S2’,a) = ԑ-closure({t | sԑ{5,3,1,2} dan sat ԑ T= ԑ-closure({})= {} (tidak ada transisi dari S2’ pada a)
Move (S2’,b) = ԑ-closure({t | sԑ{5,3,1,2} dan sbt ԑ T= ԑ-closure({4})= {4,5,3,1,2}= S3’
DFA yang dihasilkan:
S0’
S1’
S2’
S3’
a
ba
b
b
ԑ
3. Buatlah DFA yang ekivalen dengan NFA dibawah ini:
Jawab:State awal DFA:S0’ = {0}Move (S0’,a) = ԑ-closure({t | sԑ{0} dan sat ԑ T
= ԑ-closure({1})= {1,0}= S1’
Move (S0’,b) = ԑ-closure({t | sԑ{0} dan sbt ԑ T= ԑ-closure({})= {} (tidak ada transisi dari S0’ pada b)
Move (S1’,a) = ԑ-closure({t | sԑ{1,0} dan sat ԑ T= ԑ-closure({2})= {2,1,0}= S2’
Move (S1’,b) = ԑ-closure({t | sԑ{1,0} dan sbt ԑ T= ԑ-closure({0,2})= {2,1,0}= S2’
Move (S2’,a) = ԑ-closure({t | sԑ{2,1,0} dan sat ԑ T= ԑ-closure({3})= {3,2,1,0}= S3’
Move (S2’,b) = ԑ-closure({t | sԑ{2,1,0} dan sbt ԑ T= ԑ-closure({})= {} (tidak ada transisi dari S2’ pada b)
Move (S3’,a) = ԑ-closure({t | sԑ{3,2,1,0} dan sat ԑ T= ԑ-closure({2})= {3,2,1,0}= S3’
ԑ
Move (S3’,b) = ԑ-closure({t | sԑ{3,2,1,0} dan sbt ԑ T= ԑ-closure({})= {} (tidak ada transisi dari S3’ pada b)
DFA yang dihasilkan:
4. Minimalkanlah DFA berikut:
jawab:
G1 = {0}G2 = {1,2,3,4}
S0’
S1’
S3’S2’
a
b a
a
a
ԑ
Tabel transisi:a)
b)
c)
d)
e)
f)
G1 a b0 G2 G2
G2 a b1 G2 -2 G2 -3 G2 G1
4 G2 G1
G3 a b1 G3 -2 G4 -
G4 a b3 G4 G1
4 G4 G1
G5 a b1 G6 -
G6 a b2 G4 -
Nilai:G1 = 0G2 =1,2,3,4
G1 = 0G3 = 1,2G4 = 3,4
G1 = 0G4 = 3,4G5 = 1G6 = 2
Minimal DFA:
G1
G5
G4
G6
a
a
b
ba
a
ԑ
5. Minimalkanlah DFA berikut:
Jawab:G1 = {4}G2 = {0,1,2,3,5}
Tabel transisi:a)
b)
c)
d)
G1 a b4 G2 G2
G2 a b0 G2 G2
1 G2 G1
2 G2 G2
3 - G1
5 G2 G2
G3 a b0 G5 G4
2 G3 G3
5 G3 G3
G4 a b1 G3 G1
Nilai:G1 = 4G2 =0,1,2,3,5
G1 = 0G3 = 0,2,5G4 = 1G5 = 3
G1 = 0G4 = 3,4G5 = 1G6 = 2
Minimal DFA:
G1
G5
G4
G6
a
a
b
ba
a
ԑ
e)
f)
g)
h)
G5 a b3 - G1
G6 a b0 G5 G4
G7 a b2 G7 G7
5 G7 G7
G1 a b4 G4 G4