lisensi ini mengizinkan setiap orang untuk menggubah ...kc.umn.ac.id/1793/1/halaman awal.pdf ·...
TRANSCRIPT
Team project ©2017 Dony Pratidana S. Hum | Bima Agus Setyawan S. IIP
Hak cipta dan penggunaan kembali:
Lisensi ini mengizinkan setiap orang untuk menggubah, memperbaiki, dan membuat ciptaan turunan bukan untuk kepentingan komersial, selama anda mencantumkan nama penulis dan melisensikan ciptaan turunan dengan syarat yang serupa dengan ciptaan asli.
Copyright and reuse:
This license lets you remix, tweak, and build upon work non-commercially, as long as you credit the origin creator and license it on your new creations under the identical terms.
IMPLEMENTASI NONDETERMINISTIC FINITE
AUTOMATA UNTUK IDENTIFIKASI TENSES PADA
APLIKASI PENERJEMAH BAHASA INGGRIS
SKRIPSI
Diajukan sebagai persyaratan untuk memperoleh gelar
Sarjana Komputer Program Strata Satu (S1)
Viriya Putra Djaslim
NIM : 09110110080
UNIVERSITAS MULTIMEDIA NUSANTARA
TANGERANG
2014
ii
LEMBAR PENGESAHAN SKRIPSI
IMPLEMENTASI NONDETERMINISTIC FINITE AUTOMATA UNTUK
IDENTIFIKASI TENSES PADA APLIKASI PENERJEMAH BAHASA
INGGRIS
Oleh
Nama : Viriya Putra Djaslim
NIM : 09110110080
Fakultas : Teknologi Informasi dan Komunikasi
Program Studi : Teknik Informatika
Tangerang, 8 Mei 2014
telah diujikan pada Senin, 28 April 2014 pukul 15.00 s.d. 17.00 dan dinyatakan
lulus dengan susunan penguji sebagai berikut
Ketua Sidang Dosen Penguji
Dodick Z. S., S.Kom.,
B.App. Sc., M.T.I.
Seng Hansun, S.Si., M.Cs.
Dosen Pembimbing
Adhi Kusnadi, M.Si.
Disahkan oleh
Ketua Program Studi Teknik Informatika UMN
Maria Irmina P., S.Kom., M.T.
Implementasi Nondeterministic ..., Viriya Putra Djaslim, FTI UMN, 2014
iii
LEMBAR PERNYATAAN TIDAK MELAKUKAN PLAGIAT
Dengan ini saya:
Nama : Viriya Putra Djaslim
NIM : 09110110080
Fakultas : Teknologi Informasi dan Komunikasi
Program Studi : Teknik Informatika
Menyatakan bahwa skripsi ini adalah karya ilmiah saya sendiri, bukan hasil
plagiat dari karya ilmiah yang ditulis oleh orang lain atau lembaga lain, dan semua
karya ilmiah orang lain atau lembaga lain yang dirujuk dalam skripsi ini telah
disebutkan sumber kutipannya serta dicantumkan di Daftar Pustaka.
Jika di kemudian hari terbukti ditemukan kecurangan/ penyimpangan, baik dalam
pelaksanaan skripsi maupun dalam penulisan laporan skripsi, saya bersedia
menerima konsekuensi dinyatakan TIDAK LULUS untuk mata kuliah Skripsi
yang telah saya tempuh.
Tangerang, 8 Mei 2014
Viriya Putra Djaslim
Implementasi Nondeterministic ..., Viriya Putra Djaslim, FTI UMN, 2014
iv
IMPLEMENTASI NONDETERMINISTIC FINITE AUTOMATA UNTUK
IDENTIFIKASI TENSES PADA APLIKASI PENERJEMAH BAHASA
INGGRIS
ABSTRAK
Perangkat penerjemah bahasa asing yang ada saat ini sudah sangat baik
dan dapat menerjemahkan kalimat, bahkan satu laman situs di internet, khususnya
dari yang berbahasa Inggris ke dalam bahasa Indonesia, namun dalam prosesnya
tidak terdapat penjelasan mengenai apa jenis kalimat itu dan untuk apa
penggunaannya. Melalui penelitian ini, akan dibangun sebuah aplikasi yang
mampu menerjemahkan dan mengidentifikasi jenis kalimat (tenses) dari bahasa
Inggris ke bahasa Indonesia dengan menerapkan automata pada prosesnya. Selain
menitikberatkan pada penerjemahan kalimat, penelitian ini juga memaparkan
bagaimana proses Nondeterministic Finite Automata (NFA) diterapkan untuk
mengidentifikasi jenis kalimat hasil penerjemahan bahasa Inggris ke bahasa
Indonesia. Hasil dari penelitian ini menunjukkan bahwa Nondeterministic Finite
Automata dapat digunakan untuk melakukan identifikasi jenis kalimat (tenses)
pada aplikasi penerjemah dengan tingkat Word Error Rate (WER) terendah yang
dicapai adalah 4% dan total kalimat yang teridentifikasi sejumlah 17 kalimat dari
39 kalimat.
Kata kunci: NFA, Nondeterministic Finite Automata, identifikasi, penerjemah,
Bahasa Inggris, Bahasa Indonesia.
Implementasi Nondeterministic ..., Viriya Putra Djaslim, FTI UMN, 2014
v
IMPLEMENTATION OF NONDETERMINISTIC FINITE AUTOMATA FOR
TENSES IDENTIFICATION ON ENGLISH TRANSLATOR APPLICATION
ABSTRACT
Nowadays translator tools are well made and could translate language
clearly, even a whole page on the website, especially from english to bahasa,
eventhough in the process there is no explanation about what kind of tenses and
what are the tenses is used for. From this research, an aplication which could
translate and indentify the kind of tenses from english to bahasa will be built
using automata in the process. Despite from focussing on the sentence translation,
this research will also explain how Nondeterministic Finite Automata (NFA) will
be used to identify sentences that had been translated from english into bahasa.
The result of this research shows that Nondeterministic Finite Automata could be
used to identify kind of tenses from the translator with the lowest Word Error Rate
(WER) score is about 4% and the total of identified tenses are seventeen from
thirty nine sentences.
Keywords: NFA, Nondeterministic Finite Automata, indentify, translate, English,
Bahasa.
Implementasi Nondeterministic ..., Viriya Putra Djaslim, FTI UMN, 2014
vi
KATA PENGANTAR
Adalah sebuah keberhasilan mengalahkan diri dalam perang besar. Seperti
itulah kebahagiaan yang tak dapat terlukiskan yang menjadi ungkapan isi hati
penulis atas syukur yang telah diberikan oleh Sang Khalik sehingga penulis
berhasil menyelesaikan laporan sripsi yang berjudul “Implementasi
Nondeterministic Finite Automata untuk Identifikasi Tenses pada Aplikasi
Penerjemah Bahasa Inggris“ ini. Laporan Skripsi ini diajukan kepada Program
Strata I Fakultas Teknologi Informasi dan Komunikasi Universitas Multimedia
Nusantara sebagai salah satu syarat kelulusan Program Studi S-1 Teknik
Informatika dan memperoleh gelar Sarjana Komputer.
Dalam keberhasilan menyelesaikan laporan skripsi ini tentunya tidak
terlepas dari kerja sama berbagai pihak, untuk itu izinkan penulis mengucapkan
terima kasih banyak kepada:
1. Dr. Ninok Leksono, selaku Rektor Universitas Multimedia Nusantara,
2. Maria Irmina Prasetiyowati, S.Kom., M.T., selaku Ketua Program Studi
Teknik Informatika yang turut memberi masukan kepada penulis dalam
menyelesaikan laporan skripsi ini.
3. Adhi Kusnadi, M.Si., selaku pembimbing penulis yang dengan sabar
menjawab semua pertanyaan penulis serta membimbing penulis dengan
penuh tanggung jawab dan kesungguhan.
4. Bapak Dodick Zulaimi Sudirman, S.Kom., B.App.Sc., M.T.I., selaku ketua
sidang.
5. Bapak Seng Hansun, S.Si., M.Cs., selaku dosen penguji.
Implementasi Nondeterministic ..., Viriya Putra Djaslim, FTI UMN, 2014
vii
6. Keluarga penulis, khususnya orang tua penulis yang banyak memberi
dukungan kepada penulis untuk segera menyelesaikan Skripsi ini.
7. Saudara Handika Chandra, Aditya Yulianto, Andri Murfih, Adi Chandra
Halim, David Cahaya dan sahabat-sahabat penulis yang membantu penulis
dalam segala hal selama mengerjakan laporan ini.
8. Seluruh pihak yang telah membantu penulis menyelesaikan laporan ini.
Penulis berharap agar laporan skripsi ini dapat memberikan manfaat bagi
para pembaca yang terutama adalah mahasiswa Universitas Multimedia Nusantara
dalam mengembangkan teknologi informasi dan komunikasi.
Tangerang, 8 Mei 2014
Penulis
Implementasi Nondeterministic ..., Viriya Putra Djaslim, FTI UMN, 2014
viii
DAFTAR ISI
LEMBAR PENGESAHAN SKRIPSI .................................................................... ii
LEMBAR PERNYATAAN TIDAK MELAKUKAN PLAGIAT ......................... iii
ABSTRAK ............................................................................................................. iv
ABSTRACT ...............................................................................................................v
KATA PENGANTAR ........................................................................................... vi
DAFTAR ISI ........................................................................................................ viii
DAFTAR GAMBAR ...............................................................................................x
DAFTAR TABEL ................................................................................................. xii
BAB I PENDAHULUAN ........................................................................................1
1.1 Latar Belakang ..................................................................................................1
1.2 Perumusan Masalah ..........................................................................................3
1.3 Pembatasan Masalah .........................................................................................4
1.4 Tujuan Penelitian ..............................................................................................4
1.5 Manfaat Penelitian ............................................................................................5
1.6 Sistematika Penulisan .......................................................................................5
BAB II LANDASAN TEORI .................................................................................7
2.1 Finite Automata ................................................................................................7
2.1.1 Definisi Finite Automata ...........................................................................7
2.1.2 Deterministic Finite Automata dan Nondeterministic Finite Automata ...7
2.1.3 Deterministic Finite Automata ..................................................................7
2.1.4 Nondeterministic Finite Automata ..........................................................11
2.1.5 Penerapan Finite Automata .....................................................................14
2.2 Jenis-jenis kalimat bahasa Inggris (tenses) .....................................................17
2.3 Tatanan Kata dan Contoh Kalimat Bahasa Inggris ........................................21
2.4 Word Error Rate (WER) .................................................................................29
2.5 Cronbach’s Alpha ...........................................................................................30
2.6 Tingkat Kepuasan Pengguna Aplikasi ............................................................32
BAB III ANALISIS DAN PERANCANGAN APLIKASI ..................................35
3.1 Metode Penelitian ...........................................................................................35
3.2 Analisis Aplikasi.............................................................................................36
3.2.1 Analisis Nondeterministic Finite Automata ............................................37
3.2.2 Entity Relationship Diagram ...................................................................67
Implementasi Nondeterministic ..., Viriya Putra Djaslim, FTI UMN, 2014
ix
3.2.3 Struktur Tabel..........................................................................................67
3.2.4 Flowchart Sistem .....................................................................................74
3.2.5 Potongan Source Code Program .............................................................88
3.3 Perancangan Aplikasi .....................................................................................94
3.3.1 Struktur Navigasi Menu ..........................................................................94
3.3.2. Perancangan Antarmuka .........................................................................96
BAB IV IMPLEMENTASI DAN UJI COBA ....................................................102
4.1 Spesifikasi Perangkat ....................................................................................102
4.2 Implementasi Aplikasi ..................................................................................102
4.3 Uji Coba Aplikasi .........................................................................................106
4.3.1 Tempat dan Waktu Pengujian ...............................................................106
4.3.2 Persiapan Pengujian ..............................................................................106
4.3.3 Skenario Pengujian................................................................................108
4.3.4 Hasil Uji Coba Aplikasi TranslatorId ...................................................109
4.3.5 Hasil Uji Coba Aplikasi Google Translate............................................116
4.3.5 Hasil kuesioner aplikasi TranslatorId....................................................123
BAB V KESIMPULAN DAN SARAN ..............................................................127
5.1 Kesimpulan ...................................................................................................127
5.2 Saran .............................................................................................................128
DAFTAR PUSTAKA ..........................................................................................129
DAFTAR LAMPIRAN ........................................................................................131
RIWAYAT HIDUP ..............................................................................................132
Implementasi Nondeterministic ..., Viriya Putra Djaslim, FTI UMN, 2014
x
DAFTAR GAMBAR
Gambar 2.1 Gambar Notasi Five Tuple ...................................................................8 Gambar 2.2 Diagram Transisi DFA Penerima String Dengan Substring 01
(Sumber: Hopcroft, 2007) ........................................................................................9 Gambar 2.3 DFA untuk Kata – Kata Penyusun Nilai Mata Uang Inggris (Sumber:
Jurafsky, 2009) .......................................................................................................10 Gambar 2.4 Diagram Transisi NFA Penerima String Berakhiran 01 ....................12 Gambar 2.5 Skema Proses Pembacaan String “00101” Oleh NFA .......................13
Gambar 2.6 Deskripsi Game Menggunakan Finite Automata ...............................16 Gambar 2.7 Gambar Diagram English Tenses .......................................................18 Gambar 2.8 Rumus WER .......................................................................................29 Gambar 2.9 Rumus Cronbach alpha ......................................................................30 Gambar 2.10 Skema Tingkat Kepuasan Pengguna Aplikasi .................................33 Gambar 3.1 Gambar NFA Simple Present Tense jenis 1 (kalimat positif) ............39
Gambar 3.2 Gambar NFA Simple Present Tense jenis 1 (kalimat negatif) ...........40 Gambar 3.3 Gambar NFA Simple Present Tense jenis 1 (kalimat tanya) ..............41 Gambar 3.4 Gambar NFA Simple Present Tense jenis 2 (kalimat positif dan
negatif) ...................................................................................................................42 Gambar 3.5 Gambar NFA Simple Present Tense jenis 2 (kalimat tanya) ..............42
Gambar 3.6 Gambar NFA Present Continous Tense (kalimat positif dan negatif)
................................................................................................................................43 Gambar 3.7 Gambar NFA Present Continous Tense (kalimat tanya) ....................44 Gambar 3.8 Gambar NFA Present Perfect Tense (kalimat positif dan negatif) ....45 Gambar 3.9 Gambar NFA Present Perfect Tense (kalimat tanya).........................46 Gambar 3.10 Gambar NFA Present Perfect Continous Tense (kalimat positif dan
negatif) ...................................................................................................................47 Gambar 3.11 Gambar NFA Present Perfect Continous Tense (kalimat tanya) .....48 Gambar 3.12 Gambar NFA Simple Past Tense jenis 1 (kalimat positif) ...............49 Gambar 3.13 Gambar NFA Simple Past Tense jenis 1 (kalimat negatif) ..............50 Gambar 3.14 Gambar NFA Simple Past Tense jenis 1 (kalimat tanya) .................51 Gambar 3.15 Gambar NFA Simple Past Tense jenis 2 (kalimat positif dan negatif)
................................................................................................................................52 Gambar 3.16 Gambar NFA Simple Past Tense jenis 2 (kalimat tanya) .................52 Gambar 3.17 Gambar NFA Past Continous Tense (kalimat positif dan negatif) ..53 Gambar 3.18 Gambar NFA Past Continous Tense (kalimat tanya) .......................54 Gambar 3.19 Gambar NFA Past Perfect Tense (kalimat positif dan negatif) .......55 Gambar 3.20 Gambar NFA Past Perfect Tense (kalimat tanya) ............................56
Gambar 3.21 Gambar NFA Past Perfect Continous Tense (kalimat positif dan
negatif) ...................................................................................................................57 Gambar 3.22 Gambar NFA Past Perfect Continous Tense (kalimat tanya) ..........58 Gambar 3.23 Gambar NFA Future Simple Tense (kalimat positif dan negatif) ....59 Gambar 3.24 Gambar NFA Future Simple Tense (kalimat tanya).........................60
Gambar 3.25 Gambar NFA Future Continous Tense (kalimat positif dan negatif)
................................................................................................................................61
Gambar 3.26 Gambar NFA Future Continous Tense (kalimat tanya) ...................62
Implementasi Nondeterministic ..., Viriya Putra Djaslim, FTI UMN, 2014
xi
Gambar 3.27 Gambar NFA Future Perfect Tense (kalimat positif dan negatif) ...63 Gambar 3.28 Gambar NFA Future Perfect Tense (kalimat tanya) ........................64 Gambar 3.29 Gambar NFA Future Perfect Continous Tense (kalimat positif dan
negatif) ...................................................................................................................65 Gambar 3.30 Gambar NFA Future Perfect Continous Tense (tanya) ...................66 Gambar 3.31 Entity Relationship Diagram ............................................................67 Gambar 3.32 Flowchart Sistem TranslatorId ........................................................74 Gambar 3.33 Gambar Subproses Translate & Identify Tenses ..............................75 Gambar 3.34 Gambar Subproses Arrange Sequence Process ...............................77
Gambar 3.35 Gambar Subproses Distinguish Tenses ............................................78 Gambar 3.36 Flowchart Sistem Penelusuran State ................................................80 Gambar 3.37 Gambar Subproses Show, Insert, And Delete Words .......................82 Gambar 3.38 Gambar Subproses Show Words ......................................................83 Gambar 3.39 Gambar Subproses Insert Word .......................................................85 Gambar 3.40 Gambar Subproses Delete Word ......................................................87 Gambar 3.41 Potongan source code Translate Sentences .....................................89 Gambar 3.42 Potongan source code Translate Sentences (cont’d)........................90 Gambar 3.43 Potongan source code Arrange Sequence Process ..........................91 Gambar 3.44 Potongan source code GetNextState & Distinguish Tenses .............92 Gambar 3. 45 Potongan source code Show Words ................................................93
Gambar 3.46 Potongan source code insert word ...................................................93 Gambar 3.47 Potongan source code insert verb ....................................................93 Gambar 3.48 Potongan source code delete word ...................................................94 Gambar 3.49 Navigasi Menu Aplikasi ...................................................................94 Gambar 3.50 Rancangan Tatap Muka Halaman Utama.........................................96 Gambar 3.51 Rancangan Tatap Muka Penerjemah ................................................97 Gambar 3.52 Rancangan Tatap Muka Halaman Kosa Kata ..................................98 Gambar 3.53 Rancangan Tatap Muka Halaman Bantuan ......................................99 Gambar 3.54 Rancangan Tatap Muka Tentang Aplikasi .....................................100 Gambar 3.55 Rancangan Tatap Muka Keluar dari Aplikasi ................................101 Gambar 4.1 Gambar Halaman Utama ..................................................................103
Gambar 4.2 Gambar Halaman Penerjemah ..........................................................103
Gambar 4.3 Gambar Halaman Kosa Kata ............................................................104 Gambar 4.4 Halaman Bantuan .............................................................................105
Gambar 4.5 Halaman Tentang Aplikasi ...............................................................105 Gambar 4.6 Gambar Uji Coba Aplikasi ...............................................................109
Implementasi Nondeterministic ..., Viriya Putra Djaslim, FTI UMN, 2014
xii
DAFTAR TABEL
Tabel 2.1 Tabel Transisi DFA Penerima String dengan Substring “01” ...............11 Tabel 2.2 Tabel Transisi NFA Penerima String Berakhiran “01” .........................12 Tabel 2.3 Tabel indeks skor Cronbach alpha .........................................................30 Tabel 3.1 Tabel ADJECTIVE ................................................................................68
Tabel 3.2 Tabel ADVERB .....................................................................................68 Tabel 3.3 Tabel ARTICLE .....................................................................................68 Tabel 3.4 Tabel AUXILIARY ...............................................................................69
Tabel 3.5 Tabel AUXILIARY_PAST ...................................................................69 Tabel 3.6 Tabel CONJUNCTION .........................................................................69 Tabel 3.7 Tabel DETERMINER ............................................................................70 Tabel 3.8 Tabel MODAL .......................................................................................70 Tabel 3.9 Tabel NOUN ..........................................................................................70 Tabel 3.10 Tabel PREPOSITION .........................................................................71 Tabel 3.11 Tabel PRONOUN ................................................................................71 Tabel 3.12 Tabel TOBE .........................................................................................71 Tabel 3.13 Tabel TOBE_PAST .............................................................................72 Tabel 3.14 Tabel VERB .........................................................................................72 Tabel 3.15 Tabel WORDS .....................................................................................72
Tabel 3.16 Tabel FINITE_STATE ........................................................................73 Tabel 3.17 Tabel FINITE_STATE_TRANSITION ..............................................73 Tabel 4.1 Tabel Uji Coba I aplikasi TranslatorId ................................................110
Tabel 4.2 Tabel Uji Coba II aplikasi TranslatorId ...............................................110 Tabel 4.3 Tabel Uji Coba III aplikasi TranslatorId ..............................................111 Tabel 4.4 Tabel Uji Coba IV aplikasi TranslatorId..............................................112 Tabel 4.5 Tabel Uji Coba V aplikasi TranslatorId ...............................................113 Tabel 4.6 Tabel Uji Coba VI aplikasi TranslatorId..............................................115 Tabel 4.7 Tabel Uji Coba I aplikasi Google Translate.........................................116 Tabel 4.8 Tabel Uji Coba II aplikasi Google Translate .......................................117 Tabel 4.9 Tabel Uji Coba III aplikasi Google Translate ......................................117 Tabel 4.10 Tabel Uji Coba IV aplikasi Google Translate ....................................118
Tabel 4.11 Tabel Uji Coba V aplikasi Google Translate .....................................120 Tabel 4.12 Tabel Uji Coba VI aplikasi Google Translate ....................................121
Tabel 4.13 Tabel perhitungan WER Aplikasi Google Translate dan TranslatorId
..............................................................................................................................122 Tabel 4.15 Tabel Rata-Rata perhitungan Cronbach alpha ...................................125
Implementasi Nondeterministic ..., Viriya Putra Djaslim, FTI UMN, 2014