PROGRAM BANTU TRANSFORMASI TATA BAHASA BEBAS KONTEKS KE BENTUK NORMAL CHOMSKY SKRIPSI

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PROGRAM BANTU TRANSFORMASI TATA BAHASA BEBAS KONTEKS KE BENTUK NORMAL CHOMSKY

SKRIPSI

Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika

Oleh : Wiwit Kristiani NIM : 013114007

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SANATA DHARMA YOGYAKARTA 2007


ii


iii


Motto

Sebab Aku ini mengetahui rancangan-rancangan apa yang ada pada-Ku mengenai kamu, demikianlah firman Tuhan, yaitu rancangan damai sejahtera dan bukan rancangan kecelakaan, untuk memberikan kepadamu hari depan yang penuh harapan.

Terkutuklah orang yang mengandalkan manusia, yang mengandalkan kekuatannya sendiri, dan yang hatinya menjauh daripada Tuhan! ia akan seperti semak bulus di padang belantara, ia tidak akan mengalami datangnya keadaan baik;........................ Diberkatilah orang yang mengandalkan Tuhan, yang menaruh harapannya pada Tuhan! ia akan seperti pohon yang ditanam di tepi air.....................dan yang tidak berhenti menghasilkan buah.

Kado kecil ini dipersembahkan untuk : “ Yang tersayang Bapak dan Ibu serta pribadipribadi yang selalu menyanyangiku...”

iv


PERNYATAAN KEASLIAN KARYA

Penulis menyatakan dengan sesungguhnya bahwa skripsi yang penulis tulis ini tidak memuat karya atau bagian karya dari orang lain, kecuali yang telah disebutkan dalam kutipan dan daftar pustaka, sebagaimana layaknya karya ilmiah.

Yogyakarta, ........................... Penulis,

Wiwit Kristiani

v


ABSTRAK

Bentuk Normal Chomsky merupakan salah satu bentuk akhir dari tata bahasa bebas konteks yang dalam ilmu teori bahasa dan otomata dipakai untuk menunjukkan bagaimana menghasilkan untai-untai dalam sebuah bahasa. Dalam skripsi ini transformasi ke bentuk normal Chomsky diimplementasikan dalam suatu program. Transformasi bisa dilakukan jika tata bahasa bebas konteks sudah mengalami penyederhanaan, yang dilakukan dengan proses pengecekan ketidaksederhanaan tata bahasa bebas konteks oleh program. Penulisan input tata bahasa bebas konteks menggunakan tombol – tombol yang disediakan program pada layar ‘Layar_Input_Produksi’ dengan simbol awal S, simbol terminal yang terdiri dari huruf ‘a’ sampai ‘e dan non terminal terdiri dari huruf kapital ‘A’ sampai ‘E’ dan ‘S’. Hasil dari implementasi proses transformasi ini ditampilkan dalam dua langkah. Langkah pertama menampilkan hasil input yang sudah dalam bentuk normal Chomsky dan perubahan terminal lebih dari satu menjadi non terminal. Langkah kedua merupakan hasil akhir tata bahasa bebas konteks dalam bentuk normal Chomsky dengan menampilkan hasil langkah pertama yang sudah dalm bentuk normal Chomsky dan hasil perubahan non terminal dalam langkah pertama yang lebih dari dua menjadi tepat 2 non terminal. Hasil transformasi menunjukkan untuk setiap M produksi, N non terminal, K terminal, dengan P jumlah simbol tiap hasil produksi, maka maksimum jumlah produksi pada langkah pertama didapatkan (M+K) produksi dan maksimum jumlah produksi pada langkah ke dua (bentuk normal Chomsky) didapatkan (M+K)+(P-2) produksi.

vi


ABSTRACT Chomsky Normal Form is one of the form in simplifying Contexs Free Grammar that in grammar and automata theory is used to show how to generate derivation in a grammar. In this thesis transformation Contexs Free Grammar to Chomsky Normal Form is implemented. Transformation can be executed if Context Free Grammar is in the simple form. The writing of program which is provided by clicking the button application in input screen ’Layar_Input_Produksi.’ with first symbol S, terminal symbol which contain of ‘a’ until ‘e’ and non terminal which contain of capital letter ‘A’until ‘E’ and ‘S’. Result of this transformation process is shown in two step. First step show result with input which it has been in Chomsky Normal Form and the change of terminal more than one to non terminal. Second step is the final result of context free grammar in Chomsky Normal Form and result of the non terminal changing in first step which more than two non terminal become two non terminal. Transformation result show that for M production, N non terminal, K terminal, with P amount each symbol production, then amount production maximum at the first step is obtained (M+K) production and amount production maximum at the second step (Chomsky Normal Form) is obtained (M+K) + (P-2) production.

vii


KATA PENGANTAR

Segala pujian syukur hormat dan kemuliaan hanya bagi Tuhan Yesus Kristus Raja di bumi dan di surga, yang telah memberkati semua usaha yang telah dilakukan penulis sehingga dapat menyelesaikan tugas akhir ini. Dalam menulis tugas akhir ini bayak hambatan dan kesulitan yang penulis temukan. Namun berkat bantuanNya dan dukungan dari banyak pihak, akhirnya tugas ini dapat terselesaikan. Oleh karena itu, penulis ingin mengucapkan terima kasih kepada : 1. Tuhan Yesus Kristus yang selalu menyertai, memberkati, memberikan hikmat dan atas semua kasih karuniaNya, You’re best of the best of my life. 2. Bapak dan ibu yang terkasih yang setia menemani mencurahkan tenaga, pikiran dan kasih sayangnya untuk anaknya. Engkau anugerah terbaik yang diberikan Tuhan kepadaku. 3. Bapak Ir.Ig Aris Dwiatmoko, M.Sc. selaku dekan Fakultas MIPA. 4. Bapak YG Hartono,S.Si., M.Sc. selaku Kepala Program Studi Matematika. 5. Bapak Drs. J J. Siang, M.Sc. selaku dosen pembimbing. Terima kasih atas segala bimbingan, kritik, saran, dan kesabarannya dalam membimbing penulis selama menyelesaikan tugas akhir ini. 6. Ibu Lusia K B, S.Si., M.Sc. Terima kasih atas saran dan perhatiannya. 7. Ibu Ch. Eny Murwaningtyas, S.Si., M.Si. selaku dosen FMIPA. Terimakasih atas segala dukungan, kritik dan saran yang diberikan.

viii


8. Ibu M.V. Any Herawati, S.Si., M.Si. Terima kasih atas saran dan perhatiannya. 9. Seluruh Dosen FMIPA, Staf Sekretriat dan Laboratorium Universitas Sanata Dharma Yogyakarta. 10. My lovely “Zadrach S,S.T”. Aku tahu kamu membantu dan ada selalu untukku “maafin ya kalo sering aku marahin t4 pelampiasan kalo jengkel marah dll”. Thank’s for all, you’re shine and the best grace of my Lord. 11. My brother Agus G,S.T di Papua ”kerja yang rajin dan kapan nikahnya” Sigit Eka&Familys (Jakarta) and my sister Yesi & Mita, yang rajin donk belajarnya...mumpung masih da kesempatan lho..”be the best 4 all guys”.. 12. My best friend, Thomas.S (Lahat) “Sang Pecinta Wanita” & Bertha terima kasih banget ya untuk segala bantuan arahan dan perhatiannya “kapan nikahnya?punya anak yang banyak ya” dan Anak2 Kos Adi 2. “i pray my BigBoss Lord JC blessing your life in anything”. 13. Boru Anel Sri MK,S.Si dan Boru Tomi (Medan), Stefani Suryati L,S.Si (Flores) dan Om Ulizz (Maluku), Ikke (Cirebon) terima kasih buat segala bantuan dan tumpangannya, Moris Titi Cindy (Kalimantan) yang ada di kos Flamboyan, Ronal (Borneo), smua-a makasih ya bantuannya, jangan lupain aku ya...kalian semua memang teman yang terbaik yang aku punya dan aku kenal “i pray my BigBoss Lord JC blessing your life in anything”. 14. Anak-Anak Matematika ‘01, Maria, Fanya (Sulawesi), Daniel, Ajeng, Very, Indah (Wonogiri), Alam (Kediri), Erika (Kaliurang), April, Deta

ix


(Jakarta), Teddy, Ray, Agnes, Upik, Rita, Andre, Aril, Tabita, Dani cew, Yuli, cuprit jelek. Terima kasih ya... 15. Kakak-Kakak Matematika angkatan atas dan adik-adik kelasku. Thanks.. 16. Anak-Anak KKN, Pedukuhan Gedang Prambanan, Frida, Fajar, Uut (Jogja), Mira, Adri (Purwokerto), Abdi, Ema. Chiayo... man....... 17. Anak-Anak kost Luna, Yusta (Westprog), Ve (Borneo), Ela, Ika, Novi, Ponco, Ayak, Ningrum, Yuni, Ita dua-duanya, Feni, Kadek (Bali), Eva, Riri, Dina, Beni OB ( Magelang )...jadilah yang terbaik..OK !! 18. Buat: Made&Wawan (Bali), Agus (Pati), Ade (Jepara), Parto (Lampung), Wawan (Banyumas), Novi (Blora), Yoga (Klaten), Andri (Temanggung), Theo Yustri&Ariel (Purwodadi), M’Seka dan Lisa (Prambpurwd), thanks.. 19. Buat Yulius JB, Mambo,Nu2ng dan sahabat2 di UPC KA ..Semangat ya..! 20. Teman-teman di Puskesmas Kragan I, dr. Noer, dr. Sigit, bu Warni dan yang ga ku sebutin ..maafin aku ya yang sering bolos..& makasih ijinnya.. 21. Temen- Temenku yang ada di “GFK”, maafin ya,,,aku telat trus laporannya... 22. Temen-Temenku PAFI, sorry aku sering ga kumpul, besuk dech klo ga sibuk, ..he..he. dan Mbak Susi, makasih ya..selalu membantuku.. 23. Dan semua pihak yang telah banyak membantu terselesaikannya skripsi ini tetapi penulis lupa menulisnya.

“LORD JC BLESS U ALL”

x


DAFTAR ISI Halaman HALAMAN JUDUL ....................................................................................... i HALAMAN PERSETUJUAN PEMBIMBING .......................................... ii HALAMAN PENGESAHAN ........................................................................ iii HALAMAN PERSEMBAHAN ...................................................................... iv HALAMAN KEASLIAN KARYA ............................................................... v ABSTRAK ...................................................................................................... vi ABSTRACT ................................................................................................... vii KATA PENGANTAR ..................................................................................... viii DAFTAR ISI ................................................................................................... xi DAFTAR GAMBAR ...................................................................................... xv

BAB I

PENDAHULUAN A. Latar Belakang Masalah ................................................................. 1 B. Rumusan Masalah ........................................................................... 2 C. Batasan Masalah ............................................................................ 2 D. Tujuan Penulisan ..............................................................................3 E. Manfaat Penulisan ............................................................................3 F. Metode Penelitian ........................................................................... .3 G. Sistematika Penulisan ...................................................................... 4

xi


BAB II LANDASAN TEORI A. Tata Bahasa Bebas Konteks ... ..........................................................5 1. Definisi Tata Bahasa Bebas Konteks ..........................................5 B. Penyederhanaaan Tata Bahasa Bebas Konteks ............................... 6 1. Penghilangan Produksi Yang Tidak Bisa Diturunkan Hingga Terminal ..........................................................................7 2. Penghilangan Produksi Yang Tidak Bisa Dicapai Dari S ............... 9 C. Bentuk Normal Chomsky .................................................................11 1. Definisi Bentuk Normal Chomsky ............................................ 11 2. Pembentukan Bentuk Normal Chomsky ................................... 12 D. Pemprograman Java ............................................................................ 16 1. Java ........................................................................................... 16 2. JDK (Java Development Kit) ................................................... 17 3. NETBEANS ..…............................................................................ 18 4. Pemprograman Berorientasi Objek .......................................... 18 5. Objek, Data, Method ................................................................. 18

BAB III PERANCANGAN DAN IMPELMENTASI A. Perancangan Sistem............................................................................ 19 B. Perancangan Antarmuka..................................................................... 22 1. Layar_Sampul............................................................................. 22 2. Layar_Utama............................................................................... 23 3. Layar_Tambah_Produksi.............................................................24

xii


4. Layar_Input_Produksi .................................................................25 C. Perancangan Proses ............................................................................26 1. Flowchart Transformasi Tata Bahasa Bebas Konteks ke Bentuk normal Chomsky .................................................................. 26 2. Pengecekan Input Produksi Tunggal (Tahap 1) .........................28 3. Flowchart Pengecekan Input Produksi Yang Tidak Bisa Diturunkan Sampai ke Terminal (Tahap 2) .................................28 4. Flowchart Pengecekan Input Produksi Yang Tidak Bisa Dicapai dari Simbol Awal (Tahap 3) .........................................30 5. Flowchart Perubahan Terminal Lebih dari 1 Menjadi Non Terminal (Tahap 5) ............................................................ 32 6. Flowchart Perubahan Non Terminal Lebih dari 2 Menjadi Tepat 2 Non Terminal (Tahap 6) ...................................................... 34 D. Perancangan Struktur Data .............................................................. 35 1. Kelas Huruf ................................................................................ 35 2. Kelas Chomsky .......................................................................... 35 3. Frame Form Java ........................................................................ 37 E. Implementasi ..................................................................................... 37 1. Pengecekan Bentuk Produksi tunggal ..........................................37 2. Pengecekan Produksi Yang Tidak Bisa Diturunkan Hingga Terminal ..................................................................................... 41 3. Pengecekan Produksi Yang Tidak Bisa Dicapai dari Simbol Awal .............................................................................................44

xiii


4. Pengecekan Bentuk Normal Chomsky ...................................... 46 5. Pengubahan Simbol Terminal Menjadi Non Terminal ................47 6. Pengubahan Simbol Non Terminal Lebih dari 2 Menjadi Tepat 2 Non Terminal ................................................................ 48

BAB IV HASIL DAN PEMBAHASAN A. Hasil Impelmentasi ........................................................................... 50 1.

Form Layar_Sampul ...................................................................51

2.

Form Layar_Utama ....................................................................... 52

3.

Form Layar_Tambah_Produksi ..................................................53

4.

Form Layar_Input_Produksi ......................................................55

B. Penggunaaan Program ....................................................................... 56 1.

Masukkan (Input) Program .........................................................56

2.

Proses Program ............................................................................57

C. Pengujian Program ..............................................................................58 D. Pembahasan / Analisis Program ..........................................................65

BAB V

PENUTUP

A.

Kesimpulan ........................................................................................ 68

B.

Saran ................................................................................................... 69

DAFTAR PUSTAKA....................................................................................... 70

xiv


DAFTAR GAMBAR Halaman Gambar 3.1

Diagram alir tahapan transformasi tata bahasa bebas konteks ke bentuk normal Chomsky ....................................................... 21

Gambar 3.2

Perancangan Layar_Sampul........................................................ 22

Gambar 3.3

Perancangan Layar_Utama.......................................................... 23

Gambar 3.4

Perancangan Layar_Tambah_Produksi........................................24

Gambar 3.5

Perancangan Layar_Input_Produksi............................................25

Gambar 3.6

Diagram alir perancangan program transformasi tata bahasa bebas konteks ke bentuk Normal Chomsky ................................... 27

Gambar 3.7

Diagram alir pengecekan produksi yang tidak bisa diturunkan hingga ke terminal (Tahap 2) ....................................... 29

Gambar 3.8

Diagram alir pengecekan produksi yang tidak bisa dicapai dari simbol awal (Tahap 3) ........................................................ 31

Gambar 3.9

Diagram alir perubahan terminal lebih dari 1 menjadi non terminal (Tahap 5) .............................................................. 33

Gambar 3.10 Diagram alir perubahan non terminal lebih dari 2 menjadi tepat 2 non terminal (Tahap 6) ...................................................34 Gambar 4.1

Form Layar_Sampul ...................................................................51

Gambar 4.2

Form Layar_Utama .....................................................................52

Gambar 4.3

Form Layar_Tanbah_Produksi ....................................................54

Gambar 4.4

Form Layar_Input_Produksi .......................................................55

Gambar 4.5

Form hasil pengujian program contoh 1 ....................................58

xv


Gambar 4.6

Form Layar_Tambah_Produksi contoh 2 ..................................61

Gambar 4.7

61 Form hasil pengecekan program contoh 2 .......................................

Gambar 4.8

Form hasil transformasi contoh 2 .............................................. 62

Gambar 4.9

Form Layar_Tambah_Produksi contoh 3 ...................................63

64 Gambar 4.10 Form hasil pengecekan program contoh 3 ....................................... Gambar 4.12 Form hasil transformasi contoh 3 ...............................................64

xvi

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI 1

BAB I PENDAHULUAN

A. Latar Belakang Masalah Teori bahasa dan otomata merupakan disiplin ilmu yang mempunyai peranan penting dalam dunia pemprograman komputer. Dalam ilmu teori bahasa dan otomata membahas bagaimana suatu proses pekerjaan yang terdiri dari berbagai tahap (perpindahan dari suatu tahap ke tahap berikutnya ditentukan oleh masukan yang diberikan) dapat dideskripsikan ke dalam notasi sehingga memudahkan pengolahan ke tahap selanjutnya. Tata bahasa (grammar) dapat didefinisikan secara formal sebagai kumpulan dari himpunan-himpunan variabel, simbol-simbol terminal, simbol awal yang dibatasi oleh aturan-aturan produksi. Sistem dalam ilmu teori bahasa dan otomata yang dipakai untuk mendefinisikan bahasa adalah tata bahasa bebas konteks / context free grammar (cfg). Penggunaan tata bahasa bebas konteks untuk mendefinisikan bahasa akan memudahkan pekerjaan dalam memeriksa rangkaian kata berdasarkan tata bahasa atau parsing. Sebagai sebuah langkah final dari penyederhanaan tata bahasa bebas konteks, disajikan sebuah bentuk baku atau bentuk normal untuk produksiproduksi. Salah satu bentuk normal yang sangat berguna untuk tata bahasa bebas konteks adalah Bentuk Normal Chomsky / Chomsky Normal Form (CNF). Dengan bentuk normal Chomsky akan didapatkan keterhubungan pasti diantara


panjang dari sebuah untai dan banyaknya langkah penurunannya sebanyak dua kali untai yang dapat diturunkan.

B. Rumusan Masalah Permasalahan-permasalahan yang akan dibahas berdasarkan latar belakang di atas dapat dirumuskan dalam pertanyaan berikut ini : 1. Bagaimana cara menyederhanakan tata bahasa bebas konteks? 2. Bagaimana pembentukan bentuk normal Chomsky? 3. Bagaimana mengimplementasikan pembentukan bentuk normal Chomsky dalam suatu program?

C. Batasan Masalah Dalam tugas akhir ini permasalahan yang akan dibahas dibatasi pada : 1. Dalam aplikasinya untuk dapat diubah dalam bentuk normal Chomsky, input berupa tata bahasa bebas konteks yang tidak mengandung ε dan produksi tunggal. 2. Jumlah maksimum produksi input adalah 10. 3. Jumlah maksimum simbol hasil produksi (sebelah kanan tanda panah) adalah 20 simbol. 4. Program hanya bisa menguji apakah produksi tata bahasa bebas konteks yang diinputkan merupakan produksi yang sederhana, tetapi tidak mampu menyederhanakan input produksi tata bahasa bebas konteks yang tidak sederhana.


5. Program dibuat mengunakan bahasa Java dengan Java Development Kit 1.5.0 yang diedit dengan NetBeans 3.6

D. Tujuan Penulisan Tujuan yang hendak dicapai dari penulisan ini adalah membuat suatu program cara mentransformasi tata bahasa bebas konteks ke bentuk normal Chomsky.

E. Manfaat Penulisan Hasil program yang dibuat ini diharapkan memberikan manfaat, antara lain : 1. Mempermudah pengguna (user) untuk mentransformasikan tata bahasa bebas konteks ke bentuk normal Chomsky. 2. Pengguna (user) mengetahui tahap demi tahap perpindahan tata bahasa konteks menjadi bentuk normal Chomsky.

F. Metode Penulisan Metode yang digunakan dalam penulisan skripsi ini adalah : 1. Studi pustaka tentang cara mentransformasi tata bahasa bebas konteks ke bentuk normal Chomsky. 2. Implementasi transformasi tata bahasa bebas konteks ke bentuk normal Chomsky dalam suatu program


3. Jalankan program untuk mentransformasi bahasa bebas konteks ke bentuk normal Chomsky. 4. Analisis dan perhatikan hasil akhirnya.

G. Sistematika Penulisan Bab I Pendahuluan Menjelaskan uraian-uraian yang mendasari pembahasan skripsi, yaitu latar belakang masalah, masalah yang akan dibahas, batasan masalah, tujuan penulisan, manfaat penulisan, metodelogi penulisan, serta sistematika penulisan. Bab II Landasan Teori Dalam bab ini menjelaskan beberapa teori yang mendasari pembentukan

bentuk

normal

Chomsky

yang

selanjutnya

diimplementasikan ke dalam program. Bab III Perancangan dan Implementasi Menjelaskan perencanaan rancangan program dan penerapan rancangan program yang telah dibuat. Bab IV Hasil dan pembahasan Menjelaskan hasil dari rancangan program dan melakukan percobaan serta analisa hasil perancangan. Bab V Penutup Kesimpulan dan saran dari hasil pembahasan masalah dan analisa secara keseluruhan.


BAB II LANDASAN TEORI

A. Tata Bahasa Bebas Konteks Tata Bahasa Bebas Konteks / Contexs Free Grammar ( CFG) merupakan salah satu cara untuk mendefinisikan bahasa (language). Dengan tata bahasa bebas konteks dapat diketahui untai-untai yang dihasilkan dalam bahasa. A.1 Definisi Tata Bahasa Bebas Konteks Tata bahasa bebas konteks didefinisikan sebagai G = ( Ν , Σ, S , Ρ ), dengan : Ν

= himpunan simbol nonterminal.

Σ

= himpunan terminal-terminal atau alphabeth.

S ∈ Ν = simbol awal. Ρ

= aturan produksi, dimana P ⊆ Ν × ( Ν ∪ Σ) * atau dapat dijelaskan sebagai N → ( Ν ∪ Σ ) *.

Nonterminal Ν yang ada disebelah kiri produksi dapat digantikan oleh string w yang ada di sebelah kanan tanda panah, dimana w ∈ ( Ν ∪ Σ) *. Tata bahasa bebas konteks G dalam mendefinisikan sebuah bahasa L atau dinotasikan L(G ) dengan cara menetapkan sebuah himpunan produksi, dimana hanya string-string dari L yang dapat disusun oleh himpunan produksi tersebut. Setiap string yang dapat dibentuk dari keadaan awal S melalui proses penggantian semua nonterminal oleh aturan-aturan produksi sampai tidak ada lagi nonterminal yang tersisa merupakan bagian L .


Contoh : N = (S, A, B, C) Σ = (a, b, c) Ρ=

S → Abb | BC | abbC A→a B → ab C→c

String yang dapat dibentuk dari CFG di atas adalah L = (abb, abc, abbc) Penurunan string berdasarkan CFG di atas : S → Abb → abb (1)

(2 )

S → BC → abc (1)

(2 )

S → abbC → abbc (1)

(2 )

B. Penyederhanaan Tata Bahasa Bebas Konteks Pembentukan tata bahasa bebas konteks terkadang belum dalam bentuk yang sederhana, sehingga ketidaksederhanaan ini akan membuat tata bahasa bebas konteks menjadi rumit dengan aturan-aturan produksi yang tidak berarti. Oleh karena itu perlu dilakukan penyederhanaan tata bahasa bebas konteks dengan menempatkan

pembatasan-penbatasan,

sehingga

pohon

penurunan

yang

dihasilkan tidak rumit dan mudah ditelusuri. Langkah-langkah penyederhanaan tata bahasa bebas konteks : 1. Penghilangan produksi yang tidak bisa diturunkan hingga simbol terminal.


2. Penghilangan produksi yang tidak bisa dicapai dari S . 3. Menghilangkan produksi - ε 4. Menghilangkan produksi tunggal Dalam skripsi ini, karena input yang berupa tata bahasa bebas konteks dianggap sudah sederhana jadi tidak dilakukan penyedehanaan melainkan hanya melakukan pengecekan. Pengecekan tersebut adalah penghilangan produksi yang tidak bisa diturunkan sampai mencapai simbol terminal dan produksi yang tidak bias dicapai dari S . Sedangkan pengecekan untuk penyedehanaan menghilangkan produksi tunggal dan produksi ε dilakukan secara manual yaitu langsung saat user menginput diharapkan

tidak memasukkan tata bahasa konteks yang

mengandung produksi tunggal maupun produksi ε .

B.1 Penghilangan Produksi Yang Tidak Bisa Diturunkan Hingga Terminal Produksi yang tidak bisa diturunkan atau yang tidak bisa mencapai terminal dikatakan tidak sederhana, karena bila diturunkan tidak akan pernah selesai atau tidak akan pernah menghasilkan terminal-terminal seluruhnya. Contoh : N = ( S, A, B , C, D ) Σ = ( a, b, c, d, e ) Ρ=

S → Aab | bbC | aaD A → Abe | aaB | e B → Ac | bcC C → cd


Terlihat bahwa nonterminal D tidak mempunyai produksi atau tidak dapat menurunkan simbol terminal. Oleh karena itu nonterminal D dan setiap produksi yang mengandung nonterminal D dikatakan tidak berguna. Jika diketahui CFG

G = ( Ν , Σ, S , Ρ ) maka hasil penyederhanaanya

adalah G′ = ( Ν ′, Σ ′, S ′, Ρ ′ ), dimana Ν′ dan Ρ ′ dibentuk dengan langkah-langkah sebagai berikut. Algoritma : 1. Inisialisasi Ν′ dengan semua nonterminal A → w merupakan sebuah produksi dalam G dengan w ∈ Σ *. 2. Inilisiasasi Ρ ′ dengan semua produksi A → w dimana A ∈ Ν′ dan

w ∈ Σ *. 3. -

Tambahkan ke dalam Ν′ semua nonterminal A dimana A → w ,

w ∈ ( Ν ′ ∪ Σ) * adalah sebuah produksi dalam Ρ . -

Tambahkan produksi tersebut ke Ρ ′ .

-

Ulangi langkah-langkah ini sampai tidak ada lagi nonterminal yang yang ditambah ke dalam Ν′ .

Contoh penyederhanaan dengan menghilangkan nonterminal yang tidak bisa mencapai terminal : Ρ=



Ν′

Ρ′

Inisialisasi

{A, C}

A→e

Nonterminal yang bisa

{A, C, B}

S → Aab ; A → Abe B → Ac

diturunkan ke {A, C}

;

C → cd

; S → bbC

B → bcC Nonterminal yang bisa

{A, C, B}

A → aaB

diturunkan ke {A, C, B}

Ρ′ :

S → Aab | bbC A → Abe | aaB | e B → Ac | bcC C → cd

B.2 Penghilangan Produksi Yang Tidak Bisa Dicapai Dari S N = ( S, A, B , C, D ) Σ = ( a, b, c, d, e ) Ρ=

S → aabAac | BB | BBB | Ddee A → aaa | cdA B → BDc | c C → cde D→e

Nonterminal C di atas dikatakan redundan (berlebih) karena non terminal tersebut tidak akan pernah dicapai dari S atau dari produksi manapun.


Misalkan G′ = ( Ν ′, Σ ′, S ′, Ρ ′ ) merupakan hasil penyederhanaan dari G = ( Ν , Σ, S , Ρ ) yang dibentuk dengan langkah-langkah sebagai berikut. Algoritma : 1. - Inisialisasi Ν′ dengan memuat simbol awal S . - Inisialisasi Ρ ′ dan Σ ′ sebagai himpunanan kosong. 2. Untuk setiap A ∈ Ν′ , jika A → w merupakan produksi dalam Ρ , maka : - Masukkan A → w ke dalam Ρ ′ . - Masukkan semua non terminal yang ada di dalam w ke dalam Ν′ . - Masukkan semua terminal yang ada di dalam w ke dalam Σ ′ . Ulangi langkah ini sampai tidak ada lagi produksi yang dapat ditambahkan ke dalam Ρ ′ . Berikut adalah contoh penyederhanaan dengan menghilangkan nonterminal yang tidak bisa mencapai terminal : Ρ=

S → aabAac | BB | BBB | Ddee A → aaa | cdA B → BDc | c C → cde D→e

Ν′ Inisialisasi

{S}

Produksi dari S

{S, A, B, D}

Ρ′

φ S → aabAac | BB | Dde

Σ′

φ {a, b, c, d, e}


Produksi dari

{S, A, B, D}

A → aaa | cdA

{A, B, D}

{a, c, e}

B → BDc | c D→e

Ρ′ :

S → aabAac | BB | Ddee A → aaa | cdA B → BDc | c D→e

C. Bentuk Normal Chomsky Bentuk Normal Chomsky / Chomsky Normal Form (CNF) merupakan salah satu bentuk akhir dari penyederhanaan tata bahasa bebas konteks dimana bentuk untai-untainya lebih terstruktur.

C.1 Definisi Bentuk Normal Chomsky A tata bahasa bebas konteks G = ( Ν , Σ, S , Ρ ) dikatakan dalam bentuk

normal Chomsky, jika dan hanya jika setiap aturan dalam Ρ berbentuk sebagai berikut : 1. A → a , untuk setiap A ∈ Ν dan a ∈ Σ 2. A → BC , untuk setiap A , B ,C ∈ Ν Dengan kata lain tata bahasa bebas konteks berbentuk normal Chomsky jika setiap produksinya terdiri dari tepat sebuah terminal tunggal maupun dua non terminal.


C.2 Pembentukan Bentuk Normal Chomsky Dengan adanya sebuah tata bahasa bebas konteks dalam bentuk normal Chomsky, maka dapat diketahui dengan tepat bagaimana langkah-langkah dalam melakukan penurunan sebuah string . Jika G sebuah tata bahasa bebas konteks dan ε ∉ L (G ) , maka G dapat ditransformasikan menjadi sebuah tata bahasa bebas konteks dalam bentuk normal Chomsky. Cara mentransformasikan grammar ke dalam bentuk normal Chomsky : 1. Hilangkan semua produksi yang tidak diperlukan, produksi ε , dan produksi tunggal dalam G . Setelah dilakukan penyederhanaan tata bahasa konteks, maka akan meghasilkan semua produksi berbentuk A → w dengan w ≥ 1 -

Jika w = 1 berarti w ∈ Σ , karena tidak ada produksi tunggal. Jadi sudah memenuhi bentuk normal Chomsky.

-

Jika w > 1 berarti w = X 1 X 2 .... X n , maka w bisa memuat terminal dan non terminal keduanya. Cara mengkonversikan w menjadi untai-untai yang hanya memuat nonterminal-nonterminal : Misalkan diketahui sebuah produksi yang berbentuk A → w , untuk w = X 1 X 2 .... X n . Jika ada X i ∈ Σ , kita ganti X i dengan Ci ∈ Ν dan tambahkan Ci → X i


Hasil step (1) : semua produksi berbentuk A → w dengan w sebuah terminal atau string yang semuanya terdiri dari non terminal. 2. Transformasikan G ke dalam CNF dengan memecah string pada ruas kanan produksi yang panjangnya lebih dari dua non terminal. Jika sebuah produksi A → B1 B2 .....Bn ,

Bi ∈ Ν ( dengan n ≥ 2 ) maka

diubah dengan mengambil 2 non terminal pertama dan menggantikannya dengan 2 non terminal baru sampai mencapai tepat 2 non terminal. A → Z n − 3 Bn Z 0 → B1 B2 M Z n −3 → Z n − 4 Bn −1 Z i merupakan non terminal-non terminal baru. Dalam tata bahasa yang dihasilkan setelah mengalami transformasi, ruas kanan dari masing-masing produksi terdiri dari baik sebuah terminal tunggal maupun yang lainnya berupa sebuah untai dari dua non terminal. Akibatnya, suatu tata bahasa bebas konteks yang tidak memuat ε dapat diturunkan oleh sebuah tata bahasa bebas konteks dalam bentuk normal Chomsky. Berikut ini merupakan contoh tata bahasa konteks yang sudah mengalami penyederhanaan dan akan ditransformasikan ke dalam bentuk normal Chomsky: N = ( S, A, B , C ) Σ = ( a, b, c, d, e ) Ρ=

S → Bb | AA | de A → aBb B → bC | bbbb


C→c Aturan-aturan produksi yang sudah dalam bentuk normal Chomsky : S → AA C→c Transformasi pertama (‘ ⇒ ’ bisa dibaca ‘berubah menjadi’) : o Ubah produksi A → w dengan w ≥ 1 o Ganti semua terminal dalam w menjadi nonterminal baru. S → Bb

⇒

S → B Ζ0

S → de

⇒

S → Ζ1 Ζ 2

A → aBb

⇒

A → Ζ3 B Ζ0

B → bC

⇒

B → Ζ0 C

B → bbbb

⇒

B → Ζ0 Ζ0 Ζ0 Ζ0

Terbentuk aturan produksi dan simbol variable baru : Ζ0 → b

Ζ1 → d Ζ2 → e Ζ3 → a Produksi menjadi : S → B Ζ 0 | AA | Ζ1 Ζ 2 A → Ζ3 B Ζ0 B → Ζ0 C | Ζ0 Ζ0 Ζ0 Ζ0


C→c Ζ0 → b

Ζ1 → d Ζ2 → e Ζ3 → a Transformasi kedua : o Ubah produksi A → w dengan w ≥ 2 A → Ζ3 B Ζ0

⇒

A → Ζ4 Ζ0

B → Ζ0 Ζ0 Ζ0 Ζ0

⇒

B → Ζ5 Ζ0 Ζ0

B → Ζ5 Ζ0 Ζ0

⇒

B → Ζ6 Ζ0

Terbentuk aturan produksi dan symbol variable baru :

Ζ4 → Ζ3 B Ζ5 → Ζ0 Ζ0 Ζ6 → Ζ5 Ζ0 Produksi dalam CNF : S → B Ζ 0 | AA | Ζ1 Ζ 2 A → Ζ4 Ζ0 B → Ζ0 C | Ζ6 Ζ0 C→c Ζ0 → b

Ζ1 → d


Ζ2 → e Ζ3 → a

Ζ4 → Ζ3 B Ζ5 → Ζ0 Ζ0 Ζ6 → Ζ5 Ζ0 Jika L sebuah tata bahasa bebas konteks yang memuat ε , maka bisa didapatkan sebuah tata bahasa bebas konteks dalam bentuk normal Chomsky untuk L − {ε } dan kemudian menambahkan produksi S → ε kepadanya. Tata bahasa yang dihasilkan adalah dalam bentuk normal Chomsky kecuali untuk produksi ε tunggal.

D. Pemrograman Java D.1 Java Java merupakan bahasa pemprograman berorientasi objek yang diciptakan oleh James Gosling dan beberapa team lainnya di Sun Microsystem. Karasteristik Java berukuran lebih kecil, efisien dan portable untuk berbagai hardware. Java terpilih sebagai bahasa pemprograman untuk aplikasi jaringan. Keunggulan java : 1. Java bersifat sederhana dan lebih mudah. 2. Java bersifat lebih sederhana dibandingkan bahasa populer lain seperti C++. Sebagian dari Java dimodelkan dari C++, dengan memperbaiki beberapa karasteristik C++.


Sebagai contoh, Java menggantikan konsep pewarisan jamak (multiple inhiritance) yang relatif kompleks dengan struktur yang sederhana yaitu interface, tidak menggunakan pointer, alokasi memori secara otomatis, dan sebagainya. 3. Java berorientasi pada objek (Oriented Objek). Java merupakan bahasa pemprograman yang berorientasi objek (OOP). Java membagi program menjadi beberapa objek, kemudian memodelkan sifat dan tingkah lakunya masing-masing. Selanjutnya, Java menentukan dan mengatur interksi antara objek yang satu dengan yang lain. 4. Java bersifat terdistribusi. Java dirancang untuk membuat pemrograman lebih terdistribusi yang memanfaatkan jaringan komputer lebih mudah untuk diwujudkan. 5. Java bersifat Multiplatform Java bersifat mutiplatform, yakni dapat diterjemahkan oleh Java Interpreter pada berbagai sistem operasi, sehingga tidak bergantung pada arsitektur perangkat keras yang digunakan. 6. Java bersifat MultiThread Java mempunyai kemampuan untuk menjalankan beberapa bagian program dalam waktu bersamaan. D.2 JDK (Java Development Kit) JDK merupakan perangkat pemprograman Java yang berisi kompiler dan interpreter yang direlase oleh Sun. Dalam skripsi ini, program menggunakan JDK 1.5.


D. 3 NETBEANS Ada beberapa macam editor yang digunakan untuk mengedit listing program Java. Diantaranya fasilitas editor pada lingkungan DOS, Notepad / Wordpad pada Windows, Ultra edit, dan NetBeans. yang digunakan dalam skripsi ini. NetBeans dari Java dapat dipakai untuk : 1. Menulis program 2. Mengkompilasi program 3. Melakukan pencarian kesalahan (debugging) 4. Menjalankan program, dll. D.4 Pemprograman Berorientasi Objek Pemprograman Berorientasi Objek atau Object Oriented Programing (OOP) merupakan konsep pemprograman yang difokuskan pada penciptaan kelas yang merupakan abstraksi/blueprint/prototype dari suatu objek. Kelas harus mengandung sifat (data) dan tingkah laku (method) umum yang dimiliki objekobjek yang nantinya akan dibuat (diintansiasi). Data dan method merupakan anggota (member) dari suatu kelas. D.5 Objek, Data dan Method Kelas adalah prototype yang mendefinisikan data-data dan method-method secara umum. Objek merupakan instans (perwujudan) dari kelas. Sedangkan sifat karasteristik yang dimiliki objek disebut data dan prosedur/fungsi yang dimiliki objek disebut method.


BAB III PERANCANGAN DAN IMPLEMENTASI

A. Perancangan Sistem Pada program transformasi kebentuk normal Chomsky masukan harus berupa himpunan produksi dari tata bahasa bebas konteks yang sudah mengalami penyederhanaan yang kemudian akan ditransformasikan ke bentuk normal Chomsky. Sehingga diharapkan user tidak memasukkan tata bahasa bebas konteks yang tidak sederhana. Langkah dari sistem yang dibuat adalah sebagai berikut : 1. User menginputkan tata bahasa bebas konteks menggunakan daftar tombol yang disediakan program. 2. Program melakukan pengecekan bentuk produksi tunggal. Pada saat user hanya menginputkan hasil produksi sebanyak satu non terminal, maka input tersebut tidak dapat diakhiri kecuali batal sampai user menginputkan lagi simbol terminal ataupun non terminal. 3. Program melakukan pengecekan, apakah aturan produksi dalam tata bahasa bebas konteks ada yang tidak bisa diturunkan sampai terminal dan tidak bisa dicapai dari simbol awal. Jika terdapat salah satu syarat ketidaksederhanaan tersebut, maka ditampilkan pesan apakah user akan tetap melanjutkan proses transformasi. Jika ya maka tata bahasa bebas

konteks

akan

ditransformasikan

dengan

mengabaikan

penyederhanaan tata bahasa bebas konteks. Tetapi jika user memilih


tidak maka user harus menginputkan lagi tata bahasa bebas konteks yang benar sesuai dengan pesan yang ditampilkan. 4. Program melakukan pengecekan, apakah aturan produksi sudah memenuhi syarat bentuk normal Chomsky. Jika aturan produksi sudah memenuhi

syarat

bentuk

normal

Chomsky,

program

akan

menampilkan aturan produksi tersebut ke output. 5. Jika aturan produksi belum memenuhi syarat bentuk normal Chomsky dan dalam aturan produksi tersebut terdapat terminal yang jumlahnya lebih dari satu, maka terminal tersebut akan diubah menjadi non terminal baru. 6. Selanjutnya aturan produksi yang mengandung non terminal yang jumlahnya lebih dari dua akan ditansformasikan ke bentuk normal Chomsky sampai mencapai tepat dua non terminal dan hasil tersebut ditampilkan dalam output. 7. Hasil akhir dari program adalah tata bahasa bebas konteks yang sudah mengalami penyederhanaan G′ = ( Ν ′, Σ ′, S ′, Ρ ′ ) dengan aturan dalam Ρ ' berbentuk sebagai berikut :

1. A → a , untuk setiap A ∈ Ν' dan a ∈ Σ' 2. A → BC , untuk setiap A , B ,C ∈ Ν' Secara skematis alur yang digunakan dalam proses transformasi ke bentuk normal Chomsky ini dinyatakan pada gambar 3.1 :


M ulai

P engecekan : Terdapat P roduksi T unggal ?

ya

T ata B ahasa B ebas K onteks disederhanakan ?

ya

tid a k

ya

P engecekan : P roduksi tidak bisa diturunkan hingga term inal ?

tid a k

tid a k

ya

P engecekan : P roduksi tidak bisa dicapai dari sim bol awal ?

tid a k

P engecekan : P roduksi dalam B entuk N orm al C hom sky ?

ya

tid a k U bah P roduksi untuk term inal > 1 m enjadi non term inal baru

U bah produksi untuk non term inal > 2 sam pai m encapai tepat 2 non term inal

S elesai

Gambar 3.1 Diagram alir tahapan transformasi tata bahasa bebas konteks ke bentuk normal Chomsky.


B. Perancangan Antarmuka Perancangan

antarmuka

dibuat

untuk

memudahkan

user

dalam

mengoperasikan perangkat lunak. Dalam perancangan antarmuka yang akan dibuat terdiri dari 4 layar, yaitu layar Layar_Sampul, layar Layar_Utama, Layar Layar_Tambah_Produksi dan layar Layar_Input_Produksi. B.1 Layar_Sampul

PROGRAM BANTU TRANSFORMASI TATA BAHASA BEBAS KONTEKS KE BENTUK NORMAL CHOMSKY

Disusun oleh : Wiwit Kristiani - 013114007

Keluar

Lanjut >>

Gambar 3.2 Perancangan Layar_Sampul Terdiri dari 2 label dan 2 tombol : 1. Label ‘Judul Skripsi’ 2. Label ‘Penyusun Skripsi’ 3. Tombol ‘Keluar’ 4. Tombol ‘Lanjut’, untuk masuk ke Layar_Utama


B.2 Layar_Utama

Proses Transformasi Tata Bahasa Bebas Konteks ke Bentuk Normal Chomsky

HASIL INPUT

CHOMSKY BARU CHOMSKY BARU

HASIL OUTPUT 1

HASIL OUTPUT 2

PROSES CHOMSKY PROSES CHOMSKY KELUAR KELUAR

Gambar 3.3. Perancangan Layar_Utama

Terdiri dari 1 label, 3 daftar dan 3 tombol : 1. Label text judul 2. Daftar Hasil Input 3. Daftar Hasil Output Langkah 1 4. Daftar Hasil Output Langkah 2 5. Tombol ‘Chomsky Baru’, untuk masuk ke ‘Layar_Tambah_Produksi’ 6. Tombol ‘Proses Chomsky’, untuk mendapatkan output 7. Tombol ‘Keluar’, untuk kembali ke ‘Layar_Sampul’


B.3. Layar_Tambah_Produksi

Tambah Produksi Edit Produksi Hapus Produksi OK

BATAL

Gambar 3.4. Perancangan Layar_Tambah_Produksi

Terdiri dari 1 daftar dan 5 tombol : 1. Daftar Masukan Produksi 2. Tombol ‘Tambah Produksi’ 3. Tombol ‘Edit Produksi’ 4. Tombol ‘Hapus Produksi’ 5. Tombol ‘OK’ 6. Tombol ‘BATAL’


B.4. Layar_Input_Produksi

Produksi S →

A

B

C

D

E

a

b

c

d

e

OK

HAPUS KARAKTER

S

|

BATAL

Gambar 3.5. Perancangan Layar_Input_Produksi

Terdiri dari 3 label dan 15 tombol : 1. Label ‘S’ 2. Label tanda panah ‘ → ’ 3. Label untuk tempat hasil produksi (sebelah kanan tanda panah) 4. Tombol non terminal ‘A, B, C, D, E, S’ 5. Tombol terminal ‘a, b, c, d, e’ 6. Tombol tanda garis ‘|’ 7. Tombol ‘OK’ 8. Tombol ‘HAPUS KARAKTER’ 9. Tombol ‘BATAL’


C. Perancangan Proses Perancangan proses merupakan suatu gambaran proses program yang akan dibuat sehingga pengimplementasian ke dalam suatu program menjadi lebih jelas dan mudah. Proses yang dilakukan adalah pengolahan masukkan yang dimasukkan oleh user, yang kemudian akan menampilkan informasi hasil masukan dan hasil keluaran. Dalam perancangan proses transformasi kebentuk normal Chomsky ini meliputi perancangan seluruh bagian program yang digambarkan dalam suatu flowchart. Flowchart secara keseluruhan, flowchart untuk pengecekan tata bahasa bebas konteks dan flowchart untuk mentransformasikan tata bahasa bebas konteks ke dalam bentuk normal Chomsky yang terbagi menjadi dua yaitu flowchart untuk melakukan perubahan dari terminal lebih dari satu menjadi non terminal dan flowchart untuk melakukan perubahan dari non terminal lebih dari dua sampai menjadi tepat dua non terminal.. Flowchart untuk pengecekan tata bahasa bebas konteks terdiri flowchart pengecekan bentuk produksi yang tidak bisa diturunkan sampai ke terminal dan flowchart pengecekan bentuk produksi yang tidak bisa dicapai dari simbol awal. C.1 Flowchart Transformasi Tata Bahasa Bebas Konteks ke Bentuk Normal Chomsky Dalam flowchart transformasi ke bentuk normal Chomsky yang terbagi dalam pengecekan tata bahasa bebas konteks dan proses transformasi ke bentuk normal Chomsky ini terdiri dari 6 tahap bagian.


M u la i

Inpu t: Tata bah as a be bas k o n t e k s G = (Ν , Σ , S , Ρ

)

Tahap 1

Ρ : A → B ?

ya

A, B ∈ Ν ya t id a k

Tata B ah as a B ebas K ontek s d is e d e r h a n a k a n ?

Tahap 2

Ρ : A → w,

ya

w ∉

(Ν

′∪ Σ

)*

t id a k t id a k Tahap 3 Ρ : A →

ya

w ,

A ∉ Ν ′, w ∉

(Ν ∪ Σ ′ )*

t id a k

Tahap 4

Ρ : A → a, A ∈ Ν , a ∈ Σ A → B C , A , B ,C ∈ Ν

ya

t id a k

U bah

Ρ : A → w, u n t u k w > 1 , w ∈ Σ

Tahap 5

U bah

Ρ : A → w, u n t u kw > 2 , w ∈ Ν

Tahap 6

O u tp u t : c h o m s ky

A

A

→

→

b e n tu k n o r m a l G ′ = ( Ν ′ , Σ ′ , S ′, Ρ ′ ) ,

a , A

BC

∈

Ν ′, a

, A , B ,C

∈

∈

Σ ′

Ν ′

S e le s a i

Gambar 3.6 Diagram alir perancangan program transformasi ke bentuk normal Chomsky


C.2 Pengecekan Input Produksi Tunggal (Tahap 1) Pengecekan input yang mengandung produksi tunggal dilakukan saat user menginput produksi. Setelah user menginputkan hasil produksi yang berupa 1 simbol non terminal maka secara otomatis program akan hanya akan mengaktifkan simbol terminal dan non terminal sehingga diharapkan user tidak hanya menginputkan satu non terminal. Pengecekan ini dilakukan secara terus menerus selama user menginputkan tata bahasa bebas konteks. C.3 Flowchart Pengecekan Input Produksi Yang Tidak Bisa Diturunkan Sampai ke Terminal (Tahap 2) Pengecekan apakah input mengandung produksi yang tidak bisa diturunkan sampai mencapai terminal dilakukan setelah user memasukkan semua tata bahasa konteks yang akan ditransformasikan. Pengecekan dilakukan dengan cara : a) Mencari non terminal yang hasil produksinya mengandung semua non terminal. b) Mencari produksi-produksi yang bisa menurunkan non terminal-non terminal tersebut sehingga didapat non terminal-non terminal yang memproduksinya. c) Langkah b dilakukan berulang-ulang sampai tidak ada lagi non terminal yang ditambahkan d) Hasil non terminal-non terminal dan produksi-produksi dari langkah 1 sampai c yang ditemukan dibandingkan dengan non terminal dan produksi dari input


e) Jika ditemukan non terminal yang terdapat di hasil produksi tetapi tidak terdapt di non terminal yang dicari sebelumnya dari langkah a sampai c, maka non terminal tersebut tidak bisa diturunnkan. Untuk input yang demikian user harus memasukkan input yang benar.

Mulai

Input : tata bahas a bebas k ontek s G = Ν , Σ ,

(

S, Ρ )

Ρ: A → B?

ya

A, B ∈ Ν

tidak

C ari

Adim ana A → w , A ∈ N , w ∈ Σ *

C ari

A dim ana A → w, A ∈ Ν , w ∈ (Ν′ ∪ Σ )*

ya

Tata Bahas a Bebas Kontek s dis ederhanak an ?

ya

dim ana

Apak ah ada A → w,

A, A∈ Ν′

w ∈ (Ν ∪ Σ )*(s ebelah k anan ‘→ ’)

∉ w ∈ (Ν ′ ∪ Σ ) *

tidak

Tahap 4 : C ek bentuk norm al C hom s k y

tidak

Tahap 3 : C ek produk s i y ang tidak bis a dic apai dari s im bol awal atau dari produk s i s ebelum ny a.

Gambar 3.7 Diagram alir pengecekan produksi yang tidak bisa diturunkan hingga terminal (Tahap 2).


C.4 Flowchart Pengecekan Input Produksi Yang Tidak Bisa Dicapai dari Simbol Awal (Tahap 3) Pada tahap ini pengecekan dilakukan dengan cara : a) Mencari non terminal hasil produksi simbol awal. b) Dari masing-masing non terminal yang didapat, dicari non termina-non terminal turunannya. c) Langkah b dilakukan berulang-ulang sampai tidak ada lagi non terminal yang ditambahkan d) Jika non terminal yang ditemukan dari langkah a sampai c sama dengan non terminal yang ada di sebelah kiri tanda panah maka tata bahasa bebas konteks bisa dilanjutkan ke tahap selanjutnya. Tetapi jika ternyata di sebelah kiri tanda panah terdapat non terminal yang tidak terdapat di non terminal yang ditemukan pada langkah a sampai c maka non teminal tersebut dikatakan tidak bisa dicapai dari simbol awal atau dari produksi manapun. Sama dengan pengecekan pada tahap 2 untuk input yang demikian user harus memasukkan input yang benar.


Input : Tata bahasa bebas konteks G = ( Ν , Σ , S , Ρ )

Tahap 2 : Cek produksi y ang tidak bisa diturunkan hinggaterminal

Cari A dimana

Cari

B dimana

S → A,S ∈ Ν′, A∈ (Ν ∪Σ )*

A → B, A ∈ Ν′

B ∈ ( Ν ∪ Σ′ ) *

Apakah ada dimana A → w, (sebelah kiri ‘ →’)

A, A ∈ Ν′

∉ w ∈ (Ν ∪ Σ′ ) *

tidak

ya

Tata Bahasa Bebas Konteks disederhanakan ?

tidak

Tahap 4 : Cek bentuk normalChomsky

Gambar 3.8 Diagram alir pengecekan produksi yang tidak bisa dicapai dari simbol awal (Tahap 3)


C.5 Flowchart Perubahan Terminal Lebih dari 1 Menjadi Non Terminal (Tahap 5) Flowchart dalam tahap 5 ini merupakan urutan langkah dari perubahan terminal lebih dari satu menjadi non terminal. Pertama kali akan dilakukan pengecekan terhadap input apakah terdapat aturan produksi yang sudah dalam bentuk normal Chomsky. Jika ada maka hasil tersebut akan dikirimkan ke output. Tetapi jika aturan-aturan produksi tersebut tidak dalam dalam bentuk normal Chomsky akan dilakukan pengecekan kembali apakah dalam aturan produksi tersebut terdapat simbol terminal yang jumlahnya lebih dari satu. Jika ya maka simbol terminal tersebut diubah menjadi simbol non terminal..


Tahap 3 : Cek produksi y ang tidak bisa dicapai dari simbol awal

Ρ:

ya

A → a, A ∈ Ν, a ∈ Σ A → BC, A, B , C ∈ Ν

tidak

Ρ : A → w , w ≥ 1,

tidak

w = X 1, X 2,,, X X

i

∈ Σ (n ≥ 2 )

n

ya

Ubah

Xi ∈Σ

Tambahkan

dengan

Ci ∈ Ν

Ci → X i

Tahap 6 : Ubah Ρ : A→ w untuk w > 2 , w∈ Ν

Output : bentuk normal chomsky G ′ = ( Ν ′, Σ ′, S ′, Ρ′),

A → a , A ∈ Ν ′, a ∈ Σ ′ A → BC , A , B , C ∈ Ν ′

Gambar 3.9 Diagram alir perubahan terminal lebih dari 1 menjadi non terminal(Tahap 5)


C.6 Flowchart Perubahan NonTerminal Lebih dari 2 Menjadi Tepat 2 Non Terminal (Tahap 6). Setelah sebagian proses transformasi ke bentuk normal Chomsky yang digambarkan dalam flowchart tahap 5 selesai, proses tersebut akan dilanjutkan sampai tercapai bentuk normal Chomsky yang diagram alirnya digambarkan dalam flowchart tahap 6 di bawah ini. Proses yang dilakukannya adalah : a. 2 string pertama digantikan dengan non terminal baru berupa huruf kapital Z diikuti angka 0. b. Non terminal baru (Z0) dan non terminal kedua digantikan lagi dengan non terminal baru Z1 dan seterusnya sampai didapatkan tepat 2 non terminal. c. Selanjutnya hasil dari transformasi dan aturan-aturan produksi baru yang terbentuk tersebut dimasukkan dalam output .

Tahap 5:

U bah

Ρ : A → w , w ≥ 1, w = X 1 , X 2 , , , X n X i ∈ Σ ( n ≥ 2 )

X

U bah m e n ja d i

i

(w

∈ Σ

dengan

C

→ B 1 , B 2 ,.. B A →

Z

n − 3

B

n

n

i

∈

Ν

∈ Ν

(n

≥ 2

))

,Z ∈ Ν

O u t p u t : B e n t u k N o r m a l C h o m s ky

G ′ = (Ν ′ , Σ ′ , S ′ , Ρ ′ ) A → a , A ∈ Ν ′, a ∈ Σ ′ A → B C , A, B , C ∈ Ν ′

Gambar 3.10 Diagram alir perubahan non terminal lebih dari 2 menjadi tepat 2 non terminal (Tahap 6)


D. Perancangan Struktur Data Program transformasi kebentuk normal Chomsky ini terdapat 3 kelas Java dan 4 GUI Form Java, yaitu : 1. Kelas java dengan objek ‘Huruf’ dan ‘Chomsky’ 2. Frame Form Java dengan objek ‘Layar_Sampul’, ‘Layar_Utama’, ‘Layar_Tambah_Produksi’ dan ‘Layar_Input_Produksi’ D.1 Kelas Huruf Kelas CFG meliputi konstruktor, beberapa method dan field. Field kelas CFG : String huruf; int jumHuruf;

Konstruktor : public Huruf(String hrf, int jumHrf)

Method : public String getHuruf(){} public int getJumHuruf(){} public void tambahJumHuruf(){}

D.2 Kelas Chomsky Field kelas Chomsky : String [] produksi; int jumProduksi; String [] produksi1; int jumProduksi1; String [] produksi2; int jumProduksi2; String [] mappingZ; int jumMappingZ; String [] mappingZ1; int jumMappingZ1;


Huruf [] terminal1; Huruf [] nonTerminal1; int jumTerminal1, jumNonTerminal1; Huruf [] terminal2; Huruf [] nonTerminal2; int jumTerminal2, jumNonTerminal2;

Konstruktor : public Chomsky() {}

Method : public String [] ambilProduksi(){} public String [] ambilProduksi1(){} public String [] ambilProduksi2(){} public String cekProduksi(){} public String getHurufTerminal1(int index){} public String getHurufTerminal2(int index){} public String getHurufNonterminal1(int index){} public String getHurufNonterminal2(int index){} public int getJumHurufTerminal1(int index){} public int getJumHurufTerminal2(int index){} public int getJumHurufNonTerminal1(int index){} public int getJumHurufNonTerminal2(int index){} public int getJumTerminal1(){} public int getJumTerminal2(){} public int getJumNonTerminal1(){} public int getJumNonTerminal2(){} public void inisialisasi(){} private String nilaiZ(String hrf){} public void prosesChomsky1(){} public void prosesChomsky2(){} public void setJumlahHuruf(String produk){} public void setJumlahHuruf2(String produk){} public void tambahProduksi(String produk){} private String ubahHurufBesar(String hrf, int totalHrf){}


D.3 Frame Form Java Frame

Form

Java

meliputi

kelas

Layar_Sampul,

Layar_Utama,

Layar_Tambah_Produksi dan Layar_Input_Produksi yang diimport menggunakan ‘import javax.swing.JOptionPane’, ‘import javax.swing.DefaultComboBoxModel’ dan ‘import javax.swing.DefaultListModel’ yang berisi kelas-kelas untuk membuat komponen GUI yang disediakan pada masing-masing form.

E. Implementasi Program transformasi ke bentuk normal Chomsky ini dalam prosesnya mengalami perubahan tahap demi tahap untuk mencapai bentuk normal Chomsky yang optimal. Sebagai langkah awal, program melakukan pengecekan untuk penyederhanaan tata bahasa bebas konteks, kemudian pengecekan dengan mencari produksi yang sudah memenuhi syarat bentuk normal Chomsky. Selanjutnya, program akan melakukan transformasi ke bentuk normal Chomsky. E.1 Pengecekan Bentuk Produksi Tunggal Pengecekan dilakukan pada saat user menginputkan tata bahasa bebas konteks yaitu pada ‘Layar_Input_Produksi’. Dalam layar ini disediakan tombol terminal berupa huruf Yunani ‘a’ sampai ‘e’ , non terminal berupa huruf kapital ‘A’ sampai ‘E’ dan ‘S’, tanda ‘|’, tanda ‘OK’, tanda ‘HAPUS KARAKTER’ dan tanda ‘BATAL’. Jika user menginputkan simbol non terminal sebanyak 1 pada hasil produksi maka program akan mengnonaktifkan tanda ‘OK’ dan tanda ‘|’. Sedangkan semua tombol simbol terminal dan non terminal diaktifkan. Setelah user menambahkan simbol terminal atau non terminal maka program akan


mengaktifkan tanda ‘OK’ dan tanda ‘|’. Berikut adalah beberapa penggalan programnya : private void jButton_AActionPerformed(java.awt.event. ActionEvent evt) { if (hrfProduksi) { jLabel_S.setText("A"); produksi = "A->"; hrfProduksi = false; enable_hrfkecil(true); return; } produksi = produksi + "A"; jumBesar++; if (awal) { jLabel_P.setText("A"); awal = false; } else jLabel_P.setText(jLabel_P.getText() + "A"); if (jumBesar >= 2) { jButton_Garis.setEnabled(true); jButtonOK.setEnabled(true); } jButtonHapusKarakter.setEnabled(true); }

private void jButton_aActionPerformed(java.awt.event. ActionEvent evt) { produksi = produksi + "a"; if (awal) { jLabel_P.setText("a"); awal = false; } else jLabel_P.setText(jLabel_P.getText() + "a"); jButton_Garis.setEnabled(true);


jButtonOK.setEnabled(true); jumKecil++; jButtonHapusKarakter.setEnabled(true); }

private void jButtonOKActionPerformed(java.awt.event. ActionEvent evt) { int jumHuruf = 0; int i; String produk = produksi.substring(3, produksi.length()); for (i=0; i<=produk.length()-1; i++) { if (produk.charAt(i) != '|' ) jumHuruf++; } if (jumHuruf > 20) { JOptionPane.showMessageDialog(this, "Ruas kanan Tanda Panah Tidak Boleh Lebih Dari 20 Simbol"); return; } OK = true; this.dispose(); }

private void jButton_GarisActionPerformed(java.awt.event. ActionEvent evt) { produksi = produksi + "|"; jLabel_P.setText(jLabel_P.getText() + "|"); jButton_Garis.setEnabled(false); jButtonOK.setEnabled(false); jumBesar = 0; jumKecil = 0; }

private void jButtonHapusKarakterActionPerformed(java.awt. event.ActionEvent evt) { String hp = jLabel_P.getText(); if (hp.compareTo("") != 0) { if (Character.isUpperCase(produksi.charAt(produksi.


length()-1))) jumBesar--; else if Character.isLowerCase(produksi. charAt (produksi.length()-1))) jumKecil--; else if (produksi.charAt(produksi.length()-1)=='|') { //set JumHurufBesar&JumHurufKecil jika karakter | String produk = produksi.substring(0,produksi. length() - 1); int i = produk.length()-1; jumBesar = 0; jumKecil = 0; while (i>=0) { if (produk.charAt(i) == '|') break; if (produk.charAt(i) == '>') break; if (Character.isUpperCase(produksi.charAt(i))) jumBesar++; else if (Character.isLowerCase (produksi.charAt(i))) jumKecil++; i--; } JOptionPane.showMessageDialog(this, Integer. toString(jumBesar)); JOptionPane.showMessageDialog(this, Integer. toString(jumKecil)); } produksi = produksi.substring(0, produksi.length()-1); hp = hp.substring(0, hp.length()-1); jLabel_P.setText(hp); if ( (jumBesar <= 1) && (jumKecil<=0) ) { jButtonOK.setEnabled(false); jButton_Garis.setEnabled(false); } else { jButtonOK.setEnabled(true);


jButton_Garis.setEnabled(true); } } else jButtonHapusKarakter.setEnabled(false); }

private void jButtonBatalActionPerformed(java.awt.event. ActionEvent evt) { BATAL = true; this.dispose(); }

E.2 Pengecekan Produksi Yang Tidak Bisa Diturunkan Hingga Terminal Program akan mengecek input supaya tidak mengandung produksi yang tidak bisa diturunkan sampai ke terminal. Dalam hal ini program tidak akan menghilangkan produksi yang tidak digunakan tersebut, tetapi program hanya melakukan pengecekan. Selanjutnya user harus menginputkan kembali tata bahasa bebas konteks yang benar. private boolean cekProduksiTidakBisaDiturunkan() { String produk; String nonTerminalKiri = ""; String nonTerminalKanan = ""; int i, j; boolean adaHurufBesar; produksi_bantu = new String[10]; //INISISALISASI NONTERMINALKIRI DAN VARIABEL ARRAY PRODUKSI for (i=0; i
(nonTerminalKiri.indexOf(produk.charAt(j))

< 0) nonTerminalKiri = nonTerminalKiri +


produk.substring(j, j+1); } } produksi_bantu[i] = produk + "0"; } // end for i // CEK NON TERMINAL YANG ADA HURUF KECIL for (i=0; i

} nonTerminalKanan2 = nonTerminalKanan3; boolean ada;

for (i=0; i<nonTerminalKanan2.length(); i++) { ada = false; for

(j=0;

j<nonTerminalKanan.length();

j++)

{

if(nonTerminalKanan.charAt(j)==nonTerminalKanan2. charAt(i) ) { ada = true; break; } } if (ada == false) { nonTerminalKanan = nonTerminalKanan + nonTerminalKanan2.substring(i, i+1); } } String msg = ""; for ( i=0; i<nonTerminalKiri.length(); i++ ) { ada = false; for ( j=0; j<nonTerminalKanan.length(); j++ ) { if(nonTerminalKiri.charAt(i)== nonTerminalKanan. charAt(j) ) { ada = true; break; } } if ( ada == false) { if (msg.indexOf("Tata Bahasa Bebas Konteks Tidak Sederhana

Karena

Non

Terminal

"

+

nonTerminalKiri.substring(i, i+1) + " Tidak Bisa Diturunkan Hingga Terminal\n") < 0 ) msg = msg + "Tata Bahasa Bebas Konteks Tidak Sederhana

Karena

Non

Terminal

nonTerminalKiri.substring(i, Tidak

Bisa

Terminal\n";

Diturunkan

"

i+1)

+

+ "

Hingga


} } // for ( i=0; i<nonTerminalKiri.length(); i++ ) if ( msg.compareTo("") == 0 ) return true; else { msg = msg + "\n Apakah anda ingin melanjutkan Transformasi ke Bentuk Normal Chomsky tanpa menyederhanakan Tata Bahasa Bebas Konteks?"; if (JOptionPane.showConfirmDialog(this, msg, "Chomsky", JOptionPane.YES_NO_OPTION) == 0) return true; else return false; } }

E.3 Pengecekan Produksi Yang Tidak Bisa Dicapai dari Simbol Awal Setelah input tidak mengandung produksi yang tidak bisa diturunkan, program akan mengecek lagi sampai input tersebut tidak mengandung produksi yang tidak bisa dicapai dari simbol awal. Sama dengan pengecekan sebelumnya program tidak menghilangkan simbol non terminal yang tidak berguna tersebut, melainkan hanya pengecekan dan user harus memasukkan lagi input yang benar. private boolean cekNonTerminalTidakBisaDicapai() { String produk; String[] produksi = new String[10]; String nonTerminalKiri = ""; String nonTerminalKanan = "";

int i, j; //INISISALISASI NONTERMINALKIRI DAN VARIABEL ARRAY PRODUKSI for (i=0; i

nonTerminalKanan = "S"; nonTerminalKanan = listNonTerminalKanan(nonTerminalKanan, produksi, "S"); boolean ada; String msg = ""; for ( i=0; i<nonTerminalKiri.length(); i++ ) { ada = false; for ( j=0; j<nonTerminalKanan.length(); j++ ) { if (nonTerminalKiri.charAt(i)== nonTerminalKanan. charAt(j) ) { ada = true; break; } } if ( ada == false) { if (msg.indexOf("Tata Bahasa Bebas Konteks Tidak Sederhana

Karena

Non

Terminal

nonTerminalKiri.substring(i,

i+1)

+

" "

+

Tidak

Bisa Dicapai dari S \n") < 0 ) msg = msg + "Tata Bahasa Bebas Konteks Tidak Sederhana

Karena

Non

Terminal

nonTerminalKiri.substring(i,

i+1)

"

+

+

"

Tidak Bisa Dicapai dari S \n"; } } // for ( i=0; i<nonTerminalKiri.length(); i++ ) if ( msg.compareTo("") == 0 ) return true; else { msg

=

msg

+

"\n

Apakah

anda

ingin

melanjutkan

Transformasi ke Bentuk Normal Chomsky tanpa menyederhanakan Tata Bahasa Bebas Konteks ?"; if (JOptionPane.showConfirmDialog(this, msg, "Chomsky", JOptionPane.YES_NO_OPTION) == 0) return true; else return false; } } // end function


E.4 Pengecekan Bentuk Normal Chomsky Program akan melakukan pengecekan tata bahasa bebas konteks yang sudah dalam bentuk bentuk normal Chomsky, yaitu produksi yang mengandung tepat satu terminal atau dua non terminal. Berikut penggalan programnya : String produk, produk2, hrf, z; int i, j, jumHrf; for(i=0; i<jumProduksi; i++){ produk = produksi[i]; produksi1[i] = produk.substring(0,3); jumHrf = 0; for(j=3; j<produk.length(); j++){ hrf = produk.substring(j,j+1); if(produk.charAt(j) == '|') jumHrf = 0; else jumHrf++; if(Character.isLowerCase(hrf.charAt(0))){ if(j+1<produk.length()) if(produk.charAt(j+1) != '|') jumHrf++; else produksi1[i] = produksi1[i] + hrf; } else produksi1[i] = produksi1[i] + hrf; } }

// end for j

// end for i

jumProduksi1 = jumProduksi;

Program akan membiarkan produksi yang sudah dalam bentuk normal Chomsky dan mengirimkan produksi tesebut ke output.


E.5 Pengubahan Simbol Terminal Menjadi Non Terminal Mentransformasikan tata bahasa bebas konteks ke dalam bentuk normal Chomsky perlu dilakukan pengubahan dari simbol-simbol terminal menjadi simbol non terminal. Pengubahan untuk produksi A → w dengan w > 1 . Dalam program ini semua terminal yang mengalami perubahan menjadi non terminal, simbol non terminalnya menggunakan lambang huruf kapital Z yang diikuti dengan indeks yang dimulai dari ‘0’. private String nilaiZ(String hrf){ int i, j; String Z, batas, namaHrf; for(i=0; i<jumMappingZ; i++){ for(j=0; j
// end for j

Z = (mappingZ[i].substring(0, j+1)); namaHrf = (mappingZ[i].substring(j+3)); if(namaHrf.compareTo(hrf) == 0){ return Z; }

}

// end for i

namaHrf

= "Z"+Integer.toString(jumMappingZ);

mappingZ[jumMappingZ] = namaHrf + "->" + hrf ; jumMappingZ ++; return namaHrf; }


E.6 Pengubahan Simbol Non Terminal Lebih dari 2 Menjadi Tepat 2 Non Terminal Hasil transformasi pertama menyebabkan produksi berbentuk A → w dengan w ≥ 2 . Oleh karena itu untuk mencapai produksi berbentuk A → w dengan w = 2 non terminal dilakukan pemecah string pada ruas kanan produksi yang panjangnya lebih dari dua non terminal. private String ubahHurufBesar(String hrf, int totalHrf){ int i, j, jumHrf, ind1; String hrfTemp, hrf1; jumHrf = 0; i = 0; ind1 = 0; hrf1 = hrf; hrfTemp = hrf;

while(i

System.out.println("HrfBsr (ind1,i+1)+"=>"+hrfTemp); totalHrf--; if(totalHrf<=2) break; ind1 = 0; i = 0; jumHrf = 0; hrf1 = hrfTemp; } else i++; } return hrfTemp; }

"+hrf1.substring


BAB IV HASIL DAN PEMBAHASAN

A. Hasil Implementasi Proses pengaplikasian perangkat lunak (software) ke dalam bahasa pemprograman merupakan hasil dari pengembangan perancangan proses dimana sistem sudah jadi dan siap digunakan sehingga dapat dioperasikan sesuai dengan fungsi dan tujuan dibuatnya perangkat lunak tersebut. Apabila terdapat kesalahankesalahan pada sistem dapat diketahui pada saat implementasi perangkat lunak ini. Kesalahan sistem dapat terjadi karena kesalahan pada penulisan program, kesalahan logika ataupun kesalahan pada sistem operasi yang digunakan. Perangkat

lunak

yang

dibuat

memiliki

batasan-batasan

dalam

implementasinya yang lebih mengarahkan bentuk program aplikasi sesuai dengan rancangan program. Hasil implementasi perancangan antar muka dari bab sebelumnya adalah sebagai berikut :


A.1 Form Layar_Sampul Form Layar_Sampul merupakan form yang akan tampil pertama kali untuk memulai menjalankan program transformasi ke bentuk normal Chomsky.

Gambar 4.1. Form Layar_Sampul Pada form Layar_Sampul ini terdiri 2 tombol (jbutton), yaitu : a) jButton ’Keluar’ , untuk keluar dari program. b) JButton ‘Lanjut’, untuk melanjutkan ke layar berikutnya masuk ke form Layar_Utama.


A.2 Form Layar_Utama Form Layar_Utama merupakan form yang utama di mana user akan melakukan proses transformasi ke bentuk normal Chomsky dengan program ini. Semua proses yang dilakukan user akan ditampilkan dalam form Layar_Utama. Berikut adalah hasil implementasi form Layar_Utama:

Gambar 4.2. Form Layar_Utama Sesuai dengan perancangan kebutuhan antarmuka yang telah dilakukan, maka aplikasi yang dibuat memiliki beberapa komponen Swing yang berfungsi untuk membantu dan memudahkan user dalam mengoperasikan aplikasi yang telah dibuat.


Beberapa komponen Swing yang terdapat pada aplikasi ini adalah : a) jScrollPaneInput, berfungsi untuk men-scroll komponen input yang besar. b) jScrollPaneOutput1, berfungsi untuk men-scroll komponen output1 yang besar. c) jScrollPaneOutput 2, berfungsi untuk men-scroll komponen output2 yang besar. d) jListInput, berfungsi untuk menampilkan list dari item-item input. e) jListOutput1, berfungsi untuk menampilkan list dari item-item output1. f) jListOutput2, berfungsi untuk menampilkan list dari item-item output2. g) jButton ‘Chomsky Baru’, berfungsi untuk memasukkan input dengan masuk ke form Layar_Tambah_Produksi.. h) jButton ‘Proses Chomsky’, berfungsi untuk menampilkan hasil transformasi (output 1, dan output 2). i) jButton ‘Keluar’, berfungsi untuk keluar dari program.

A.3. Form Layar_Tambah_Produksi Pada form Layar_Tambah_Produksi ini berfungsi untuk memasukkan atau menambah produksi, mengedit produksi dan menghapus produksi. Dalam form ini mempunyai 1 list dan 5 tombol (jButton), yaitu : a) List, berfungsi sebagai tempat masukan jumlah produksi. b) jButton ‘Tambah Produksi’, berfungsi untuk menambah produksi c) jButton ‘Edit Produksi’, berfungsi untuk mengedit hasil produksi.


d) jButton ‘Hapus Produksi’, berfungsi untuk menghapus produksi. e) jButton ‘OK’, yang berarti selesai berfungsi untuk melanjutkan ke layar berikutnya f) jButton ‘BATAL’, berfungsi untuk membatalkan.proses yang telah dilakukan oleh user.

Gambar 4.3. Form Layar_Tambah_Produksi


A.4. Form Layar_Input_Produksi Form yang berfungsi untuk memasukkan produksi ini akan tampil setelah user menekan tombol ‘Tambah Produksi’ pada form Layar_Tambah_Produksi. Tampilan layar ini terdiri dari tombol-tombol yang diperlukan untuk menuliskan tata bahasa bebas konteks.

Gambar 4.4. Form Layar_Input_Produksi Terdiri dari : a) jLabel ‘S’, sebagai simbol awal. b) jLabel ‘Æ’, sebagai tanda penunjuk hasil produksi c) jLabel kosong yang diletakkan setelah tanda panah yang berfungsi sebagai tempat user meletakkan hasil produksi d) jButton simbol non terminal dari ‘A’ sampai ‘E’ dan ‘S’. e) jButton simbol terminal dari ‘a’ sampai ‘e’. f) jButton ‘|’ sebagai pemisah hasil produksi. g) jButton ‘OK’, berfungsi untuk mengakhiri memasukkan produksi. h) jButton ‘HAPUS KARAKTER’, berfungsi untuk menghapus karakterkarakter hasil produksi


i) jButton ‘BATAL’, berfungsi untuk membatalkan simbol yang dimasukkan dan proses yang telah dilakukan oleh user.

B. Penggunaan Program Dalam hal ini akan dijelaskan penggunaan program perubahan tata bahasa bebas konteks menjadi tata bahasa bebas konteks dalam bentuk normal Chomsky. B.1 Masukan (Input) Program B.1.1 Aturan Penulisan Tata Bahasa Bebas Konteks Penulisan masukan yang berupa tata bahasa bebas konteks agar dapat dimengerti program memilikai beberapa aturan, yaitu : 1. Simbol non terminal dapat berupa huruf kapital ‘A, B, C, D, E’ dan‘S’. 2. Simbol terminal dapat berupa huruf Yunani ‘a, b, c, d, e’. 3. Simbol tanda panah untuk memisahkan non terminal dengan produksi berupa gabungan karakter ‘-’ dan ‘>’. 4. Simbol yang memisahkan antara dua produksi dari sebuah non terminal dengan tanda ’|’. S → aB | bb | Ac Simbol-simbol di atas disediakan program dalam bentuk tombol-tombol pada form Layar_Input_Produksi.


B.2 Proses Program Proses transformasi yang dilakukan program sehingga mencapai bentuk normal Chomsky, yaitu : a. Input berupa tata bahasa bebas konteks yang tidak mengandung ε dan produksi tunggal. b. Program melakukan pengecekan produksi yang tidak bisa dicapai dari simbol awal dan tidak bisa diturunkan. c. Program akan membiarkan produksi yang sudah dalam bentuk normal Chomsky dan menampilkan dalam output. d. Untuk produksi berbentuk

A → w dengan

w > 1 , program akan

mengkonversikan w menjadi untai-untai yang hanya memuat non terminal-non terminal, yang dalam program ini dilambangkan dengan huruf kapital Z yang diikuti dengan angka dimulai dari 0. Hasil langkah c dan d di masukkan dalam output sebagai langkah 1, sehingga semua produksi berbentuk A → w dengan w sebuah terminal atau string yang semuanya terdiri dari non terminal. e. Proses selanjutnya program memecah string pada ruas kanan produksi yang panjangnya lebih dari dua non terminal. f. Setelah program melakukan langkah a sampai e sehingga dicapai bentuk normal Chomsky, keluaran akan ditampilkan dalam output.


C. Pengujian Program Contoh : 1. Mentransformasikan tata bahasa bebas konteks : P = S → Bb | AA | de A → aBb B → bC | bbbb C→c

Gambar 4.5. Form hasil pengujian program contoh 1. Berdasarkan percobaan yang ditampilkan gambar 4.5 di atas, input merupakan tata bahasa bebas konteks yang sudah sederhana.


Produksi yang sudah dalam bentuk normal Chomsky ditampilkan dalam output pada langkah 1. S → AA C→c Dari bentuk produksi awal, produksi yang belum memenuhi bentuk normal Chomsky adalah : S → Bb | de A → aBb B → bC | bbbb Untuk mentransformasikannya, pertama program akan mengubah simbol terminal menjadi simbol non terminal yang dalam program ini dilambangkan dengan huruf kapital Z diikuti dengan angka dimulai dari 0 : S → BZ0 | AA | Z1Z2 A → Z3BZ0 B → Z0C | Z0Z0Z0Z0 Dan menambahkan non terminal hasil perubahan ke terminal yang diubah : Z0 → b Z1 → d Z2 → e Z3 → a Produksi yang sudah mengalami perubahan di atas ditampilkan dalam output pada langkah 1.


Selanjutnya dari hasil output langkah 1, program mentransformasikan produksi sampai didapatkan hasil bentuk normal Chomsky. Produksi yang memiliki simbol non terminal lebih 2 diubah : A → Z3BZ0 B → Z0Z0Z0Z0 Program akan mengubah produksi di atas dengan mengubah 2 string pertama dan seterusnya : A → Z4Z0 B → Z6Z0 Kemudian menambahkan simbol non terminal hasil perubahan ke simbol non terminal yang diubah : Z4 → Z3B Z6 → Z5Z0 Hasil transformasi dari output langkah 1 tersebut selanjutnya ditampilkan pada output pada langkah 2.

2. Mentransformasikan tata bahasa bebas konteks : N = ( S, A, B , C, D ) Σ = ( a, b, c, d, e ) Ρ=



Gambar 4.6. Form Layar_Tambah_Produksi contoh 2. Dalam contoh 2 pada gambar 4.6 terdapat non terminal ‘D’ berada di hasil produksi (sebelah kanan tanda panah) tetapi tidak terdapat di pemproduksi (sebelah kiri tanda panah). Hal ini menunjukkan bahwa input merupakan tata bahasa bebas konteks yang belum sederhana. Sehingga setelah user menekan tonbol ‘OK’ maka akan tampil pesan sebagai berikut :

Gambar 4.7. Form hasil pengecekan contoh 2.


Jika user menekan tombol ‘Yes’, maka tata bahasa bebas konteks akan ditransformasikan dengan mengabaikan penyederhanaan tata bahasa bebas konteks, yaitu tanpa harus menurunkan non terminal D sampai ke terminal.

Gambar 4.8. Form hasil transformasi contoh 2. Tetapi jika user menekan tombol ‘No’, maka untuk sampai ke bentuk normal Chomsky user harus mengedit tata bahasa bebas konteks tersebut sampai ke bentuk yang sederhana.

3. Mentransformasikan tata bahasa bebas konteks : N = ( S, A, B , C, D ) Σ = ( a, b, c, d, e ) Ρ=

S → aabAac | BB | BBB | Ddee


A → aaa | cdA B → BDc | c C → cde D→e

Gambar 4.9. Form Layar_Tambah_Produksi contoh 3. Non terminal ‘C’ hanya terletak di pemproduksi (sebelah kiri tanda panah). Hasil produksi (sebelah kanan tanda panah) tidak terdapt non terminal ‘C’. Terbukti bahwa input merupakan tata bahasa bebas konteks yang belum


sederhana. Sehingga setelah user menekan tonbol ‘OK’ maka akan tampil pesan sebagai berikut :

Gambar 4.10. Form hasil pengecekan contoh 3. Jika user menekan tombol ‘Yes’, maka tata bahasa bebas konteks akan ditransformasikan walaupun non terminal C tidak bisa dicapai dari simbol awal.

Gambar 4.11. Form hasil transformasi contoh 3. Jika user menekan tombol ‘No’, maka untuk sampai ke bentuk normal Chomsky user harus mengedit tata bahasa bebas konteks tersebut sampai ke bentuk yang sederhana sesuai dengan pesan yang ditampilkan.


D. Pembahasan/Analisis Program Berdasarkan beberapa percobaan masukan, dilakukan pengamatan serta pengujian. Pengujian ini dilakukan untuk memperoleh gambaran kesesuaian antara input dengan output. Adapun hasil pembahasan program transformasi ke bentuk normal Chomsky ini meliputi : 1. Pemprograman menggunakan tipe data array, karena array beranggotakan elemen-elemen (variabel) yang bertipe data sama dan dapat diakses dengan memanggil nama array beserta indeks elemennya. 2. Pemprograman menggunakan kelas String. Pada program Java, string diperlakukan sebagai suatu objek yang pada program ini, kelas String sangat berperan penting karena memiliki beberapa method, yaitu : a. Membuat dan menginisialisasi string. b. Membaca karakter secara individu dalam string. c. Membandingkan dua string, yang pada program ini menggunakan method ‘compareTo’. d. Mengubah karakter kecil menjadi kapital dan sebaliknya dengan mengecek karakter string input menggunakan bentuk ‘isLowerCase’ dan ‘isUpperCase’. e. Mencari karakter dan substring yang berguna untuk mencari indeks dari suatu karakter atau indeks awal dari suatu substring dalam suatu String menggunakan method ‘int indexOf (int ch)’. f. Mengekstrak atau mengambil suatu substring yaitu membuat string baru yang karakternya diambil dari suatu substring suatu string.


Method yang digunakan untuk mengekstrak substring tersebut adalah ‘String substring(int startIndex, int endIndex)’. Method tersebut mengambil suatu substring yang berawal dari posisi yang ditunjukkan oleh startIndex dan diakhiri oleh endIndex. 3. Untuk mengubah non terminal - non terminal produksi yang jumlahnya lebih dari dua, program akan mengambil 2 karakter pertama dan selajutnya akan mengambil 1 karakter berikutnya sampai mencapai tepat 2 non terminal. 4. Jika w ∈ Σ * dapat diturunkan dan | w | > 0, maka penurunannya mempunyai tepat 2 | w | langkah. 5. Berdasarkan hasil percobaan, jumlah produksi dari masing-masing langkah dapat dirumuskan sebagai berikut : Untuk setiap M produksi, N non terminal, K terminal, dengan P jumlah simbol tiap hasil produksi, maka maksimum jumlah produksi pada langkah pertama didapatkan (M+K) produksi dan maksimum jumlah produksi pada langkah ke dua (bentuk normal Chomsky) didapatkan (M+K)+(P-2) produksi. Jumlah produksi langkah pertama = (M+K) produksi dan langkah ke dua = (M+K)+(P-2) produksi akan dipenuhi jika K > 1 dan P > 2. Contoh Gambar 4.11 : M = 5 produksi N = 5 simbol K = 5 simbol


Jumlah produksi langkah 1 = M + K =5+5 = 10 Jumlah produksi langkah 2 = (M+K) + (P-2) = 10 + (Ρs + ΡA + ΡB + ΡC + ΡD ) = 10 + ((4+0+1+2)+(1+1)+(1+0)+(1)+(0)) = 10 + (7+2+1+1) = 10 + 11 = 21


BAB V PENUTUP

A. Kesimpulan Berdasarkan hasil pengujian yang telah dilakukan, maka dapat disimpulkan sebagai berikut : 1. Jika G = ( Ν , Σ, S , Ρ ) adalah sebuah tata bahasa bebas konteks dan

ε ∉ L (G ) , maka G dapat ditransformasikan ke bentuk normal Chomsky. 2. Jika w ∈ Σ * dapat diturunkan dan | w | > 0, maka penurunannya mempunyai tepat 2 | w | langkah. 3. Untuk setiap M produksi, N non terminal, K terminal, dengan P jumlah simbol tiap hasil produksi, maka maksimum jumlah produksi pada langkah pertama didapatkan (M + K) produksi dan makimum jumlah produksi pada langkah ke dua (bentuk normal Chomsky) didapatkan (M+K)+(P-2) produksi. 4. Program hanya dapat melakukan pengecekan apakah produksi tata bahasa bebas konteks yang diinputkan merupakan produksi yang sederhan, tetapi program tidak dapat menyederhanakan input tata bahasa bebas konteks yang tidak sederhana.. 5. Program dapat menampilkan bentuk normal Chomsky sesuai dengan langkah-langkah

proses

pentransformasiannya

sehingga

dengan

mentransformasikan tata bahasa bebas konteks ke bentuk normal Chomsky menggunakan program Java proses menjadi lebih cepat .

68


B. Saran 1. Untuk mendapatkan hasil yang lebih sempurna, sebaiknya program dapat melakukan penyederhanan tata bahasa bebas konteks dan dapat menampilkan secara terurut proses penyederhanaan tata bahasa bebas konteks. 2. Jumlah simbol terminal dan non terminalnya tidak terbatas. 3. Jumlah produksi tidak terbatas.

69


DAFTAR PUSTAKA

Benny Hermawan, 2004. Menguasai Java 2 dan Object Oriented Programing. Yogyakarta : Andi. Benyamin L. Sinaga, 2005. Pemprograman Berorientasi Objec Dengan Java. Yogyakarta : Gava Media. Dean Kelley, 1995. Automata and Formal Language : An Introduction. Englewood Clift, NJ : Prentice Hall. Firrar Utdirartatmo, 2001. Teori Bahasa dan Otomata. Yogyakarta : J&J Learning.

70

PROGRAM BANTU TRANSFORMASI TATA BAHASA BEBAS KONTEKS KE BENTUK NORMAL CHOMSKY SKRIPSI

Recommend Documents