Teori Bahasa dan Otomata
i
iv
Pengantar Teori Bahasa & Otomata
TEORI BAHASA & OTOMATA Penulis: Adi Sulistyo Nugroho, S.Kom., M.M. Edisi Kedua Cetakan Pertama, 2013 Hak Cipta 2013 pada penulis, Hak Cipta dilindungi undang-undang. Dilarang memperbanyak atau memindahkan sebagian atau seluruh isi buku ini dalam bentuk apa pun, secara elektronis maupun mekanis, termasuk memfotokopi, merekam, atau dengan teknik perekaman lainnya, tanpa izin tertulis dari penerbit.
Ruko Jambusari No. 7A Yogyakarta 55283 Telp. : 0274-889836; 0274-889398 Fax. : 0274-889057 E-mail :
[email protected]
Nugroho, Adi Sulistyo, S.Kom., M.M. TEORI BAHASA & OTOMATA/Adi Sulistyo Nugroho, S.Kom., M.M. - Edisi Pertama – Yogyakarta; Graha Ilmu, 2013 xii + 98 hlm, 1 Jil.: 26 cm. ISBN:
978-602-262-011-2
1. Komputer
I. Judul
Buku ini didedikasikan kepada mendiang Bunda, Mintarti dan mendiang Dinda, Lisa
KATA PENGANTAR
P
uji syukur kepada Allah SWT, yang oleh perkenan-Nya, penulis dapat menyelesaikan buku Teori Bahasa dan Otomata ini dengan tuntas. Tak lupa penulis mengucapkan terima kasih kepada pihakpihak yang membantu dalam penyelesaian buku Teori Bahasa dan Otomata baik secara langsung maupun tidak langsung, seperti : 1. Editor saya, bu Marta, yang selalu memberikan masukan untuk membuat buku lebih baik lagi; 2. Ayahanda Kaswadi, yang selalu memberikan nasehat, setia mendampingi di saat-saat senang maupun susah serta selalu mendoakan yang terbaik untuk putranya; 3. Almarhumah Ibunda tercinta Y.Susilih Mintarti; 4. Almarhumah Adinda tercinta Lisa Surviva Prihatini; 5. Kekasih tercinta, Anggun Maharany yang selalu memberikan support berupa kata-kata manis via telepon ataupun SMS; 6. Saudara Sahlan yang telah meminjamkan notebooknya dan saudara Novri Aldi yang telah membantu saya dalam hal tata letak gambar; 7. Rekan-rekan dosen di lingkungan Fakultas Teknik Informatika Universitas Pamulang; 8. Rekan-rekan dosen di lingkungan Jurusan Teknik Sistem Informasi STMIK (STI & K) Jakarta; 9. Dan lain-lainnya yang tak dapat disebutkan secara satu per satu. Terakhir kata, mohon ma’af bilamana buku ini masih ada kekurangan, karena bagaimana pun penulis masih tetap harus belajar banyak tentang apa pun selama masih diberikan kuasa umur panjang. Terima kasih. Jakarta, 25 Januari 2013 Adi Sulistyo Nugroho
viii
Pengantar Teori Bahasa & Otomata
Teori Bahasa dan Otomata
ix
DAFTAR ISI
KATA PENGANTAR DAFTAR ISI BAB 1 MENGENAL OTOMATA 1.1. Pengertian Teori Otomata 1.2. Istilah Otomata Pertama 1.3. Buku Otomata Pertama 1.4. Implementasi Teori Otomata 1.5. Konsep-Konsep Pokok Teori Otomata 1.6. Lambang Struktural
v vii 1 1 2 2 2 2 7
BAB 2 OTOMATA HINGGA/FINITE STATE AUTOMATA (FSA) 2.1. Konsep Dasar Otomata Hingga/Finite State Automata (FSA) 2.2. Pengelompokkan Finite State Automata (FSA) 2.3. Ekuivalensi Finite State Automata (FSA) 1.4. Aplikasi FSA : Penelusuran Teks 2.5. Ekuivalensi NFA dan DFA
9 9 10 14 16 17
BAB 3 TATA BAHASA (GRAMMAR) DAN BAHASA BEBAS KONTEKS 3.1. Pengertian Bahasa Bebas Konteks 3.2. Aturan Dasar 3.3. Notasi Untuk Derivation 3.4. Leftmost Derivation dan Rightmost Derivation 3.5. Pohon Urai 3.6. Terminologi Pohon
19 19 20 21 21 22 22
x
Pengantar Teori Bahasa & Otomata
3.7. 3.8. 3.9. 3.10. 3.11. 3.12. 3.13. 3.14.
Aplikasi Tata Bahasa Bebas Konteks Parsing dan Keanggotaan Ambiguitas pada Tata Bahasa Bebas Konteks Menghilangkan Ambiguitas dari Tata Bahasa Bebas Konteks Pumping Lemma untuk Bahasa Bebas Konteks Bahasa Bebas Konteks dan Bahasa Pemrograman Algoritma CYK untuk Bahasa Bebas Konteks Tata Bahasa (Grammar)
23 23 24 24 25 26 26 27
BAB 4 PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS 4.1. Tujuan 4.2. Penghilangan Produksi Useless 4.3. Penghilangan Produksi Unit 4.4. Penghilangan Produksi ε
33 33 34 37 38
BAB 5 BENTUK NORMAL CHOMSKY 5.1. Pengertian Bentuk Normal Chomsky 5.2. Pembentukan Bentuk Normal Chomsky
43 43 43
BAB 6 BENTUK NORMAL GREIBACH 6.1. Pengertian Bentuk Normal Greibach 6.2. Pembentukan Bentuk Normal Greibach
49 49 50
BAB 7 PUSHDOWN AUTOMATA 7.1. Pengertian Pushdown Automata 7.2. Pergerakan Pushdown Automata 7.3. Mekanisme Kerja Pushdown Automata 7.4. Jenis Pushdown Automata 7.5. DeterministicPushdown Automata
53 53 53 54 56 56
BAB 8 MENGENAL MESIN TURING 8.1. Pengertian Tentang Mesin Turing 8.2. Deskripsi Singkat Mengenai Mesin Turing 8.3. Ketentuan Notasi untuk Mesin Turing 8.4. Mensimulasikan Sebuah Komputer Dengan Mesin Turing
59 59 59 59 60
BAB 9 EKSPRESI REGULER 9.1. Pengertian Ekspresi Reguler 9.2. Operator-Operator Ekspresi Reguler 9.3. Hubungan RE dan Otomata Hingga (FSA)
63 63 65 65
BAB 10 PENERAPAN TEORI OTOMATA DALAM COMPILER (TEKNIK KOMPILASI) 10.1. Mengenal Teknik Kompilasi
67 67