Soal :
Buatlah Soal RE dan konversikan ke DFA dengan 2 cara , berikut constraintnya:
- Jumlah State DFA min 5 dan max 8.
- Jumlah Final State DFA min 2 dan max 3.
Tentukan : DFA dengan menggunakan metode tree dan metode ε-NFA dan buatlah Minimized DFA
RE : ( a | b )* ( aa | bb )
Dengan metode tree dan followpos
1 2 3 4 5 6 7
( a | b )* . ( a . a | b . b ) . #
S0 = 1,2,3,5
Followpos 1 = 1, 2, 3, 5
Followpos 2 = 1, 2, 3, 5
Followpos 3 = 4
Followpos 4 = 7
Followpos 5 = 6
Followpos 6 = 7
Followpos 7 = –
|
a |
b |
|
|
-> S0 {1,2,3,5} |
Followpos(1,3) = {1,2,3,4,5} = S1 |
Followpos(2,5) = {1,2,3,5,6} = S2 |
|
S1 {1,2,3,4,5} |
Followpos(1,3,4) = {1,2,3,4,5,7} = S3* |
Followpos(2,5) = S2 |
|
S2 {1,2,3,5,6} |
Followpos(1,3) = S1 |
Followpos(2,5,6) = {1,2,3,5,6,7} = S4* |
|
S3* {1,2,3,4,5,7} |
Followpos(1,3,4) = S3* |
Followpos(2,5,7) = {1,2,3,5,6} = S2 |
|
S4* {1,2,3,5,6,7} |
Followpos(1,3) = S1 |
Followpos(2,5,6) = S4* |
sehingga DFA yang dihasilkan
Minimalisasi DFA
Memisahkan final sate dengan non-final state
Karena tidak adanya state yang memiliki index yang sama pada inputan a dan b dengan state lainnya maka DFA yang ada sudah merupakan DFA minimal
Dengan metode ε– NFA dan ε – Closure
Kelompok 5
Bernardus Robby 1501144332
Glory Tania 1501187470
Haris Winoto 1501188611
Rifan Wijaya 1501145700