Tugas :
Membuat DFA dari RE dengan metode Tree dan ε-NFA, dengan syarat :
- Jumlah state DFA minimal 5 state dan maximal 8 state.
- Jumlah final state DFA minimal 2 state dan maximal 3 state.
1. RE : ( a | b )* ( aa | bb )
2. Membuat DFA dengan Metode Tree
RE : ( a | b )* ( a a | b b ) . #
Index : 1 2 3 4 5 6 7
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* |
Minimalisasi DFA
DFA sudah dalam bentuk minimal karena tidak ada state yang mempunyai index yang sama pada inputan a dan b dengan state yang lainnya.
3. Membuat DFA dengan Metode ε-NFA
Kelompok 5 :
Bernardus Robby – 1501144332
Rifan Wijaya – 1501145700
Glory Tannia – 1501187470
Haris Winoto – 1501188611