Untuk konversi dari RE (Regular Expression) ke DFA dapat dilakukan dengan menggunakan 2 cara, yaitu:
- Dengan menggunakan metode Thomson’s Construction (ɛ-NFA) lalu baru ke DFA
- Dengan menggunakan konversi ke tree terlebih dahulu
Berikut adalah contoh untuk konversinya:
RE: ab(a|b)*ab* | ab(a|b)+ #
- Dengan cara ke – 1 :
– Langkah pertama gambarkan ɛ-NFA dari RE tersebut.
– Setelah itu tentukan ɛ-closure untuk mendapatkan state pada DFA, dengan cara sebagai berikut:
S0 = ɛ-closure(0) = {0, 1, 15}
ɛ-closure(move(S0, a)) = ɛ-closure({2, 16}) = {2, 16} = S1
ɛ-closure(move(S0, b)) = –
ɛ-closure(move(S1, a)) = –
ɛ-closure(move(S1, b)) = ɛ-closure({3, 17}) = {3, 4, 5, 7, 10, 17, 18, 20} = S2
ɛ-closure(move(S2, a)) = ɛ-closure({6, 11, 19}) = {4, 5, 6, 7, 9, 10, 11, 12, 14, 17, 18, 19, 20, 22, 23} = S3*
ɛ-closure(move(S2, b)) = ɛ-closure({8, 21}) = {4, 5, 7, 8, 9, 10, 17, 18, 20, 21, 22, 23} = S4*
ɛ-closure(move(S3, a)) = ɛ-closure({6, 11, 19}) = S3*
ɛ-closure(move(S3, b)) = ɛ-closure({8, 13, 21}) = {4, 5, 7, 8, 9, 10, 12, 13, 14, 17, 18, 20, 21, 22, 23} = S5*
ɛ-closure(move(S4, a)) = ɛ-closure({6, 11, 19}) = S3*
ɛ-closure(move(S4, b)) = ɛ-closure({8, 21}) = S4*
ɛ-closure(move(S5, a)) = ɛ-closure({6, 11, 19}) = S3*
ɛ-closure(move(S5, b)) = ɛ-closure({8, 13, 21}) = S5*
– Selanjutnya, gambarkan state DFA tersebut:
– Selanjutnya DFA tersebut akan di minimalisasikan menjadi minimized DFA dengan cara:
Berikut adalah gambar hasil dari Minimized DFA:
2. Dengan cara ke- 2:
– Langkah pertama tentukan follow pos dari RE tersebut:
Follow pos 1 = 2
Follow pos 2 = 3, 4, 5
Follow pos 3 = 3, 4, 5
Follow pos 4 = 3, 4, 5
Follow pos 5 = 6
Follow pos 6 = 6, 11
Follow pos 7 = 8
Follow pos 8 = 9, 10
Follow pos 9 = 9, 10, 11
Follow pos 10 = 9, 10, 11
Follow pos 11 = –
– Langkah selanjutnyagambarkan treenya dari RE tersebut untuk menentukan S0:
Didapat S0 = {1, 7}
– Selanjutnya buatlah table untuk menentukan dfanya:
|
a |
b |
|
|
S0 |
2, 8 = S1 |
– |
|
S1 |
– |
3, 4, 5, 9, 10 = S2 |
|
S2 |
3, 4, 5, 6, 9, 10, 11 = S3* |
3, 4, 5, 9, 10, 11 = S4* |
|
S3 |
3, 4, 5, 6, 9, 10, 11 = S3* |
3, 4, 5, 6, 9, 10, 11 = S3* |
|
S4 |
3, 4, 5, 6, 9, 10, 11 = S3* |
3, 4, 5, 9, 10, 11 = S4* |
Untuk hasil DFA dari cara ini didapat hasilnya merupakan DFA minimizednya sehingga gambarnya menjadi:
Sekian penjelasan mengenai konversi RE ke DFA. Semoga bermanfaat untuk Anda 
Recent Comments