06PFT
Daftar Nama Kelompok:
- Antonius Tirta Surya – 1501166213
- Herlina Astari – 1501155506
- Putri Indah – 1501210536
- Steven – 1501154182
Soal:
Diketahui RE = a(ab*a+|ba*b+)#
Buatlah DFA (yang sudah diminimisasi) dari RE tersebut dengan menggunakan 2 cara, yaitu cara tree dan cara dengan melalui ε-NFA!
Jawab:
CARA TREE
Firstpos dan Lastpos
Followpos
Followpos 1 = 2,5
Followpos 2 = 3,4,8
Followpos 3 = 3,4,8
Followpos 4 = 4,8
Followpos 5 = 6,7
Followpos 6 = 6,7
Followpos 7 = 7,8
Followpos 8 = –
Tabel DFA
|
a |
b |
|
|
S0 |
2,5 (S1) |
– |
|
S1 |
3,4,8 (S2) |
6,7 (S3) |
|
S4 |
4,8 (S4) |
7,8 (S5) |
|
S3 |
S3 |
– |
|
S4 |
S4 |
– |
|
S5 |
– |
S5 |
DFA
CARA ε-NFA
ε-closure
ε-closure({0})={0} -> S1
ε-closure({S0,a}) = ε-closure({1}) = {1,2,8} ->S1
ε-closure({S0,b}) = –
ε-closure({S1,a}) = ε-closure({3}) = {3,4,6} ->s2
ε-closure({S1,b}) = ε-closure({9}) = {9,10,12} ->s3
ε-closure({S2,a}) = ε-closure({7}) = {6,7,14} ->S4
ε-closure({S2,b}) = ε-closure({5}) = {4,5,6} ->S5
ε-closure({S3,a}) = ε-closure({11}) = {11,12,10} ->S6
ε-closure({S3,b}) = ε-closure({13}) = {12,13,14} ->S7
ε-closure({S4,a}) = ε-closure({7}) = s4
ε-closure({S4,b}) = –
ε-closure({S5,a}) = ε-closure({7}) = S4
ε-closure({S5,b}) = ε-closure({5}) = S5
ε-closure({S6,a}) = ε-closure({11}) = S6
ε-closure({S6,b}) = ε-closure({13}) = S7
ε-closure({S7,a}) = –
ε-closure({S7,b}) = ε-closure({13}) = S7
Tabel Minimisasi DFA
|
a |
b |
|
|
S0 |
S1 |
– |
|
S1 |
S2 |
S3 |
|
S2 |
S4 |
S5 |
|
S3 |
S6 |
S7 |
|
S4* |
S4* |
– |
|
S5 |
S4 |
S5 |
|
S6 |
S6 |
S7 |
|
S7* |
– |
S7* |
DFA
