Breaking News
Thursday, October 4, 2018
MATERI Matematika Dasar & Contohnya Lengkap PDF
Pendahuluan Materi Lengap Matematika Dasar
Dalam Matematika Dasar terdapat konsep dari himpunan obyek-obyek,
khususnya tentang konsep himpunan dari bilangan-bilangan yang banyak sekali
diterapkan untuk matematika lebih lanjut maupun penerapan di bidang-bidang
yang lain. Himpunan bilangan yang penting untuk diketahui adalah himpunan
bilangan Asli, himpunan bilangan Cacah, himpunan bilangan Bulat, himpunan
bilangan Rasional, himpunan bilangan Irrasional (tak terukur), dan himpunan
bilangan Real. Sifat-sifat dari bilangan ini akan digunakan dalam Bentuk Pangkat,
Penarikan Akar, dan Logaritma.
Diharapkan mahasiswa dapat memahami konsep himpunan bilangan yang
penting untuk diketahui dan mampu menggunakan sifat-sifat dari himpunan
bilangan diantaranya yaitu Bentuk Pangkat, Penarikan Akar, dan Logaritma.
B. Himpunan Bilangan
Konsep dari himpunan obyek-obyek yang paling penting dipelajari untuk
matematika lebih lanjut adalah konsep dari himpunan bilangan-bilangan. Beberapa
konsep dari himpunan bilangan-bilangan tersebut diantaranya adalah himpunan
bilangan Asli, himpunan bilangan Cacah, himpunan bilangan Bulat, himpunan
bilangan Rasional, himpunan bilangan Irrasional (tak terukur), dan himpunan
bilangan Real.
1. Himpunan bilangan Asli atau disebut juga himpunan bilangan bulat positif dapat
ditulis sebagai : N
2. Himpunan bilangan Cacah ditulis : W
3. Himpunan bilangan Bulat ditulis : I -3, - 2, -
4. Himpunan bilangan Rasional / Terukur ditulis :
, a,b I, b 0
b
Q x x a yaitu bilangan yang dapat dinyatakan sebagai
hasil bagi antara dua bilangan bulat (pecahan) dengan syarat bahwa nilai
penyebut tidak sama dengan nol, contoh :
7
, 5
5
, 3
4
, 1
2
1
dan sebagainya.
5
Dengan demikian bilangan rasional adalah bilangan yang dapat ditulis dalam
bentuk pecahan
b
a
dengan a dan b bilangan bulat dan b 0 . Adapun
himpunan bilangan rasional terdiri dari bilangan bulat, bilangan pecahan murni,
dan bilangan pecahan desimal.
5. Himpunan bilangan Irrasional (tak terukur) ditulis : Q' x x Q yaitu
bilangan yang tidak dapat dinyatakan sebagai hasil bagi antara dua bilangan
bulat (pecahan), tapi dapat dinyatakan dengan bilangan desimal tak tentu atau
2
sebagainya.
6. Himpunan bilangan Real (nyata) ditulis : R x x bilangan Real . Bilangan
rasional dan Irrasional merupakan himpunan bilangan real.
Dengan demikian, himpunan bilangan Asli adalah subset dari himpunan
bilangan Cacah. Himpunan bilangan Cacah adalah subset dari himpunan bilangan
Rasional. Sedangkan himpunan bilangan baik Rasional maupun Irrasional disebut
himpunan bilangan Real. Himpunan bilangan yang tidak Real adalah himpunan
bilangan Imaginer ataupun himpunan bilangan Kompleks. Himpunan-himpunan
bilangan di atas dapat ditulis dalam bentuk subset sebagai berikut :
N W I Q R
Sifat Ketidaksamaan Bilangan Real
a. Sembarang bilangan Real a dan b, dapat terjadi salah satu dari tiga hal yaitu : a <
b, b < a, atau a = b.
b. Jika a < b dan b < c maka a < c .
c. Jika a < b, maka a + c < b + c untuk sembarang nilai c.
d. Jika a < b dan c > 0 maka ac < bc.
e. Jika a < b dan c < 0 maka ac > bc.
Sistem bilangan Real dibentuk atas dasar sistem bilangan Asli, di mana semua
sifat-sifatnya dapat diturunkan. Jika x, y, dan z adalah bilangan Real maka sifat-sifat
bilangan Real adalah :
a. Sifat komutatif untuk penjumlahan
x + y = y + x
6
b. Sifat komutatif untuk perkalian
x.y = y.x
c. Sifat assosiatif untuk penjumlahan
x + (y + z) = (x + y) + z
d. Sifat assosiatif untuk perkalian
x (yz) = (xy) z
e. Sifat distributif
x (y + z) = xy + xz
f. Jika x dan y dua bilangan Real, maka terdapat suatu bilangan Real z sehingga x +
z = y. Bilangan z ini kita nyatakan dengan y x dan disebut selisih dari y dan x.
Selisih x x kita nyatakan dengan simbol 0. Simbol 0 ini selanjutnya disebut nol.
g. Terdapat paling sedikit satu bilangan real x x dan y dua bilangan Real
dengan x z demikian sehingga x.z = y.
Bilangan z ini kita nyatakan dengan
x
y
dan disebut hasil bagi dari y dan x. Hasil
bagi x dan x dinyatakan dengan simbol 1, yang selanjutnya disebut satu dan
tidak bergantung pada x.
C. Bentuk Pangkat, Akar dan Logaritma
1. Bentuk Pangkat Bulat
Definisi
Fungsi notasi pangkat salah satunya adalah untuk menyederhanakan penulisan
atau meringkas penulisan. Contoh, 10.000.000,- dapat ditulis dengan notasi
pangkat 107. Notasi pangkat dapat menghemat tempat, sehingga notasi pangkat
banyak digunakan dalam perumusan dan penyederhanakan perhitungan.
Pangkat Bulat Positif
Perkalian berulang dari suatu bilangan dapat dinyatakan dalam bentuk bilangan
berpangkat bilangan bulat positif.
Contoh:
2 = 21
2 . 2 = 22
2 . 2 . 2 = 23
2 . 2 . 2 . 2 = 24
7
2 . 2 . 2 . 2 . 2 = 25
2 . 2 . 2 . 2 . 2 . 2 = 26
Bentuk 26 6 disebut bilangan berpangkat bulat
positif. Bilangan 2 disebut bilangan pokok atau bilangan dasar dan bilangan 6
yang ditulis agak di atas disebut pangkat atau eksponen. Secara umum bilangan
berpangkat dapat ditulis :
Jika a bilangan real atau dan n bilangan bulat positif, maka
an
a disebut bilangan pokok dan n disebut pangkat.
Contoh 1.1
1. 32 = 3 . 3 = 9
2. 64 = 4 . 4 . 4 = 43
3. 648 = 2 . 2 . 2 . 3 . 3 . 3 . 3 = 23 . 34
4.
4
3
2
3
. 2
3
. 2
3
. 2
3
2
Contoh 1.2
Tentukan nilai dari persamaan berikut untuk nilai variabel yang ditentukan.
1. x3 2x2 3x 4 untuk x = 2
2 3 2 2 2 3 2 4 8 8 6 4 26
2. 3x3 2x2 y 3xy2 4y3 untuk x = - 1 dan y = 2
3 1 3 2 1 2 2 3 1 2 2 4 2 3 3 4 12 32 21
Sifat-sifat Pangkat Bulat Positif
Pada bilangan berpangkat bulat positif dapat dilakukan beberapa operasi aljabar
seperti : perkalian, pemangkatan, dan pembagian untuk bilangan berpangkat
bulat positif. Perhatikan teorema-teorema untuk bentuk perkalian,
pemangkatan, dan pembagian dari bilangan berpangkat bulat positif berikut:
a. Jika a bilangan real, p dan q adalah bilangan bulat postitif maka
a p . aq a p q
b. Jika dan 0, p dan q bilangan bulat positif maka
8
p q
q p
a
a p q
a
a a a q p
p q
q
p
p q
1 ; jika
1 ; jika
; jika
:
c. Jika a bilangan real, p dan q bilangan bulat positif maka
a p q a p. q a pq
d. Jika a dan b bilangan real, p bilangan bulat maka
ab p a p b p
Contoh 1.3
Sederhanakan :
1. 23 . 24 = 23+4 = 27
2. x2 . x6 = x2+6 = x8
3. 2x 3 y 3x 2 y 3 2( 3)x 3 2 y1 3 6x5 y 4
Contoh 1.4
Kalikanlah 2x 2 y 3xy2 dengan 4x3 y2 .
Penyelesaian
5 3 4 4
2 2 3 2 2 3 1 2 1 3 2 2
8 12
2 3 4 2( 4) 3( 4)
x y x y
x y xy x y x y x y
Pangkat Bulat Negatif dan Nol
Jika pada bentuk perpangkatan pangkat dari bilangan dasar kurang dari satu dan
nol maka akan diperoleh pangkat bilangan bulat negatif dan nol.
Contoh 1.5
3-1 ; 3-2 ; 3-3 ; 3-4 ; 3-5 ; dan 30
a-1 ; a-2 ; a-3 ; a-4 ; a-5 a-n ; dan a0
Untuk mendefinisikan an dengan a bilangan real dan n bilangan bulat negarif dan
nol, maka dapat digunakan teorema-teorema perpangkatan pada bilangan bulat
positif, seperti :
1 n
n
a
a . Jika teorema p q
q
p
a
a
a digunakan maka akan diperoleh
a a0 1
a
a n n
n
n
dan untuk q = p + n maka diperoleh
p p n n
p n
p
q
p
a a
a
a
a
a ( ) .
9
Dengan demikian maka terdapat teorema berikut,
Jika 0, a bilangan real dan n bilangan bulat positif maka
n
n
a
a 1 dan a0 = 1.
2. Bentuk Akar
menyatakan akar
pangkat dua yaitu merupakan kebalikan dari kuadrat. Pernyataan yang ditulis
dengan tanda akar disebut bentuk akar.
Contoh 1.6
1. Karena 52 = 25 maka 25 5
2. Karena 82 = 64 maka 64 8
Contoh 1.7
Bentuk-bentuk berikut merupakan contoh bentuk akar :
2, 3, 5, 21 dan sebagainya.
Operasi aljabar seperti penjumlahan, pengurangan, perkalian, dan pembagian
dapat juga dilakukan terhadap bentuk akar. Operasi tersebut digunakan untuk
merasionalkan penyebut yang dinyatakan dalam bentuk akar. Operasi-operasi
aljabar tersebut adalah sebagai berikut :
a. a x b x a b x
b. a x b x a b x
c. a . b ab
d. a a aa a a 2 a
2
. 2
e.
b
a : b a
f.
cd
ab
c d
a b
Contoh 1.8
Sederhanakanlah.
1. 3 2 4 2 (3 4) 2 7 2
2. 8 32 2 2 4 2 (2 4) 2 6 2
10
3. 32 . 8 32.8 256 16
4. 4 2
8
32 : 8 32
5. 25 5
2
50
2
50
2
5.10
2
5. 10
Merasionalkan Pecahan Bentuk Akar
Suatu pecahan yang penyebutnya mengandung bentuk akar dapat
disederhanakan bentuknya dengan cara merasionalkan bentuk akar yang ada
pada penyebutnya. Untuk merasionalkan bentuk pecahan dari penyebut
tersebut maka pembilang dan penyebut harus dikalikan dengan bentuk rasional
dari bentuk akar yang ada pada penyebutnya. Di bawah ini bentuk-bentuk
rumusan untuk penyederhanaan pecahan yang mengandung bentuk akar :
Wednesday, October 3, 2018
MATERI DIGITAL FORENSIK Pengertian & Contohnya LENGKAP
Digital Forensik
Apa dan Bagaimana????
By :Asrizal
Abstract. The increasing of information technology in fact followed by issues around cyber crime and
computer security. Nowadays, many cases of law has opened our mind and shows us the critical of digital
forensic as the method in proofing crimes beside the law and role of regulation that happening. As more
criminals utilize technology to achieve their goals and avoid apprehension, there is a developing need for
individuals who can analyze and utilize evidence stored on and transmitted using computers. By apllying
science methods in investigating digital evidence, made digital forensic as the answer of law standing
effort in digital era.
Kata kunci: digital forensik, kejahatan, bukti digital
Pendahuluan
emajuan teknologi dan industri yang merupakan hasil dari budaya manusia
disamping membawa dampak positif, dalam arti dapat didayagunakan untuk
kepentingan umat manusia juga membawa dampak negatif terhadap
perkembangan dan peradaban manusia itu sendiri. Dampak negatif yang dimaksud
adalah berkaitan dengan dunia kejahatan. J.E. Saheteapy menyatakan dalam tulisannya,
bahwa kejahatan erat kaitannya dengan perkembangan masyarakat. Semakin maju
kehidupan masyarakat, maka kejahatan juga ikut semakin maju. Kejahatan juga menjadi
sebagian dari hasil budaya itu sendiri. Hal ini berarti bahwa semakin tinggi tingkat
budaya dan semakin modern suatu bangsa, maka semakin modern pula kejahatan itu
dalam bentuk, sifat dan cara pelaksanaannya.1
Secara garis besar, kejahatan yang berkaitan dengan teknologi informasi dapat
dibagi menjadi dua bagian besar. Pertama, kejahatan yang bertujuan merusak atau
menyerang sistem atau jaringan komputer. Dan kedua, kejahatan yang menggunakan
komputer atau internet sebagai alat bantu dalam melancarkan kejahatan. Namun begitu,
mengingat teknologi informasi merupakan konvergensi telekomunikasi, komputer dan
media, kejahatan ini berkembang menjadi lebih luas lagi.
1 Wahid, A. & Labib, M. 2005, Kejahatan Mayantara (Cyber Crime), Bandung: PT. Refika Aditama. hal
21.
K
2
Dalam catatan beberapa literatur dan situs-situs yang mengetengahkan
cybercrime, terdapat berpuluh jenis kejahatan yang berkaitan dengan dunia cyber. Yang
masuk dalam kategori kejahatan umum yang difasilitasi teknologi informasi antara lain
penipuan kartu kredit, penipuan bursa efek, penipuan perbankan, pornografi anak,
perdagangan narkoba, serta terorisme. Sedang kejahatan yang menjadikan sistem dan
fasilitas TI (teknologi informasi) sebagai sasaran diantaranya adalah denial of service
attack (DOS), defacing, cracking ataupun phreaking.2
Berdasarkan fungsi sistem komputer sebagai penyedia informasi, ancaman
terhadap sistem komputer dikategorikan menjadi empat yaitu:
1. Interruption, merupakan suatu ancaman terhadap avaibility, informasi atau data
dalam komputer dirusak, dihapus, sehingga jika dibutuhkan sudah tidak ada lagi.
2. Interception, merupakan ancaman terhadap kerahasiaan (secrecy), informasi
yang ada didalam sistem disadap oleh orang yang tidak berhak.
3. Modification, merupakan ancaman terhadap integritas. Orang yang tidak berhak
berhasil menyadap lalu lintas informasi yang sedang dikirim lalu mengubahnya
sesuai keinginannya.
4. Fabrication, merupakan ancaman ancaman terhadap integritas. Orang yang tidak
berhak berhasil meniru atau memalsukan suatu informasi sehingga orang yang
menerima informasi menyangka informasi tersebut berasal dari orang yang
dikehendaki oleh si penerima informasi tersebut.3
Keempat ancaman terhadap system komputer tersebut digambarkan sebagai berikut:
Gambar 1. Ancaman terhadap Sistem Komputer
2 Ibid, hal 27.
3 Simarmata, J. 2006, Pengamanan Sistem Komputer, Yogyakarta : Andi Offset. hal 30-31
3
Dengan meningkatnya kejahatan berbasis teknologi dalam berbagai modus
sebagaimana disebutkan diatas, maka diperlukan suatu mekanisme ilmiah untuk
menganalisa dan menelusuri bukti-bukti digital yang ada baik yang disimpan maupun
yang ditransmisikan melalui komputer atau perangkat digital lainnya.
Sesuai dengan Undang-undang Republik Indonesia Nomor 11 Tahun 2008
tentang Informasi dan Transaksi Elektronik bahwa informasi elektronik dan/atau
dokumen elektronik dan/atau hasil cetaknya merupakan alat bukti hukum yang sah,4
maka peran digital forensik sebagai metode pembuktian suatu kasus kejahatan secara
digital menjadi sangat penting. Sebagaimana tertuang dalam Penjelasan atas Undangundang
Republik Indonesia Nomor 11 Tahun 2008 tentang Informasi dan Transaksi
Elektronik: “……… pembuktian merupakan faktor yang sangat penting, mengingat
informasi elektronik bukan saja belum terakomodasi dalam sistem hukum acara
Indonesia secara komprehensif, melainkan juga ternyata sangat rentan untuk diubah,
disadap, dipalsukan, dan dikirim ke berbagai penjuru dunia dalam waktu hitungan
detik. Dengan demikian, dampak yang diakibatkannya pun bisa demikian kompleks dan
rumit.”5
Lebih lanjut informasi elektronik adalah satu atau sekumpulan data elektronik,
termasuk tetapi tidak terbatas pada tulisan, suara, gambar, peta, rancangan, foto,
electronic data interchange (EDI), surat elektronik (electronic mail), telegram, teleks,
telecopy atau sejenisnya, huruf, tanda, angka, Kode Akses, simbol, atau perforasi yang
telah diolah yang memiliki arti atau dapat dipahami oleh orang yang mampu
memahaminya.6
Berbagai kasus yang mencuat akhir-akhir ini sangat bergantung penelusurannya
kepada bukti-bukti digital yang ada. Maka mulailah kita melihat bukti-bukti digital ini
diungkap di persidangan dan bahkan diekspose oleh berbagai media dalam pemberitaan
mulai dari foto digital, rekaman pembicaraan, rekaman video, sms, email, dan lain
sebagainya seperti pada kasus pembobolan ATM, kasus Bank Century, kasus Artalyta
Suryani, kasus pembunuhan Nasruddin Zulkarnain yang melibatkan mantan ketua KPK,
kasus Prita Mulyasari, kasus video mesra yang melibatkan artis papan atas, dan yang
paling menghebohkan adalah kasus mafia pajak Gayus Tambunan.
4 Undang-undang Republik Indonesia Nomor 11 Tahun 2008 tentang Informasi dan Transaksi Elektronik
Bab III Informasi Dokumen dan Tanda Tangan Elektronik pasal 5 ayat 1. 2009. Yogyakarta: Pustaka
Yustisia. hal 14
5 Ibid, hal 53.
6 Ibid, hal 51
4
Sejarah Komputer Forensik
Barang bukti yang berasal dari komputer telah muncul dalam persidangan
hampir 30 tahun. Awalnya, hakim menerima bukti tersebut tanpa melakukan
pembedaan dengan bentuk bukti lainnya. Seiring dengan kemajuan teknologi komputer,
perlakuan serupa dengan bukti tradisional akhirnya menjadi bermasalah. Bukti-bukti
komputer mulai masuk kedalam dokumen resmi hukum lewat US Federal Rules of
Evidence pada tahun 1976. Selanjutnya dengan berbagai perkembangan yang terjadi
muncul beberapa dokumen hukum lainnya, antara lain adalah:
The Electronic Communications Privacy Act 1986, berkaitan dengan
penyadapan peralatan elektronik.
The Computer Security Act 1987 (Public Law 100-235), berkaitan dengan
keamanan system komputer pemerintahan.
Economic Espionage Act 1996, berhubungan dengan pencurian rahasia dagang.
Pembuktian dalam dunia maya memiliki karakteristik tersendiri. Hal ini
dikarenakan sifat alami dari teknologi komputer memungkinkan pelaku kejahatan untuk
menyembunyikan jejaknya. Karena itulah salah satu upaya untuk mengungkap
kejahatan komputer adalah lewat pengujian sistem dengan peran sebagai seorang
detektif dan bukannya sebagai seorang user. Kejahatan computer (cybercrime) tidak
mengenal batas geografis, aktivitas ini bisa dilakukan dari jarak dekat, ataupun dari
jarak ribuan kilometer dengan hasil yang serupa. Penjahat biasanya selangkah lebih
maju dari penegak hukum, dalam melindungi diri dan menghancurkan barang bukti.
Untuk itu tugas ahli digital forensik untuk menegakkan hukum dengan mengamankan
barang bukti, rekonstruksi kejahatan, dan menjamin jika bukti yang dikumpulkan itu
akan berguna di persidangan.7
Bagaimanapun, digital forensik banyak dibutuhkan dalam berbagai keperluan,
bukan hanya pada kasus-kasus kriminal yang melibatkan hukum. Secara umum
kebutuhan digital forensik dapat diklasifikasikan sebagai berikut:
Keperluan investigasi tindak kriminal dan perkara pelanggaran hukum.
Rekonstruksi duduk perkara insiden keamanan komputer.
Upaya-upaya pemulihan kerusakan sistem.
Troubleshooting yang melibatkan hardware maupun software.
7 Prayudi, Y & Afrianto, D. S. 2007. Antisipasi Cyber Crime menggunakan Teknik Komputer Forensik.
Makalah disajikan pada Seminar Nasional Aplikasi Teknologi Informasi 2007, diselenggarakan
Universitas Islam Indonesia, Yogyakarta, 16 Juni 2007.
5
Keperluan untuk memahami sistem ataupun berbagai perangkat digital dengan
lebih baik.
Definisi Digital Forensik
Ada beberapa definisi yang bisa dijadikan acuan tentang apa sebenarnya Digital
Forensik. Menurut Marcella8: digital forensik adalah aktivitas yang berhubungan
dengan pemeliharaan, identifikasi, pengambilan/penyaringan, dan dokumentasi
bukti digital dalam kejahatan computer. Istilah ini relatif baru dalam bidang komputer
dan teknologi, tapi telah muncul diluar term teknologi (berhubungan dengan investigasi
bukti-bukti intelijen dalam penegakan hukum dan militer) sejak pertengahan tahun
1980-an.
Sedangkan menurut Budhisantoso9, digital forensik adalah kombinasi disiplin
ilmu hukum dan pengetahuan komputer dalam mengumpulkan dan menganalisa
data dari sistem komputer, jaringan, komunikasi nirkabel, dan perangkat
penyimpanan sehingga dapat dibawa sebagai barang bukti di dalam penegakan
hukum.
Definisi lain sebagaimana yang terdapat pada situs Wikipedia10 yaitu: Komputer
forensik yang juga dikenal dengan nama digital forensik, adalah salah satu cabang
ilmu forensik yang berkaitan dengan bukti legal yang ditemui pada komputer dan
media penyimpanan digital.
Dari definisi diatas dapat disimpulkan bahwa digital forensik adalah
penggunaan teknik analisis dan investigasi untuk mengidentifikasi, mengumpulkan,
memeriksa dan menyimpan bukti/informasi yang secara magnetis
tersimpan/disandikan pada komputer atau media penyimpanan digital sebagai alat
bukti dalam mengungkap kasus kejahatan yang dapat dipertanggungjawabkan
secara hukum.
Karena luasnya lingkup yang menjadi objek penelitian dan pembahasan digital
forensik maka ilmu digital forensik dibagi kedalam beberapa bagian yaitu: firewall
forensics, network forensics, database forensics, dan mobile device forensics.
8 Marcella, A. J. & Greenfiled, R. S. 2002. “Cyber Forensics a field manual for collecting, examining,
and preserving evidence of computer crimes”, Florida: CRC Press LLC.
9 Budhisantoso, Nugroho, Personal Site, (http:// www.forensik-komputer.info, diakses 24 Desember
2010).
10 Wikipedia, (http://id.wikipedia.org/wiki/Komputer_forensik, diakses 25 Desember 2010.)
6
Komponen Digital Forensik
Komponen pada digital forensik pada umumnya hampir sama dengan bidang
yang lain. Komponen ini mencakup manusia (people), perangkat/peralatan (equipment)
dan aturan (protocol) yang dirangkai, dikelola dan diberdayakan sedemikian rupa dalam
upaya mencapai tujuan akhir dengan segala kelayakan dan kualitas sebagaimana bisa
dilihat pada gambar berikut:
Gambar 2. Komponen Digital Forensik
Manusia yang diperlukan dalam komputer forensik merupakan pelaku yang
tentunya mempunyai kualifikasi tertentu untuk mencapai kualitas yang diinginkan.
Belajar forensik tidak sama dengan menjadi ahli dalam bidang forensik. Dibutuhkan
lebih dari sekedar pengetahuan umum tentang komputer, tetapi juga pengalaman
(experience) disamping berbagai pelatihan (training) pada materi-materi digital forensik
yang telah ditempuh dan dibuktikan dengan sertifikat-sertifikat pendukung.
Ada tiga kelompok sebagai pelaku digital forensik:
1. Collection Specialist, yang bertugas mengumpulkan barang bukti berupa
digital evidence.
2. Examiner, tingkatan ini hanya memiliki kemampuan sebagai penguji terhadap
media dan mengekstrak data.
3. Investigator, tingkatan ini sudah masuk kedalam tingkatan ahli atau sebagai
penyidik.
Manusia
Aturan Perangkat
7
Menurut Budhisantoso,11 secara garis besar perangkat untuk kepentingan
digital forensik dapat dibedakan kepada dua kategori yaitu hardware dan software. Ada
banyak jenis perangkat hardware yang digunakan pada implementasi digital forensik
dengan fungsi dan kemampuan yang beragam. Mulai dari yang sederhana dengan
komponen single-purpose seperti write blocker (fungsinya hampir sama dengan “writeprotect”
pada disket, pada optical media dan hardisk fungsi seperti ini tidak ada) yang
memastikan bahwa data tidak akan berubah manakala diakses,12 sampai pada sistem
komputer lengkap dengan kemampuan server seperti F.R.E.D (Forensic Recovery of
Evidence Device). Sedangkan perangkat software dikelompokkan kedalam dua
kelompok yaitu aplikasi berbasis command line dan aplikasi berbasis GUI (Graphical
User Interface).
Aturan merupakan komponen yang paling penting dalam pemodelan digital
forensik, didalamnya mencakup prosedur dalam mendapatkan, menggali, menganalisa
barang bukti dan akhirnya bagaimana menyajikan hasil penyelidikan dalam laporan.
Tahapan pada Digital Forensik
Ada berbagai tahapan pada proses implementasi digital forensik. Namun
menurut Kemmish,13 secara garis besar dapat diklasifikasikan kepada empat tahapan,
yaitu:
1. Identifikasi bukti digital
2. Penyimpanan bukti digital
3. Analisa bukti digital
4. Presentasi
Keempat tahapan ini secara terurut dan berkesinambungan digambarkan pada
gambar berikut:
11 Budhisantoso, Nugroho, Personal Site, (http:// www.forensik-komputer.info, diakses 24 Desember
2010).
12 Kirschenbaum, M. G, dkk. 2010. Digital Forensic and Born-Digital Content in Cultural Heritage
Collection. Washington: Council on Library and Information Resources.
13 Kemmish, R. M. What is forensic computer. Australian institute of Criminology, Canberra. (http://:
www.aic.gov.au/publications/tandi/ti118.pdf, diakses 15 Desember 2010).
8
Gambar 3. Tahapan Digital Forensik
1. Identifikasi bukti digital
Pada tahap ini segala bukti-bukti yang mendukung penyelidikan
dikumpulkan. Penyelidikan dimulai dari identifikasi dimana bukti itu berada,
dimana disimpan, dan bagaimana penyimpanannya untuk mempermudah
penyelidikan. Media digital yang bisa dijadikan sebagai barang bukti mencakup
sebuah sistem komputer, media penyimpanan (seperti flash disk, pen drive, hard
disk, atau CD-ROM), PDA, handphone, smart card, sms, e-mail, cookies, source
code, windows registry, web browser bookmark, chat log, dokumen, log file, atau
bahkan sederetan paket yang berpindah dalam jaringan komputer.
Tahapan ini merupakan tahapan yang sangat menentukan karena bukti-bukti
yang didapatkan akan sangat mendukung penyelidikan untuk mengajukan seseorang
ke pengadilan dan diproses sesuai hukum hingga akhirnya dijebloskan ke tahanan.
Penelusuran bisa dilakukan untuk sekedar mencari "ada informasi apa disini?"
sampai serinci pada "apa urutan peristiwa yang menyebabkan terjadinya situasi
terkini?".
Berdasarkan klasifikasinya file yang menjadi objek penelusuran terbagi
kepada tiga kategori, yaitu: file arsip (archieved files), file aktif (active files) dan file
sisa (residual data). File Arsip adalah file yang tergolong arsip karena kebutuhan
file tersebut dalam fungsi pengarsipan. Mencakup penanganan dokumen untuk
disimpan dalam format yang ditentukan, proses mendapatkannya kembali dan
pendistribusian untuk kebutuhan yang lainnya, misalnya beberapa dokumen yang
didigitalisasi untuk disimpan dalam format TIFF untuk menjaga kualitas dokumen.
Identifikasi Penyimpanan Analisa Presentasi
Media Data Informasi Bukti
Umpan Balik
9
File aktif adalah file yang memang digunakan untuk berbagai kepentingan yang
berkaitan erat dengan kegiatan yang sedang dilakukan, misalnya file-file gambar,
dokumen teks, dan lain-lain. Sedangkan file yang tergolong residual mencakup filefile
yang diproduksi seiring proses komputer dan aktivitas pengguna, misalkan
catatan penggunan dalam menggunakan internet, database log, berbagai temporary
file, dan lain sebagainya.
Beberapa software atau tools yang bisa digunakan dalam mendukung
tahapan ini antara lain:
Forensic Acquisition Utilities (http://users.erols.com/gmgarner/forensics/)
FTimes (http://ftimes.sourceforge.net/FTimes/index.shtml)
Liveview (http://liveview.sourceforge.net/)
Netcat (http://www.atstake.com/research/tools/network_utilities/pdd)
ProDiscover DFT (www.techpathways.com)
Psloggedon
(http://www.sysinternals.com/ntw2k/freeware/psloggedon.shtml)
TULP2G (http://sourceforge.net/projects/tulp2g/)
UnxUtils (http://unxutils.sourceforge.net)
Webjob (http://webjob.sourceforge.net/WebJob/index.shtml).
dan lain sebagainya
Forensik pada dasarnya adalah pekerjaan identifikasi sampai dengan muncul
hipotesa yang teratur menurut urutan waktu. Sangat tidak mungkin forensik dimulai
dengan munculnya hipotesa tanpa ada penelitian yang mendalam berdasarkan buktibukti
yang ada. Dalam kaitan ini pada digital forensik dikenal istilah chain of custody
dan rules of evidence. 14
Chain of custody artinya pemeliharaan dengan meminimalisir kerusakan yang
diakibatkan karena investigasi. Tujuan dari chain of custody adalah:
Menjamin bahwa bukti itu benar-benar masih asli (authentic).
Pada saat persidangan, bukti masih bisa dikatan seperti pada saat ditemukan
karena biasanya jarak antara penyidikan dan persidangan relatif lama.
14 http://budi.insan.co.id/courses/el7010/2003/rahmadi-report.pdf, diakses pada: 12 Januari 2011.
10
Beberapa hal yang menjadi pertimbangan sesuai dengan aturan chain of custody
ini adalah:
Siapa yang mengumpulkan bukti?
Bagaimana dan dimana?
Siapa yang memiliki bukti tersebut?
Bagaimana penyimpanan dan pemeliharaan bukti itu?
Lalu sebagai alternatif penyelesaian ada beberapa cara yang bisa dilakukan,
yaitu:
1. Gunakan catatan yang lengkap mengenai keluar-masuk bukti dari penyimpanan.
2. Simpan di tempat yang dianggap aman.
3. Akses yang terbatas dalam tempat penyimpanan.
4. Catat siapa saja yang dapat mengakses bukti tersebut.
Sedangkan rules of evidence artinya pengaturan barang bukti dimana barang
bukti harus memiliki keterkaitan dengan kasus yang diinvestigasi dan memiliki kriteria
sebagai berikut:
1. Layak dan dapat diterima (Admissible).
Artinya barang bukti yang diajukan harus dapat diterima dan digunakan demi
hukum, mulai dari kepentingan penyidikan sampai ke pengadilan.
2. Asli (Authentic).
Barang bukti harus mempunyai hubungan keterkaitan yang jelas secara hukum
dengan kasus yang diselidiki dan bukan rekayasa.
3. Akurat (Accurate).
Barang bukti harus akurat dan dapat dipercaya.
4. Lengkap (Complete).
Bukti dapat dikatakan lengkap jika didalamnya terdapat petunjuk-petunjuk yang
lengkap dan terperinci dalam membantu proses investigasi.
2. Penyimpanan bukti digital.
Tahapan ini mencakup penyimpanan dan penyiapan bukti-bukti yang ada,
termasuk melindungi bukti-bukti dari kerusakan, perubahan dan penghilangan oleh
pihak-pihak tertentu. Bukti harus benar-benar steril artinya belum mengalami proses
apapun ketika diserahkan kepada ahli digital forensik untuk diteliti. Karena bukti
digital bersifat sementara (volatile), mudah rusak, berubah dan hilang, maka
11
pengetahuan yang mendalam dari seorang ahli digital forensik mutlak diperlukan.
Kesalahan kecil pada penanganan bukti digital dapat membuat barang bukti digital
tidak diakui di pengadilan. Bahkan menghidupkan dan mematikan komputer dengan
tidak hati-hati bisa saja merusak/merubah barang bukti tersebut. Sebagaimana
diungkapkan Peter Plummer15:
“When you boot up a computer, several hundred files get changed, the data of
access, and so on. Can you say that computer is still exactly as it was when the
bad guy had it last?”.
Sebuah pernyataan yang patut dipikirkan bahwa bagaimana kita bisa
menjamin kondisi komputer tetap seperti keadaan terakhir ketika ditinggalkan oleh
pelaku kriminal manakala komputer tersebut kita matikan atau hidupkan kembali.
Karena ketika komputer kita hidupkan terjadi beberapa perubahan pada temporary
file, waktu akses, dan seterusnya. Sekali file-file ini telah berubah ketika komputer
dihidupkan tidak ada lagi cara untuk mengembalikan (recover) file-file tersebut
kepada keadaan semula. Komputer dalam kondisi hidup juga tidak bisa
sembarangan dimatikan. Sebab ketika komputer dimatikan bisa saja ada program
penghapus/perusak yang dapat menghapus dan menghilangkan bukti-bukti yang
ada. Ada langkah-langkah tertentu yang harus dikuasai oleh seorang ahli digital
forensik dalam mematikan/menghidupkan komputer tanpa ikut
merusak/menghilangkan barang bukti yang ada didalamnya.
Aturan utama pada tahap ini adalah penyelidikan tidak boleh dilakukan
langsung pada bukti asli karena dikhawatirkan akan dapat merubah isi dan struktur
yang ada didalamnya. Mengantisipasi hal ini maka dilakukan copy data secara
Bitstream Image dari bukti asli ke media penyimpanan lainnya. Bitstream image
adalah metode penyimpanan digital dengan mengkopi setiap bit demi bit dari data
orisinil, termasuk file yang tersembunyi (hidden files), file temporer (temporary
file), file yang terdefrag (defragmented file), dan file yang belum teroverwrite.
Dengan kata lain, setiap biner digit demi digit di-copy secara utuh dalam media
baru. Teknik ini umumnya diistilahkan dengan cloning atau imaging. Data hasil
cloning inilah yang selanjutnya menjadi objek penelitian dan penyelidikan.
15 Seorang pengacara pada Divisi High-Tech Crime di Kepolisian Michigan, Amerika Serikat
12
3. Analisa bukti digital
Tahapan ini dilaksanakan dengan melakukan analisa secara mendalam
terhadap bukti-bukti yang ada. Bukti yang telah didapatkan perlu di-explore kembali
kedalam sejumlah skenario yang berhubungan dengan tindak pengusutan, seperti:
Siapa yang telah melakukan
Apa yang telah dilakukan
Apa saja software yang digunakan
Hasil proses apa yang dihasilkan
Waktu melakukan.
Penelusuran bisa dilakukan pada data-data sebagai berikut: alamat URL
yang telah dikunjungi, pesan e-mail atau kumpulan alamat e-mail yang terdaftar,
program word processing atau format ekstensi yang dipakai, dokumen spreedsheat
yang dipakai, format gambar yang dipakai apabila ditemukan, file-file yang dihapus
maupun diformat, password, registry windows, hidden files, log event viewers, dan
log application. Termasuk juga pengecekan pada metadata. Kebanyakan file
mempunyai metadata yang berisi informasi yang ditambahkan mengenai file
tersebut seperti computer name, total edit time, jumlah editing session, dimana
dicetak, berapa kali terjadi penyimpanan (saving), tanggal dan waktu modifikasi.
Selanjutnya melakukan recovery dengan mengembalikan file dan folder
yang terhapus, unformat drive, membuat ulang partisi, mengembalikan password,
merekonstruksi ulang halaman web yang pernah dikunjungi, mengembalikan emailemail
yang terhapus dan seterusnya.
Tahapan analisis terbagi dua, yaitu: analisis media (media analysis) dan
analisis aplikasi (application analysis) pada barang bukti yang ada. Beberapa tools
analisis media yang bisa digunakan antara lain:
TestDisk (http://www.cgsecurity.org/testdisk.html)
Explore2fs (http://uranus.it.swin.edu.au/~jn/linux/explore2fs.htm)
ProDiscover DFT (http://www.techpathways.com)
Sedangkan untuk analisis aplikasi, beberapa tools yang bisa digunakan seperti:
Event Log Parser
(http://www.whitehats.ca/main/members/Malik/malik_eventlogs/malik_event
logs.html)
Galleta (http://www.foundstone.com/resources/proddesc/galleta.htm)
13
Libpff (http://libpff.sourceforge.net)
Md5deep (http://md5deep.sourceforge.net/)
MD5summer (http://www.md5summer.org/)
Outport (http://outport.sourceforge.net/)
Pasco (http://www.foundstone.com/resources/proddesc/pasco.htm)
RegRipper (http://windowsir.blogspot.com/2008/04/updated-regripper.html)
Rifiuti (http://www.foundstone.com/resources/proddesc/rifiuti.htm)
4. Presentasi
Presentasi dilakukan dengan menyajikan dan menguraikan secara detail
laporan penyelidikan dengan bukti-bukti yang sudah dianalisa secara mendalam dan
dapat dipertanggung jawabkan secara hukum di pengadilan. Laporan yang disajikan
harus di cross-check langsung dengan saksi yang ada, baik saksi yang terlibat
langsung maupun tidak langsung. Hasil laporan akan sangat menentukan dalam
menetapkan seseorang bersalah atau tidak sehingga harus dipastikan bahwa laporan
yang disajikan benar-benar akurat, teruji, dan terbukti.
Beberapa hal penting yang perlu dicantumkan pada saat presentasi/panyajian
laporan ini, antara lain:
Tanggal dan waktu terjadinya pelanggaran
Tanggal dan waktu pada saat investigasi
Permasalahan yang terjadi
Masa berlaku analisa laporan
Penemuan bukti yang berharga (pada laporan akhir penemuan ini sangat
ditekankan sebagai bukti penting proses penyidikan)
Tehnik khusus yang digunakan, contoh: password cracker
Bantuan pihak lain (pihak ketiga)
Training dan Sertifikasi
Untuk menjadi seorang ahli dibidang Digital Forensik, seseorang harus
mempunyai pengetahuan yang mendalam tentang teknologi informasi baik hardware
maupun software. Seperti: sistem operasi, bahasa pemrograman, media penyimpanan
komputer, networking, routing, protokol komunikasi dan sekuriti, kriptologi, teknik
14
pemrograman terbalik, teknik investigasi, perangkat komputer forensik, bentuk/format
file, dan segala perangkat digital forensik baik hardware maupun software.
Kemudian harus mendapatkan pelatihan atau training khusus Digital Forensik
dari berbagai lembaga yang dibuktikan dengan sertifikat keahlian yang tidak sedikit,
antara lain Certified Information System Security Professional (CISSP), lalu Certified
Forensics Analyst (CFA), Experienced Computer Forensic Examiner (ECFE), Certified
Computer Examiner (CCE), Computer Hacking Forensic Investigator (CHFI) dan
Advanced Information Security (AIS).
Seorang ahli Digital Forensik juga ditentukan kapasitasnya dari sudah berapa
lama dia bergerak dibidang ini, kasus-kasus apa saja yang sudah ditangani, dan pernah
diminta kesaksiannya sebagai saksi ahli dalam kasus-kasus tertentu. Penting untuk
diingat bahwa seorang ahli Digital Forensik juga terikat dengan aturan atau kode etik
seperti mengutamakan kejujuran, kebenaran, ketelitian, ketepatan tindakan, tidak
merusak barang bukti dan independen.
Kesimpulan
Dengan adanya Undang-undang Republik Indonesia Nomor 11 Tahun 2008
tentang Informasi dan Transaksi Elektronik segala aktivitas digital yang menyangkut
informasi dan transaksi elektronik mempunyai payung hukum dan dapat dijadikan
sebagai alat bukti yang sah di pengadilan. Berkaitan dengan hal ini perlu suatu
mekanisme pembuktian yang legal dan dapat dipertanggungjawabkan secara hukum
dalam penelusuran bukti-bukti kejahatan khususnya kejahatan komputer (cybercrime).
Dalam menelusuri bukti digital sampai pada proses pengungkapan di
pengadilan, digital forensik menerapkan empat tahapan yaitu: Pengumpulan
(Acquisition), Pemeliharaan (Preservation), Analisa (Analysis), dan Presentasi
(Presentation). Seiring dengan perkembangan teknologi, dimasa depan objek penelitian
dan cakupan digital forensik akan menjadi lebih luas lagi, dan keahlian dalam digital
forensik tentu akan lebih dibutuhkan.
Penulis adalah staf Subbag Akademik dan Kemahasiswaan Fakultas Tarbiyah dan
mahasiswa Program Studi Magister Teknik Informatika Universitas Sumatera Utara.
15
DAFTAR PUSTAKA
Budhisantoso, Nugroho, Personal Site, (http:// www.forensik-komputer.info, diakses 24
Desember 2010).
http://budi.insan.co.id/courses/el7010/2003/rahmadi-report.pdf, diakses pada: 12 Januari
2011.
Kemmish, R. M. What is Forensic Computer. Australian institute of Criminology,
Canberra. (http:// www.aic.gov.au/publications/tandi/ti118.pdf, diakses 15
Desember 2010).
Kirschenbaum, M. G, dkk. 2010. Digital Forensic and Born-Digital Content in
Cultural Heritage Collection. Washington: Council on Library and Information
Resources.
Marcella, A. J. & Greenfiled, R. S. 2002. “Cyber Forensics a field manual for
collecting, examining, and preserving evidence of computer crimes”. Florida:
CRC Press LLC.
Prayudi, Y & Afrianto, D. S. 2007. Antisipasi Cyber Crime menggunakan Teknik
Komputer Forensik. Makalah disajikan pada Seminar Nasional Aplikasi
Teknologi Informasi 2007, diselenggarakan Universitas Islam Indonesia,
Yogyakarta, 16 Juni 2007.
Simarmata, J. 2006. Pengamanan Sistem Komputer. Yogyakarta : Andi Offset.
Undang-undang Republik Indonesia Nomor 11 Tahun 2008 tentang Informasi dan
Transaksi Elektronik Bab III Informasi Dokumen dan Tanda Tangan Elektronik
pasal 5 ayat 1. 2009. Yogyakarta: Pustaka Yustisia.
Wahid, A. & Labib, M. 2005. Kejahatan Mayantara (Cyber Crime). Bandung: PT.
Refika Aditama.
Wikipedia, (http://id.wikipedia.org/wiki/Komputer_forensik, diakses 25 Desember
MATERI Teori Bahasa Dan Automata Pengertian & Contohnya LENGKAP
Pengantar Teori Bahasa & Aotomata
Teori bahasa membicarakan bahasa formal (formal language), terutama untuk
kepentingan perancangan kompilator (compiler) dan pemroses naskah (text
processor). Bahasa formal adalah kumpulan kalimat. Semua kalimat dalam sebuah
bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama. Sebuah bahasa
formal bisa dibangkitkan oleh dua atau lebih tata bahasa berbeda. Dikatakan bahasa
formal karena grammar diciptakan mendahului pembangkitan setiap kalimatnya.
Bahasa manusia bersifat sebaliknya; grammar diciptakan untuk meresmikan kata-kata
yang hidup di masyarakat. Dalam pembicaraan selanjutnya ‘bahasa formal’ akan
disebut ‘bahasa’ saja.
Automata
Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima
(accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.
Beberapa Pengertian Dasar
• Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam
geometri). Sebuah huruf atau sebuah angka adalah contoh simbol.
• String adalah deretan terbatas (finite) simbol-simbol. Sebagai contoh, jika a, b,
dan c adalah tiga buah simbol maka abcb adalah sebuah string yang dibangun dari
ketiga simbol tersebut.
• Jika w adalah sebuah string maka panjang string dinyatakan sebagai w dan
didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut.
Sebagai contoh, jika w = abcb maka w= 4.
• String hampa adalah sebuah string dengan nol buah simbol. String hampa
dinyatakan dengan simbol ε (atau ^) sehingga ε= 0. String hampa dapat
dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.
• Alfabet adalah hinpunan hingga (finite set) simbol-simbol
Operasi Dasar String
Diberikan dua string : x = abc, dan y = 123
• Prefik string w adalah string yang dihasilkan dari string w dengan menghilangkan
nol atau lebih simbol-simbol paling belakang dari string w tersebut.
Contoh : abc, ab, a, dan ε adalah semua Prefix(x)
• ProperPrefix string w adalah string yang dihasilkan dari string w dengan
menghilangkan satu atau lebih simbol-simbol paling belakang dari string w
tersebut.
Contoh : ab, a, dan ε adalah semua ProperPrefix(x)
• Postfix (atau Sufix) string w adalah string yang dihasilkan dari string w dengan
menghilangkan nol atau lebih simbol-simbol paling depan dari string w tersebut.
Contoh : abc, bc, c, dan ε adalah semua Postfix(x)
• ProperPostfix (atau PoperSufix) string w adalah string yang dihasilkan dari string
w dengan menghilangkan satu atau lebih simbol-simbol paling depan dari string w
tersebut.
Contoh : bc, c, dan ε adalah semua ProperPostfix(x)
• Head string w adalah simbol paling depan dari string w.
Contoh : a adalah Head(x)
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 2
• Tail string w adalah string yang dihasilkan dari string w dengan menghilangkan
simbol paling depan dari string w tersebut.
Contoh : bc adalah Tail(x)
• Substring string w adalah string yang dihasilkan dari string w dengan
menghilangkan nol atau lebih simbol-simbol paling depan dan/atau simbol-simbol
paling belakang dari string w tersebut.
Contoh : abc, ab, bc, a, b, c, dan ε adalah semua Substring(x)
• ProperSubstring string w adalah string yang dihasilkan dari string w dengan
menghilangkan satu atau lebih simbol-simbol paling depan dan/atau simbolsimbol
paling belakang dari string w tersebut.
Contoh : ab, bc, a, b, c, dan ε adalah semua Substring(x)
• Subsequence string w adalah string yang dihasilkan dari string w dengan
menghilangkan nol atau lebih simbol-simbol dari string w tersebut.
Contoh : abc, ab, bc, ac, a, b, c, dan ε adalah semua Subsequence(x)
• ProperSubsequence string w adalah string yang dihasilkan dari string w dengan
menghilangkan satu atau lebih simbol-simbol dari string w tersebut.
Contoh : ab, bc, ac, a, b, c, dan ε adalah semua Subsequence(x)
• Concatenation adalah penyambungan dua buah string. Operator concatenation
adalah concate atau tanpa lambang apapun.
Contoh : concate(xy) = xy = abc123
• Alternation adalah pilihan satu di antara dua buah string. Operator alternation
adalah alternate atau .
Contoh : alternate(xy) = xy = abc atau 123
• Kleene Closure : x* = εxxxxxx… = εxx 2 x 3 …
• Positive Closure : x + = xxxxxx… = xx 2 x 3 …
Beberapa Sifat Operasi
• Tidak selalu berlaku : x = Prefix(x)Postfix(x)
• Selalu berlaku : x = Head(x)Tail(x)
• Tidak selalu berlaku : Prefix(x) = Postfix(x) atau Prefix(x) ≠ Postfix(x)
• Selalu berlaku : ProperPrefix(x) ≠ ProperPostfix(x)
• Selalu berlaku : Head(x) ≠ Tail(x)
• Setiap Prefix(x), ProperPrefix(x), Postfix(x), ProperPostfix(x), Head(x), dan
Tail(x) adalah Substring(x), tetapi tidak sebaliknya
• Setiap Substring(x) adalah Subsequence(x), tetapi tidak sebaliknya
• Dua sifat aljabar concatenation :
♦ Operasi concatenation bersifat asosiatif : x(yz) = (xy)z
♦ Elemen identitas operasi concatenation adalah ε : εx = xε = x
• Tiga sifat aljabar alternation :
♦ Operasi alternation bersifat komutatif : xy = yx
♦ Operasi alternation bersifat asosiatif : x(yz) = (xy)z
♦ Elemen identitas operasi alternation adalah dirinya sendiri : xx = x
• Sifat distributif concatenation terhadap alternation : x (yz) = xyxz
• Beberapa kesamaan :
♦ Kesamaan ke-1 : (x*)* = (x*)
♦ Kesamaan ke-2 : εx + = x + ε = x*
♦ Kesamaan ke-3 : (xy)* = εxyxxyyxyyx… = semua string yang
merupakan concatenation dari nol atau lebih x, y, atau keduanya.
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 3
II. GRAMMAR DAN BAHASA
Konsep Dasar
1. Dalam pembicaraan grammar, anggota alfabet dinamakan simbol terminal atau
token.
2. Kalimat adalah deretan hingga simbol-simbol terminal.
3. Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga
kalimat.
4. Simbol-simbol berikut adalah simbol terminal :
• huruf kecil awal alfabet, misalnya : a, b, c
• simbol operator, misalnya : +, −, dan ×
• simbol tanda baca, misalnya : (, ), dan ;
• string yang tercetak tebal, misalnya : if, then, dan else.
5. Simbol-simbol berikut adalah simbol non terminal :
• huruf besar awal alfabet, misalnya : A, B, C
• huruf S sebagai simbol awal
• string yang tercetak miring, misalnya : expr dan stmt.
6. Huruf besar akhir alfabet melambangkan simbol terminal atau non terminal,
misalnya : X, Y, Z.
7. Huruf kecil akhir alfabet melambangkan string yang tersusun atas simbol-simbol
terminal, misalnya : x, y, z.
8. Huruf yunani melambangkan string yang tersusun atas simbol-simbol terminal
atau simbol-simbol non terminal atau campuran keduanya, misalnya : α, β, dan γ.
9. Sebuah produksi dilambangkan sebagai α → β, artinya : dalam sebuah derivasi
dapat dilakukan penggantian simbol α dengan simbol β.
10. Simbol α dalam produksi berbentuk α → β disebut ruas kiri produksi sedangkan
simbol β disebut ruas kanan produksi.
11. Derivasi adalah proses pembentukan sebuah kalimat atau sentensial. Sebuah
derivasi dilambangkan sebagai : α ⇒ β.
12. Sentensial adalah string yang tersusun atas simbol-simbol terminal atau simbolsimbol
non terminal atau campuran keduanya.
13. Kalimat adalah string yang tersusun atas simbol-simbol terminal. Jelaslah bahwa
kalimat adalah kasus khusus dari sentensial.
14. Pengertian terminal berasal dari kata terminate (berakhir), maksudnya derivasi
berakhir jika sentensial yang dihasilkan adalah sebuah kalimat (yang tersusun atas
simbol-simbol terminal itu).
15. Pengertian non terminal berasal dari kata not terminate (belum/tidak berakhir),
maksudnya derivasi belum/tidak berakhir jika sentensial yang dihasilkan
mengandung simbol non terminal.
Grammar dan Klasifikasi Chomsky
Grammar G didefinisikan sebagai pasangan 4 tuple : V T , V N , S, dan Q, dan
dituliskan sebagai G(V T , V N , S, Q), dimana :
VT : himpunan simbol-simbol terminal (atau himpunan token -token, atau
alfabet)
VN : himpunan simbol-simbol non terminal
S ∈ V N : simbol awal (atau simbol start)
Q : himpunan produksi
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 4
Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (α → β), Noam
Chomsky mengklasifikasikan 4 tipe grammar :
1. Grammar tipe ke-0 : Unrestricted Grammar (UG)
Ciri : α, β ∈ (V T VN )*, α> 0
2. Grammar tipe ke-1 : Context Sensitive Grammar (CSG)
Ciri : α, β ∈ (V T VN )*, 0 < α ≤ β
3. Grammar tipe ke-2 : Context Free Grammar (CFG)
Ciri : α ∈ V N , β ∈ (V T VN )*
4. Grammar tipe ke-3 : Regular Grammar (RG)
Ciri : α ∈ V N , β ∈ {V T , V T VN } atau α ∈ V N , β ∈ {V T , V N VT }
Mengingat ketentuan simbol-simbol (hal. 3 no. 4 dan 5), ciri-ciri RG sering
dituliskan sebagai : α ∈ V N , β ∈ {a, bC} atau α ∈ V N , β ∈ {a, Bc}
Tipe sebuah grammar (atau bahasa) ditentukan dengan aturan sebagai berikut :
A language is said to be type-i (i = 0, 1, 2, 3) language if it can be
specified by a type-i grammar but can’t be specified any type-(i+1)
grammar.
Contoh Analisa Penentuan Type Grammar
1. Grammar G1 dengan Q1 = {S → aB, B → bB, B → b}. Ruas kiri semua
produksinya terdiri dari sebuah V N maka G1 kemungkinan tipe CFG atau RG.
Selanjutnya karena semua ruas kanannya terdiri dari sebuah V T atau string
VT VN maka G1 adalah RG.
2. Grammar G 2 dengan Q 2 = {S → Ba, B → Bb, B → b}. Ruas kiri semua
produksinya terdiri dari sebuah V N maka G 2 kemungkinan tipe CFG atau RG.
Selanjutnya karena semua ruas kanannya terdiri dari sebuah V T atau string
VN VT maka G 2 adalah RG.
3. Grammar G3 dengan Q 3 = {S → Ba, B → bB, B → b}. Ruas kiri semua
produksinya terdiri dari sebuah V N maka G 3 kemungkinan tipe CFG atau RG.
Selanjutnya karena ruas kanannya mengandung string V T V N (yaitu bB) dan juga
string V N VT (Ba) maka G 3 bukan RG, dengan kata lain G 3 adalah CFG.
4. Grammar G 4 dengan Q 4 = {S → aAb, B → aB}. Ruas kiri semua produksinya
terdiri dari sebuah V N maka G 4 kemungkinan tipe CFG atau RG. Selanjutnya
karena ruas kanannya mengandung string yang panjangnya lebih dari 2 (yaitu
aAb) maka G 4 bukan RG, dengan kata lain G 4 adalah CFG.
5. Grammar G5 dengan Q 5 = {S → aA, S → aB, aAb → aBCb}. Ruas kirinya
mengandung string yang panjangnya lebih dari 1 (yaitu aAb) maka G5
kemungkinan tipe CSG atau UG. Selanjutnya karena semua ruas kirinya lebih
pendek atau sama dengan ruas kananya maka G 5 adalah CSG.
6. Grammar G 6 dengan Q 6 = {aS → ab, SAc → bc}. Ruas kirinya mengandung
string yang panjangnya lebih dari 1 maka G 6 kemungkinan tipe CSG atau UG.
Selanjutnya karena terdapat ruas kirinya yang lebih panjang daripada ruas
kananya (yaitu SAc) maka G 6 adalah UG.
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 5
Derivasi Kalimat dan Penentuan Bahasa
Tentukan bahasa dari masing-masing gramar berikut :
1. G1 dengan Q1 = {1. S → aAa, 2. A → aAa, 3. A → b}.
Jawab :
Derivasi kalimat terpendek : Derivasi kalimat umum :
S ⇒ aAa (1) S ⇒ aAa (1)
⇒ aba (3) ⇒ aaAaa (2)
…
⇒ a n Aa n (2)
⇒ a n ba n (3)
Dari pola kedua kalimat disimpulkan : L1(G1 ) = { a n ba n n ≥ 1}
2. G2 dengan Q 2 = {1. S → aS, 2. S → aB, 3. B → bC, 4. C → aC, 5. C → a}.
Jawab :
Derivasi kalimat terpendek : Derivasi kalimat umum :
S ⇒ aB (2) S ⇒ aS (1)
⇒ abC (3) …
⇒ aba (5) ⇒ a n-1S (1)
⇒ a nB (2)
⇒ a nbC (3)
⇒ a n baC (4)
…
⇒ a n ba m-1C (4)
⇒ a n ba m (5)
Dari pola kedua kalimat disimpulkan : L 2 (G 2 ) = { a n ba m n ≥ 1, m ≥ 1}
3. G3 dengan Q 3 = {1. S → aSBC, 2. S → abC, 3. bB → bb,
4. bC → bc, 5. CB → BC, 6. cC → cc}.
Jawab :
Derivasi kalimat terpendek 1: Derivasi kalimat terpendek 3 :
S ⇒ abC (2) S ⇒ aSBC (1)
⇒ abc (4) ⇒ aaSBCBC (1)
Derivasi kalimat terpendek 2 : ⇒ aaabCBCBC (2)
S ⇒ aSBC (1) ⇒ aaabBCCBC (5)
⇒ aabCBC (2) ⇒ aaabBCBCC (5)
⇒ aabBCC (5) ⇒ aaabBBCCC (5)
⇒ aabbCC (3) ⇒ aaabbBCCC (3)
⇒ aabbcC (4) ⇒ aaabbbCCC (3)
⇒ aabbcc (6) ⇒ aaabbbcCC (4)
⇒ aaabbbccC (6)
⇒ aaabbbccc (6)
Dari pola ketiga kalimat disimpulkan : L 3 (G 3 ) = { a n b n c n n ≥ 1}
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 6
Menentukan Grammar Sebuah Bahasa
1. Tentukan sebuah gramar regular untuk bahasa L1 = { a n n ≥ 1}
Jawab :
Q1 (L1 ) = {S → aSa}
2. Tentukan sebuah gramar bebas konteks untuk bahasa :
L 2 : himpunan bilangan bulat non negatif ganjil
Jawab :
Langkah kunci : digit terakhir bilangan harus ganjil.
Buat dua buah himpunan bilangan terpisah : genap (G) dan ganjil (J)
Q2 (L 2 ) = {S → JGSJS, G → 02468, J → 13579}
3. Tentukan sebuah gramar bebas konteks untuk bahasa :
L3 = himpunan semua identifier yang sah menurut bahasa pemrograman Pascal
dengan batasan : terdiri dari simbol huruf kecil dan angka, panjang identifier
boleh lebih dari 8 karakter
Jawab :
Langkah kunci : karakter pertama identifier harus huruf.
Buat dua buah himpunan bilangan terpisah : huruf (H) dan angka (A)
Q3 (L 3 ) = {S → HHT, T → ATHTHA, H → abc…, A → 012…}
4. Tentukan gramar bebas konteks untuk bahasa L 4 (G 4 ) = {a n b m n,m ≥ 1, n ≠ m}
Jawab :
Langkah kunci : sulit untuk mendefinisikan L 4 (G 4 ) secara langsung. Jalan
keluarnya adalah dengan mengingat bahwa x ≠ y berarti x > y atau x < y.
L 4 = L A ∪ L B , L A ={a n b m n > m ≥ 1}, L B = {a n b m 1 ≤ n < m}.
QA (L A ) = {A → aAaC, C → aCbab}, Q(L B ) = {B → BbDb, D→ aDbab}
Q4 (L 4 ) = {S→ AB, A → aAaC, C → aCbab, B → BbDb, D→ aDbab}
5. Tentukan sebuah gramar bebas konteks untuk bahasa :
L5 = bilangan bulat non negatif genap. Jika bilangan tersebut terdiri dari dua digit
atau lebih maka nol tidak boleh muncul sebagai digit pertama.
Jawab :
Langkah kunci : Digit terakhir bilangan harus genap. Digit pertama tidak boleh
nol. Buat tiga himpunan terpisah : bilangan genap tanpa nol (G), bilangan genap
dengan nol (N), serta bilangan ganjil (J).
Q5 (L 5 ) = {S → NGAJA, A → NNAJA, G→ 2468, N→ 02468,
J → 13579}
Asep Juarna, Catatan Teori Bahasa dan Atutomata, Hal 7
Mesin Pengenal Bahasa
Untuk setiap kelas bahasa Chomsky, terdapat sebuah mesin pengenal bahasa. Masing-masing
mesin tersebut adalah :
Kelas Bahasa Mesin Pengenal Bahasa
Unrestricted Grammar (UG) Mesin Turing (Turing Machine), TM
Context Sensitive Grammar (CSG) Linear Bounded Automaton, LBA
Context Free Gammar (CFG) Automata Pushdown (Pushdown Automata), PDA
Regular Grammar, RG Automata Hingga (Finite Automata), FA
Catatan :
1. Pengenal bahasa adalah salah satu kemampuan mesin turing.
2. LBA adalah variasi dari Mesin Turing Nondeterministik.
3. Yang akan dibahasa dalam kuliah Teori Bahasa dan Automata adalah : TM (sekilas), FA,
dan PDA.
III. MESIN TURING
Ilustrasi TM sebagai sebuah ‘mesin’:
Pita TM. Terbatas di kiri. Setiap sel berisi sebuah karakter dari
kalimat yang akan dikenali. Di kanan kalimat terdapat tak hingga
simbol hampa.
Head : membaca dan menulisi sel pita TM, bisa bergerak ke kiri atau ke akan
Finite State FSC : otak dari TM, diimplementasikan dari algoritma pengenalan
Control (FSC) kalimat.
Ilustrasi TM sebagai sebuah graf berarah :
1. Sebagaimana graf, TM terdiri dari beberapa node dan beberapa edge. Dari satu node
mungkin terdapat satu atau lebih edge yang menuju node lainnya atau dirinya sendiri.
2. Sebuah node menyatakan sebuah stata (state). Dua stata penting adalah stata awal S
(start) dan stata penerima H (halt). Sesaat sebelum proses pengenalan sebuah kalimat,
TM berada pada stata S. Jika kalimat tersebut dikenali maka, setelah selesai membaca
kalimat tersebut, TM akan akan berhenti pada stata H.
3. Sebuah edge mempunyai ‘bobot’ yang dinotasikan sebagai triple : (a, b, d). a adalah
karakter acuan bagi karakter dalam sel pita TM yang sedang dibaca head. Jika yang
dibaca head adalah karakter a maka a akan di-overwrite dengan karakter b dan head akan
berpindah satu sel ke arah d (kanan atau kiri).
4. Kondisi crash akan terjadi jika ditemui keadaan sebagai berikut :
j1
(a1, b1, c1)
TM sedang berada pada stata i. Jika TM sedang
(a2, b2, c2) membaca simbol ax ≠ a1 ≠ a2 ≠ … ≠ an maka
i j2 TM tidak mungkin beranjak dari stata i. Jadi
pada kasus ini penelusuran (tracing) TM ber-
(an, bn, cn) akhir pada stata i.
jn
Asep Juarna, Catatan Teori Bahasa dan Atutomata, Hal 8
Contoh :
Rancanglah sebuah mesin turing pengenal bahasa L = {a n b n | n ≥ 0).
Jawab :
L tersebut terdiri dari 2 kelompok kalimat yaitu ε dan non-ε. Kelompok non-ε adalah : ab,
aabb, aaabbb, dan seterusnya. Untuk dapat menerima kalimat ε TM harus mempunyai edge
dari S ke H dengan bobot (ε ,ε , R). TM menerima kalimat-kalimat : ab, aabb, aaabbb, dan
seterusnya, dengan algoritma sebagai berikut :
1. Mulai dari S, head membaca simbol a.
2. Head membaca simbol a. Tandai simbol a yang sudah dibaca tersebut, head bergerak ke
kanan mencari simbol b pasangannya.
3. Head membaca simbol b. Tandai simbol b yang sudah dibaca tersebut, head bergerak ke
kiri mencari simbol a baru yang belum dibaca/ditandai.
4. Ulangi langkah 2 dan 3.
5. Head sampai ke H hanya jika semua simbol a dan simbol b dalam kalimat a n b n selesai
dibaca.
Algoritma di atas lebih diperinci lagi sebagai berikut :
1. Mulai dari S, head membaca simbol a.
2. Overwrite a tersebut dengan suatu simbol (misalkan A) untuk menandakan bahwa a
tersebut sudah dibaca. Selanjutnya head harus bergerak ke kanan untuk mencari sebuah b
sebagai pasangan a yang sudah dibaca tersebut.
i) Jika yang ditemukan adalah simbol a maka a tersebut harus dilewati (tidak boleh
dioverwrite), dengan kata lain a dioverwrite dengan a juga dan head bergerak ke
kanan.
ii) Jika TM pernah membaca simbol b ada kemungkinan ditemukan simbol B. Simbol B
tersebut harus dilewati (tidak boleh dioverwrite), artinya B diover-write dengan B
juga dan head bergerak ke kanan.
3. Head membaca simbol b, maka b tersebut harus dioverwrite dengan simbol lain (misalnya
B) untuk menandakan bahwa b tersebut (sebagai pasangan dari a) telah dibaca, dan head
bergerak ke kiri untuk mencari simbol A.
i) Jika ditemukan B maka B tersebut harus dilewati (tidak boleh dioverwrite), dengan
kata lain B dioverwrite dengan B juga dan head bergerak ke kiri.
ii) Jika ditemukan a maka a tersebut harus dilewati (tidak boleh dioverwrite), dengan
kata lain a dioverwrite dengan a juga dan head bergerak ke kiri.
4. Head membaca simbol A, maka A tersebut harus dilewati (tidak boleh dioverwrite),
dengan kata lain A dioverwrite dengan A juga dan head bergerak ke kanan.
5. Head membaca simbol a, ulangi langkah 2 dan 3.
6. (Setelah langkah 3) head membaca simbol A, maka A tersebut harus dilewati (tidak boleh
dioverwrite), dengan kata lain A dioverwrite dengan A juga dan head bergerak ke kanan.
7. Head membaca simbol B, maka B tersebut harus dilewati (tidak boleh dioverwrite),
dengan kata lain B dioverwrite dengan A juga dan head bergerak ke kanan.
8. Head membaca simbol ε, maka ε dioverwrite dengan ε dan head bergerak ke kanan
menuju stata H.
Asep Juarna, Catatan Teori Bahasa dan Atutomata, Hal 9
Skema graf Mesin Turing di atas adalah :
(ε, ε, R)
(B, B, R) (B, B, L) (B, B, R)
(a, A, R) (b, B, L) (A, A, R) (ε, ε, R)
S 1 2 4 H
(a, a, R)
(a, a, L)
(A, A, R)
3
(a, a, L)
Contoh :
Lakukan tracing dengan mesin turing di atas untuk kalimat-kalimat : aabb, aab.
Jawab :
i) (S,aabb) ⇒ (1,Aabb) ⇒ (1,Aabb) ⇒ (2,AaBb) ⇒ (3,AaBb) ⇒ (S,AaBb)
⇒ (1,AABb) ⇒ (1,AABb) ⇒ (2,AABB) ⇒ (2,AABB) ⇒ (4,AABB)
⇒ (4,AABB) ⇒ (4,AABBε) ⇒ (H,AABBεε)
ii) (S,aab) ⇒ (1,Aab) ⇒ (1,Aab) ⇒ (2,AaB) ⇒ (3,AaB) ⇒ (S,AaB) ⇒ (1,AAB)
⇒ (1,AAbε) ⇒ crash, karena dari node 1 tidak ada edge dengan bobot
komponen pertamanya hampa (ε)
IV. AUTOMATA HINGGA (AH)
• AH didefinisikan sebagai pasangan 5 tupel : (K, V T , M, S, Z).
K : himpunan hingga stata,
VT : himpunan hingga simbol input (alfabet)
M : fungsi transisi, menggambarkan transisi stata AH akibat pembacaan simbol
input.
Fungsi transisi ini biasanya diberikan dalam bentuk tabel.
S ∈ K : stata awal
Z ⊂ K : himpunan stata penerima
• Ada dua jenis automata hingga : deterministik (AHD, DFA = deterministic finite
automata) dan non deterministik (AHN, NFA = non deterministik finite automata).
- AHD : transisi stata AH akibat pembacaan sebuah simbol bersifat tertentu.
M(AHD) : K × V T → K
- AHN : transisi stata AH akibat pembacaan sebuah simbol bersifat tak tentu.
M(AHN) : K × VT → 2K
Asep Juarna, Catatan Teori Bahasa dan Atutomata, Hal 10
IV. 1. Automata Hingga Deterministik (AHD)
Berikut ini sebuah contoh AHD F(K, V T , M, S, Z), dimana :
K = {q0, q1, q2} M diberikan dalam tabel berikut :
VT = {a, b} a b
S = q0 q0 q0 q1
Z = {q0, q1} q1 q0 q2
q2 q2 q2
Ilustrasi graf untuk AHD F adalah sebagai berikut :
Lambang stata awal adalah node dengan anak panah.
Lambang stata awal adalah node ganda.
a b a
q0 q1 q2 b
a b
Contoh kalimat yang diterima AHD : a, b, aa, ab, ba, aba, bab, abab, baba
Contoh kalimat yang tidak diterima AHD : bb, abb, abba
AHD ini menerima semua kalimat yang tersusun dari simbol a dan b yang tidak mengandung
substring bb.
Contoh :
Telusurilah, apakah kalimat-kalimat berikut diterima AHD :
abababaa, aaaabab, aaabbaba
Jawab :
i) M(q0,abababaa) ⇒ M(q0,bababaa) ⇒ M(q1,ababaa) ⇒ M(q0,babaa)
⇒ M(q1,abaa) ⇒ M(q0,baa) ⇒ M(q1,aa) ⇒ M(q0,a) ⇒ q0
Tracing berakhir di q0 (stata penerima) ⇒ kalimat abababaa diterima
ii) M(q0, aaaabab) a M(q0,aaabab) a M(q0,aabab) a M(q0,abab)
⇒ M(q0,bab) ⇒ M(q1,ab) ⇒ M(q0,b) a q1
Tracing berakhir di q1 (stata penerima) ⇒ kalimat aaaababa diterima
iii) M(q0, aaabbaba) ⇒ M(q0, aabbaba) ⇒ M(q0, abbaba) ⇒ M(q0, bbaba)
⇒ M(q1,bbaba) ⇒ M(q2,baba) ⇒ M(q2,aba) ⇒ M(q2,ba) ⇒ M(q2,a) a q2
Tracing berakhir di q2 (bukan stata penerima) ⇒ kalimat aaabbaba ditolak
Kesimpulan : sebuah kalimat diterima oleh AHD jika tracingnya berakhir di salah satu stata
penerima.
Asep Juarna : Catatan Teori Bahasa dan Automata, hal 11
IV.2. Equivalensi 2 AHD
Dua buah AHD dikatakan equivalen jika keduanya dapat menerima bahasa yang
sama. Misalkan kedua AHD tersebut adalah A dan A’. Misalkan pula bahasa yang
diterima adalah bahasa L yang dibangun oleh alfabet V T = {a1, a2, a3, ..., an}.
Berikut ini algoritma untuk menguji equivalensi dua buah AHD.
1. Berikan nama kepada semua stata masing-masing AHD dengan nama berbeda.
Misalkan nama-nama tersebut adalah : S, A1, A2, ... untuk AHD A, dan : S’, A1’,
A2’, ... untuk AHD A’.
2. Buat tabel (n+1) kolom, yaitu kolom-kolom : (v, v’), (v a 1 , v a 1 ’), ..., (v a n ,
v a n ’), yaitu pasangan terurut (stata AHD A, stata AHD A’).
3. Isikan (S, S’) pada baris pertama kolom (v, v’), dimana S dan S’ masing-masing
adalah stata awal masing-masing AHD.
4. Jika terdapat edge dari S ke A1 dengan label a1 dan jika terdapat edge dari S’ ke
A1’ juga dengan label a1, isikan pasangan terurut (A1, A1’) sebagai pada baris
pertama kolom (v a 1 , v a 1 ’). Lakukan hal yang sama untuk kolom-kolom
berikutnya.
5. Perhatikan nilai-nilai pasangan terurut pada baris pertama. Jika terdapat nilai
pasangan terurut pada kolom (v a 1 , v a 1 ’) s/d (v a n , v a n ’) yang tidak sama
dengan nilai pasangan terurut (v, v’), tempatkan nilai tersebut pada kolom (v, v’)
baris-baris berikutnya. Lakukan hal yang sama seperti yang dilakukan pada
langkah (4). Lanjutkan dengan langkah (5).
6. Jika selama proses di atas dihasilkan sebuah nilai pada kolom (v, v’), dengan
komponen v merupakan stata penerima sedangkan komponen v’ bukan, atau
sebaliknya, maka kedua AHD tersebut tidak ekuivalen. Proses dihentikan.
7. Jika kondisi (6) tidak dipenuhi dan jika tidak ada lagi pasangan terurut baru yang
harus ditempatkan pada kolom (v, v’) maka proses dihentikan dan kedua AHD
tersebut ekuivalen.
Contoh :
Periksalah ekuivalensi kedua AHD berikut :
a
b
1 a 4 5
a
b a b a
a a
2 3 b 7 6 b
a a
AHD A AHD A’
Jawab :
Dengan menggunakan menggunakan algoritma di atas maka dapat dibentuk tabel
berikut :
(v, v’) (v a , v a ’) (v b , v b ’) Keterangan :
(1, 4) (1, 4) (2, 5) (2, 5) adalah pasangan terurut baru
(2,5) (3, 6) (1, 4) (3, 6) adalah pasangan terurut baru
(3, 6) (2, 7) (3, 6) (2, 7) adalah pasangan terurut baru
(2, 7) (3, 6) (1, 4) tidak adal lagi pasangan terurut baru
Asep Juarna : Catatan Teori Bahasa dan Automata, hal 12
IV. 3. Mesin Stata Hingga (MSH)
• MSH atau FSM (Finite State Machine) adalah sebuah varians automata hingga.
MSH sering juga disebut sebagai automata hingga beroutput atau mesin
sekuensial.
• MSH didefinisikan sebagai pasangan 6 tupel F(K, V T , S, Z, f, g) dimana :
K : himpunan hingga stata,
VT : himpunan hingga simbol input (alfabet)
S ∈ K : stata awal
Z : himpunan hingga simbol output
f : K × V T → K disebut fungsi next state
g : K × V T → Z disebut fungsi output
Contoh :
Berikut ini adalah contoh MSH dengan 2 simbol input, 3 stata, dan 3 simbol output :
K = {q0, q1, q2} fungsi f : fungsi g :
S = q0 f(q0,a) = q1 f(q0,b) = q2 f(q0,a) = x f(q0,b) = y
VT = {a, b} f(q1,a) = q2 f(q1,b) = q1 f(q1,a) = x f(q1,b) = z
Z = {x, y, z} f(q2,a) = q0 f(q2,b) = q1 f(q2,a) = z f(q2,b) = y
MSH dapat disajikan dalam bentuk tabel atau graf. Untuk MSH contoh di atas tabel
dan grafnya masing-masing adalah :
a x b z
a b q0 q1
q0 q1, x q2, y b x y a
q1 q2, x q1, z a b
q2 q0, z q1, y q2
y x
Jika MSH di atas mendapat untai masukan “aaba” maka akan dihasilkan :
- untai keluaran : xxyx
- untai stata : q0 q1 q2 q1 q2
IV. 4. MSH penjumlah biner
MSH dapat disajikan sebagai penjumlah biner. Sifat penjumlahan biner bergantung
pada statusnya : carry atau not carry.
Pada status not carry berlaku : 0 + 0 = 0, 1 + 0 = 0 + 1 = 1, 1 + 1 = 0
Pada status carry berlaku : 0 + 0 = 1, 1 + 0 = 0 + 1 = 0, 1 + 1 = 1
Pada status not carry blank (b) menjadi b, sedangkan pada status carry menjadi 1.
Nilai setiap tupel untuk MSH ini adalah :
K = N (not carry), C (carry), dan S (stop) Tabel MSH
S = N 00 01 10 11 b
VT = {00, 01, 10, 11, b} N N, 0 N, 1 N, 1 C, 0 S, b
Z = {0, 1, b} C N, 1 C, 0 C, 0 C, 1 S, 1
Asep Juarna : Catatan Teori Bahasa dan Automata, hal 13
Graf MSH penjumlah biner :
00 0 1 00 01 0
1 10
N 11 0 C
01 0
1 10 1 11
b b
b 1
S
Contoh :
Hitunglah : 1101011 + 0111011
Jawab :
Input = pasangan digit kedua bilangan, mulai dari LSB (least significant bit)
= 11, 11, 00, 11, 01, 11, 11, b
Output = 0, 1, 1, 0, 0, 1, 1, 1 (jawab : dibaca dari kanan)
Stata = N, C, C, N, C, C, C, C, S
Periksa : 1 1 0 1 0 1 1
0 1 1 1 0 1 1 +
1 1 1 0 0 1 1 0
IV. 5. Ekspresi Regular
• Bahasa regular dapat dinyatakan sebagai ekspresi regular dengan menggunakan 3
operator : concate, alternate, dan closure.
• Dua buah ekspresi regular adalah ekuivalen jika keduanya menyatakan bahasa
yang sama
Contoh :
L1 = {a n ba m n ≥ 1, m ≥ 1} ⇔ er 1 = a + b a +
L 2 = {a n ba m n ≥ 0, m ≥ 0} ⇔ er 2 = a* b a*
Perhatikan bahwa kita tidak bisa membuat ekspresi regular dari bahasa
L3 = {a n ba n n ≥ 1} atau L 4 = {a n ba n n ≥ 0}, karena keduanya tidak dihasilkan
dari grammar regular.
Kesamaan 2 ekspresi regular :
(a b)* a = a (b a)*
Bukti :
(a b)* a = (ε(ab)(abab)…) a = (ε a(aba)(ababa)…) = (a(aba)(ababa)…)
= a (ε(ba)(baba)…) = a (b a)*
Latihan 2. Buktikan kesamaan ekspresi regular berikut :
1. (a*b)* = (ab)*
2. (ab*)* = (ab)*
3. (a* b)* a* = a* (b a*)*
4. (a a*)(εa) = a*
5. a(b aa)* b = a a* b(a a* b)*
Asep Juarna : Catatan Teori Bahasa dan Automata, hal 10
IV. 6. Automata Hingga Nondeterministik (AHN)
Berikut ini sebuah contoh AHN F(K, V T , M, S, Z), dimana :
K = {q 0 , q1, q 2 ,q 3 , q 4 } M diberikan dalam tabel berikut :
VT = {a, b,c} a b c
S = q 0 q0 {q 0 , q1} {q 0 , q 2 } {q 0 , q 3 }
Z = {q 4 } q1 {q1, q 4} {q1} {q1}
q 2 {q2} {q 2 , q 4} {q2 }
q 3 {q3} {q 3} {q3 , q 4 }
q 4 ∅ ∅ ∅
Ilustrasi graf untuk AHN F adalah sebagai berikut :
a, b, c a, b, c
a
q0 q1
c b a
b
q3 q2 q4
a, b, c a, b, c
c
Contoh kalimat yang diterima AHN di atas : aa, bb, cc, aaa, abb, bcc, cbb
Contoh kalimat yang tidak diterima AHN di atas : a, b, c, ab, ba, ac, bc
Fungsi transisi M sebuah AHN dapat diperluas sebagai berikut :
1. M(q, ε) = {q} untuk setiap q ∈ K
2. M(q, t T) = ∪ M(p i , T) dimana t ∈ V T , T adalah V T *, dan M(q, t) = {p i }
3. M({q1, q 2 , …, q n }, x) = ∪ M(q i ,x), untuk x ∈ V T *
Sebuah kalimat di terima AHN jika :
• salah satu tracing-nya berakhir di stata penerima, atau
• himpunan stata setelah membaca string tersebut mengandung stata penerima
Asep Juarna : Catatan Teori Bahasa dan Automata, hal 11
Contoh :
Telusurilah, apakah kalimat-kalimat berikut diterima AHN : ab, abc, aabc, aabb
Jawab :
i) M(q0 ,ab) ⇒ M(q 0 ,b) ∪ M(q1 ,b) ⇒ {q 0 , q 2 } ∪ {q1} = {q 0 , q1, q 2 }
Himpunan stata tidak mengandung stata penerima ⇒ kalimat ab tidak diterima
ii) M(q0 ,abc) ⇒ M(q 0 ,bc) ∪ M(q1 ,bc) ⇒ {M(q 0 ,c) ∪ M(q 2 ,c)} ∪ M(q1, c)
⇒ {{ q 0 , q 3}∪{ q 2 }}∪{ q1} = {q 0 , q1, q 2 ,q 3 }
Himpunan stata tidak mengandung stata penerima ⇒ kalimat abc tidak diterima
iii) M(q0 ,aabc) ⇒ M(q 0 ,abc) ∪ M(q1 ,abc) ⇒ {M(q 0 ,bc) ∪ M(q1 ,bc)} ∪ M(q1 ,bc)
⇒ {{M(q 0 , c) ∪ M(q 2 ,c)} ∪ M(q1, c)} ∪ M(q1, c)
⇒ {{{ q 0 , q 3}∪ { q 2 }} ∪ {q1}} ∪ {q1} = {q 0 , q1, q 2 ,q 3 }
Himpunan stata tidak mengandung stata penerima ⇒ kalimat aabc tidak diterima
iv) M(q0 ,aabb) ⇒ M(q 0 ,abb) ∪ M(q1 ,abb) ⇒ {M(q 0 ,bb) ∪ M(q1 ,bb)} ∪ M(q1 ,bb)
⇒ {{M(q 0 , b) ∪ M(q 2 ,b)} ∪ M(q1, b)} ∪ M(q1, b)
⇒ {{{ q 0 , q 2 }∪ { q 2 , q 4 }} ∪ {q1}} ∪ {q1} = {q 0 , q1, q 2 , q 4 }
Himpunan stata tidak mengandung stata penerima ⇒ kalimat aabb diterima
AHN Dengan Transisi Hampa
Perhatikan AHN berikut.
1 0
ε
q 0 q1
AHN di atas mengandung ruas dengan bobot ε. AHN demikian dinamakan AHN dengan
transisi ε, atau singkatnya AHN-ε. AHN-ε di atas menerima bahasa L = {1 i 0 j i , j ≥ 0}
IV. 7. Ekuivalensi AHN, AHD, dan GR
AHD bisa dibentuk dari AHN. AHN
GR bisa dibentuk dari AHD.
AHN bisa dibentuk dari GR. AHD GR
Pembentukan AHD dari AHN
Diberikan sebuah AHN F = (K, VT , M, S, Z). Akan dibentuk sebuah AHD F’ = (K’,
VT ’, M’, S’, Z’) dari AHN F tersebut. Algoritma pembentukannya adalah sbb. :
1. Tetapkan : S’ = S dan VT ’ = V T
2. Copykan tabel AHN F sebagai tabel AHD F’. Mula-mula K’ = K dan M’ = M
3. Setiap stata q yang merupakan nilai (atau peta) dari fungsi M dan q ∉ K, ditetapkan
sebagai elemen baru dari K’. Tempatkan q tersebut pada kolom Stata M’, lakukan
pemetaan berdasarkan fungsi M.
4. Ulangi langkah (3) sampai tidak diperoleh stata baru.
5. Elemen Z’ adalah semua stata yang mengandung stata elemen Z.
Asep Juarna : Catatan Teori Bahasa dan Automata, hal 12
Contoh :
Berikut ini diberikan sebuah AHN F = (K, VT , M, S, Z) dengan :
K = {A, B, C}, V T = {a, b}, S = A, Z = {C}, dan M didefinisikan sebagai berikut :
Stata K Input
AHN F a b
A [A,B] C
B A B
C B [A,B]
Tentukan AHD hasil transformasinya.
Jawab :
Berdasarkan algoritma di atas, maka :
1. S’ = S = A, V T ’ = VT = {a, b}.
2. Hasil copy tabel AHN F menghasilkan tabel AHD F’ berikut :
Stata K’ Input
AHD F’ a b
A [A,B] C
B A B
C B [A,B]
3. Pada tabel AHD F’ di atas terdapat stata baru yaitu [A,B]. Pemetaan [A,B] adalah :
M([A,B],a) = M(A,a) ∪ M(B,a) = [A,B] ∪ A = [A,B], dan
M([A,B],b) = M(A,b) ∪ M(B,b) = C ∪ B = [B,C], sehingga diperoleh tabel berikut :
Stata K’ Input
dari AHD F’ a b
A [A,B] C
B A B
C B [A,B]
[A,B] [A,B] [B,C]
4. Langkah (3) di atas menghasilkan stata baru yaitu [B,C]. Setelah pemetaan terhadap
[B,C] diperoleh tabel berikut :
Stata K’ Input
dari AHD F’ a b
A [A,B] C
B A B
C B [A,B]
[A,B] [A,B] [B,C]
[B,C] [A,B] [A,B]
5. Setelah langkah (4) di atas tidak terdapat lagi stata baru.
Dengan demikian AHD F’ yang dihasilkan adalah : AHD F’ = (K’, VT ’, M’, S’, Z’),
dimana : K’ = {A, B, C, [A,B], [B,C]}, V T ’ = {a, b}, S’ = A, Z’ = {C, [B,C]}. Fungsi
transisi M’ serta graf dari AHD F’ adalah sebagai berikut :
Asep Juarna : Catatan Teori Bahasa dan Automata, hal 13
B b
Stata K’ Input a
dari AHD F’ a b A a
A [A,B] C a b C
B A B
C B [A,B] b
[A,B] [A,B] [B,C] [A,B] b [B,C]
[B,C] [A,B] [A,B] a, b
a
Pembentukan GR dari AHD
Diketahui sebuah AHD F = (K, V T , M, S, Z). Akan dibentuk GR G = (V T ’,V N , S’, Q).
Algoritma pembentukan GR dari AHD adalah sebagai berikut :
1. Tetapkan V T ’ = VT , S’ = S, VN = S
2. Jika A p , A q ∈ K dan a ∈ V T , maka :
M(A p , a) = A q ekuivalen dengan produksi :
A aA jika A Z
A a jika A Z
p q q
p q
→ ∉
→ ∈
,
,
Contoh
Diketahui sebuah AHD F dengan Z = {S} dan fungsi transisi M sebagai berikut :
Stata K Input Dengan algoritma di atas maka diperoleh Q(GR) sbb. :
AHD F 0 1 M(S,0) = B ⇔ S → 0B M(S,1) = A⇔ S → 1A
S B A M(A,0) = C ⇔ A → 0C M(A,1) = S⇔ A → 1
A C S M(B,0) = S ⇔ B → 0 M(B,1) = C⇔ B→ 1C
B S C M(C,0) = A ⇔ C → 0A M(C,1) = B⇔ C → 1B
C A B
GR yang dihasilkan adalah G(V T ’,V N , S’, Q), dengan V T ’ = {0,1}, V N = {S, A, B, C},
S’ = S, dan Q = {S → 0B, S → 1A, A → 0C, B→ 1C, C → 0A, C → 1B, A → 1, B → 0}
Pembentukan AHN dari GR
Diketahui GR G = (V T ,V N , S, Q). Akan dibentuk AHN F = (K,VT ’, M, S’, Z).
Algoritma pembentukan AHN dari GR :
1. Tetapkan V T ’ = VT , S’ = S, K = V N
2. Produksi A p → a A q ekuivalen dengan M(A p , a) = A q
Produksi Ap → a ekuivalen dengan M(A p , a) = X, dimana X ∉ V N
3. K = K ∪ {X}
4. Z = {X}
Asep Juarna : Catatan Teori Bahasa dan Automata, hal 14
Contoh
Diketahui GR G = (V T ,V N , S, Q) dengan : VT = {a, b}, V N = {S, A, B}, S = S, dan
Q = {S → aS, S → bA, A → aA, A → aB, B → b}
Terapkan algoritma di atas untuk memperoleh AHN F sebagai berikut :
1. V T ’ = V T = {a, b}, S’ = S, K = VN = {S, A, B} Tabel M :
2. S → aS ⇔ M(S,a) = S, S → bA ⇔ M(S,b) = A, Stata K Input
A → aA ⇔ M(A,a) = A, A → aB ⇔ M(A,a) = B, AHN F a b
B → b ⇔ M(B,b) = X S S A
AHN yang diperoleh : F(K,V T ’, M, S’, Z), dengan A [A,B] φ
K = {S, A, B, X}, V T ’ = {a, b}, S’ = S, Z = {X}, B φ X
X φ φ
IV.8. Ekuivalensi Ahn-ε Dengan ER (Ekspresi Regular)
Jenis ER Simbol ER AHN
Simbol hampa
ε
q 0
ER hampa
φ atau {}
q 0 q 1
ER umum
r
r
q 0 q 1
Alternation
r 1 | r 2
ε r 1 ε
q 0 ε ε q 1
r 2
Concatenation
r 1 r 2
ε ε ε
q 0 r 1 r 2 q 1
Kleene Clossure
r *
ε
ε ε
q 0 r q 1
ε
Asep Juarna : Catatan Teori Bahasa dan Automata, hal 15
Contoh :
Tentukan AHN untuk ekspresi regular r = 0(1 | 23)*
Jawab :
0
r1 = 0 ⇔ q 0 q1
1
r 2 = 1 ⇔ q 3 q4
2 3
r 3 = 23 ⇔ q 5 q6
q7
1
q3
q4
ε ε
r 4 = r 2 | r 3 = 1| 23 ⇔ q 2 q8
ε ε
2 3
q5
q6
q7
ε
1
q3
q4
ε ε ε ε
r 5 = r 4 * = (1| 23)* ⇔ q1 q2 q 8 q9
ε 2 3 ε
q5 q6 q7
ε
1
q3
q4
0 ε ε ε ε
r = r 5 = 0(1| 23)* ⇔ q 0 q1 q2 q 8 q9
ε 2 3 ε
q5 q6 q7
V. GRAMMAR CONTEXT-FREE DAN PARSING
Bentuk umum produksi CFG adalah : α → β, α ∈ V N , β ∈ (V N VT )*
Analisis sintaks adalah penelusuran sebuah kalimat (atau sentensial) sampai pada simbol
awal grammar. Analisis sintaks dapat dilakukan melalui derivasi atau parsing.
Penelusuran melalui parsing menghasilkan pohon sintaks.
Contoh 1 :
Diketahui grammar G 1 = {I → HI HIA, H → abc...z, A → 012...9}
dengan I adalah simbol awal. Berikut ini kedua cara analisa sintaks untuk kalimat x23b.
cara 1 (derivasi) cara 2 (parsing)
I ⇒ IH I
⇒ IAH
⇒ IAAH I H
⇒ HAAH
⇒ xAAH I A b
⇒ x2AH
⇒ x23H I A 3
⇒ x23b
H 2
x
Sebuah kalimat dapat saja mempunyai lebih dari satu pohon.
Contoh 2 :
Diketahui grammar G 2 = {S → SOSA , O → *+, A → 012...9}
Kalimat : 2*3+7 mempunyai dua pohon sintaks berikut :
S S
S O S S O S
A * S O S S O S + A
2 A + A A * A 7
3 7 2 3
Sebuah kalimat yang mempunyai lebih dari satu pohon sintaks disebut kalimat ambigu
(ambiguous). Grammar yang menghasilkan paling sedikit sebuah kalimat ambigu disebut
grammar ambigu.
5.1. Metoda Parsing
Ada 2 metoda parsing : top-down dan bottom-up.
Parsing top-down : Diberikan kalimat x sebagai input. Parsing dimulai dari simbol awal
S sampai kalimat x nyata (atau tidak nyata jika kalimat x memang
tidak bisa diturunkan dari S) dari pembacaan semua leaf dari pohon
parsing jika dibaca dari kiri ke kanan.
Parsing bottom-up : Diberikan kalimat x sebagai input. Parsing dimulai dari kalimat x
yang nyata dari pembacaan semua leaf pohon parsing dari kiri ke
kanan sampai tiba di simbol awal S (atau tidak sampai di S jika
kalimat x memang tidak bisa diturunkan dari S)
Parsing Top-down
Ada 2 kelas metoda parsing top-down, yaitu kelas metoda dengan backup dan kelas
metoda tanpa backup. Contoh metoda kelas dengan backup adalah metoda Brute-Force,
sedangkan contoh metoda kelas tanpa backup adalah metoda recursive descent.
Metoda Brute-Force
Kelas metoda dengan backup, termasuk metoda Brute-Force, adalah kelas metoda
parsing yang menggunakan produksi alternatif, jika ada, ketika hasil penggunaan sebuah
produksi tidak sesuai dengan simbol input. Penggunaan produksi sesuai dengan nomor
urut produksi.
Contoh 3 :
Diberikan grammar G = {S → aAdaB, A → bc, B → ccdddc}. Gunakan metoda
Brute-Force untuk melakukan analisis sintaks terhadap kalimat x = accd.
S
Hasil :
Input : Sisa : accd
Penjelasan : Gunakan produksi
S pertama. Masukkan simbol
terkiri kalimat sebagai
input.
S
a A d
Hasil : a
Input : a Sisa : ccd
Penjelasan : Hasil = Input.
Gunakan produksi A pertama.
S
a A d
b
Hasil : ab
Input : ac Sisa : cd
Penjelasan : Hasil ≠ Input.
Backup : Gunakan produksi A
alternatif pertama.
S
a A d
c
Hasil : ac
Input : ac Sisa : cd
Penjelasan : Hasil = Input.
Karakter berikutnya adalah
simbol terminal, Hasil
dibandingkan dengan Input.
S
a A d
c
Hasil : acd
Input : acc Sisa : c
Penjelasan : Hasil ≠ Input.
Tidak ada lagi produksi A
alternatif, backup : gunakan
produksi S alternatif pertama.
S
a B
Hasil : a
Input : a Sisa : ccd
Penjelasan : Hasil = Input.
Gunakan produksi B pertama.
S
a B
c c d
Hasil : ac
Input : ac Sisa : cd
Penjelasan : Hasil = Input.
Karakter berikutnya adalah
simbol terminal, Hasil
dibandingkan dengan Input.
S
a B
c c d
Hasil : acc
Input : acc Sisa : d
Penjelasan : Hasil = Input.
Karakter berikutnya adalah
simbol terminal, Hasil
dibandingkan dengan Input.
S
a B
c c d
Hasil : accd
Input : accd Sisa :
Penjelasan : Hasil = Input.
SELESAI, SUKSES
Metoda Brute-Force tidak dapat menggunakan grammar rekursi kiri, yaitu grammar yang
mengandung produksi rekursi kiri (left recursion) : A → A∝. Produksi rekursi kiri akan
menyebabkan parsing mengalami looping tak hingga.
Contoh 4 :
Diberikan grammar G = {S → aAc, A → Abε}. Gunakan metoda Brute-Force untuk
melakukan analisis sintaks terhadap kalimat x = ac.
S
Hasil :
Input : Sisa : ac
Penjelasan : Masukkan simbol
terkiri kalimat sebagai input.
Gunakan produksi S pertama.
S
a A c
Hasil : a
Input : a Sisa : c
Penjelasan : Hasil = Input.
Gunakan produksi A pertama.
S
a A c
A b
Hasil : a
Input : a Sisa : c
Penjelasan : Hasil = Input.
Gunakan produksi A pertama.
S
a A c
A b
A b
Hasil : a
Input : a Sisa : c
Penjelasan : Hasil = Input.
Gunakan produksi A pertama.
S
a A
A b
A b
A b
Hasil : a
Input : a Sisa : c
Penjelasan : Hasil = Input.
Gunakan produksi A pertama.
dan seterusnya...... (looping)
Agar tidak menghasilkan looping tak hingga, grammar rekursi kiri harus ditransformasi.
Untuk contoh di atas transformasi berarti merubah produksi A → Ab menjadi A → bA.
Metoda Recursive-Descent
• Kelas metoda tanpa backup, termasuk metoda recursive descent, adalah kelas metoda
parsing yang tidak menggunakan produksi alternatif ketika hasil akibat penggunaan
sebuah produksi tidak sesuai dengan simbol input. Jika produksi A mempunyai dua
buah ruas kanan atau lebih maka produksi yang dipilih untuk digunakan adalah
produksi dengan simbol pertama ruas kanannya sama dengan input yang sedang
dibaca. Jika tidak ada produksi yang demikian maka dikatakan bahwa parsing tidak
dapat dilakukan.
• Ketentuan produksi yang digunakan metoda recursive descent adalah : Jika terdapat
dua atau lebih produksi dengan ruas kiri yang sama maka karakter pertama dari
semua ruas kanan produksi tersebut tidak boleh sama. Ketentuan ini tidak melarang
adanya produksi yang bersifat rekursi kiri.
Contoh 5 :
Diketahui grammar G = {S → aBA, A → a, B → bd}. Gunakan metoda recursive
descent untuk melakukan analisis sintaks terhadap kalimat x = ac.
S
Hasil :
Input : Sisa : ab
Penjelasan : Masukkan simbol
terkiri kalimat sebagai input.
Gunakan produksi S dengan
simbol pertama ruas kanan = a
S
a B
Hasil : a
Input : a Sisa : c
Penjelasan : Hasil = Input.
Gunakan produksi B dengan
simbol pertama ruas kanan =
c. Karena produksi demikian
maka parsing gagal dilakukan.
SELESAI,
PARSING GAGAL
Parsing Bottom-Up
Salah satu contoh menarik dari parsing bottom-up adalah parsing pada grammar preseden
sederhana (GPS). Sebelum sampai ke parsing tersebut, akan dikemukakan beberapa
pengertian dasar serta relasi yang ada pada GPS.
Pengertian Dasar
• Jika α dan x keduanya diderivasi dari simbol awal grammar tertentu, maka α disebut
sentensial jika α ∈ (V T V N )*, dan x disebut kalimat jika x ∈ (V T )*
• Misalkan α = Q 1 β Q 2 adalah sentensial dan A ∈ V N :
- β adalah frase dari sentensial α jika : S ⇒ … ⇒ Q 1 A Q 2 dan A⇒ … ⇒ β
- β adalah simple frase dari sentensial α jika : S ⇒ … ⇒ Q 1 A Q 2 dan A⇒ β
- Simple frase terkiri dinamakan handel
- frase, simple frase, dan handel adalah string dengan panjang 0 atau lebih..
Contoh 6 :
(1) I ⇒ I H Hb adalah sentensial dan b adalah simple frase
⇒ H H (dibandingkan dengan Q1 β Q 2 maka Q1 = H, β = b, dan Q2 = ε)
⇒ H b Perhatikan : simple frase (b) adalah yang terakhir diturunkan
(2) I ⇒ I H Hb adalah sentensial dan H adalah simple frase
⇒ I b (dibandingkan dengan Q 1 β Q 2 maka Q1 = ε, β = H, dan Q 2 = b)
⇒ H b Perhatikan : simple frase (H) adalah yang terakhir diturunkan
Sentensial Hb mempunyai dua simple frase (b dan H), sedangkan handelnya adalah H.
Relasi Preseden dan Grammar Preseden Sederhana
• Relasi preseden adalah relasi antara 2 simbol grammar (baik V T maupun V N )
dimana paling tidak salah satu simbol tersebut adalah komponen handel.
• Misalkan S dan R adalah 2 simbol. Ada 3 relasi preseden yang : ←, ↔, dan →
U U U
…………… R S ……R S…… R S……………
handel handel handel
Relasi : R → S Relasi : R ↔ S Relasi : R ← S
Perhatikan : komponen handel selalu ‘menunjuk’ yang simbol lainnya.
Contoh 7 :
Diketahui grammar dengan G = {Z → bMb, M → (L a, L → Ma)}. Dari 3 sentensial :
bab, b(Lb, b(Ma)b, tentukan handel dan relasi yang ada.
bab b(Lb b(Ma)b
Z Z Z
b M b b M b b M b
a ( L ( L
Handel : a Handel : (L
Relasi : b ← a, a → b Relasi : b ← (, (↔ L, M a )
L → b Handel : Ma)
Relasi : (←M, M ↔ a,
a ↔), ) → b
• Secara umum : jika A → aBc adalah sebuah produksi maka :
- aBc adalah handel dari sentensial yang mengandung string “aBc”
- relasi preseden antara a, B, dan c adalah : a ↔ B, B ↔ c
• Dengan memperhatikan ruas kanan produksi yang ada serta berbagai sentensial yang
dapat diderivasi dari Z maka semua relasi preseden tercantum dalam tabel berikut :
Z b M L a ( )
Z
b ↔ ← ←
M ↔ ↔
L → →
a → → ← ↔
( ← ↔ ← ←
) →
Grammar G disebut grammar preseden sederhana jika :
1. paling banyak terdapat satu relasi antara setiap dua simbolnya
2. tidak terdapat dua produksi produksi dengan ruas kanan yang sama
Parsing Grammar Preseden Sederhana
Prosedur parsing :
1. Buat tabel 3 kolom dengan label : sentensial dan relasi, handel, dan ruas kiri produksi.
2. Tuliskan kalimat (atau sentensial) yang diselidiki pada baris pertama kolom pertama.
3. Dengan menggunakan tabel relasi preseden cantumkan relasi preseden antara setiap
dua simbol yang bertetangga.
4. Tentukan handel dari sentensial tersebut. Handel adalah string yang dibatasi “←“
terakhir dan “→ “ pertama jika dilakukan penelusuran dari kiri atau yang saling
mempunyai relasi “↔“. Handel tersebut pastilah merupakan ruas kanan produksi,
karena itu tentukan ruas kiri dari handel tersebut.
5. Ganti handel dengan ruas kiri produksinya. GOTO 3.
6. Kalimat yang diselidiki adalah benar dapat diderivasi dari simbol awal jika kolom
“ruas kiri produksi” menghasilkan simbol awal.
Contoh 8 :
Lakukan parsing atas kalimat x = b(aa)b berdasarkan grammar G di atas.
sentensial dan relasi handel ruas kiri produksi
b ← (← a → a ↔)→ b a M
b ← (← M ↔ a ↔)→ b Ma) L
b ← (↔ L→ b (L M
b ↔ M ↔ b bMb Z
Prosedur parsing sampai di simbol awal (Z). Maka kalimat “b(aa)b” memang dapat
diderivasi dari simbol awal Z dengan menggunakan grammar G.
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 26
5.2. Bentuk Normal Chomsky
• Bentuk normal Chomsky (Chomsky Normal Form, CNF) adalah grammar bebas
konteks (CFG) dengan setiap produksinya berbentuk : A → BC atau A → a.
• Transformasi CFG ke CNF adalah trnasformasi berikut :
A → α , dimana : A → BC, atau
α ∈ (VNVT )* A → a
• 4 langkah konversi CFG – CNF adalah sebagai berikut :
1. Eliminir semua produksi hampa
2. Eliminir semua produksi unitas
3. Terapkan prinsip batasan bentuk ruas kanan produksi
4. Terapkan prinsip batasan panjang ruas kanan produksi
• Penjelasan Tentang 4 Langkah Konversi
1. Eliminasi produksi hampa
Produksi hampa dikaitkan dengan pengertian nullable
Suatu simbol A ∈ VN dikatakan nullable jika :
(a) terkait dengan produksi berbentuk : A → ε, atau
(b) terkait dengan derivasi berbentuk : A ⇒…⇒ ε
Eliminasi yang dilakukan terhadap simbol nullable adalah :
(a) Buang produksi hampa
(b) Tambahkan produksi lain yang merupakan produksi lama tetapi simbol nullablenya
yang di ruas kanan produksi dicoret.
Contoh 9 :
Lakukan eliminasi produksi hampa terhadap himpunan produksi berikut :
Q = { S → aXbaYa, X → Yε, Y → bX}
Solusi :
• Simbol nullable adalah X (karena X → ε) dan Y (karena Y ⇒ X ⇒ ε)
• Dua langkah eliminasi simbol nullable adalah :
- langkah (a) menghilangkan produksi X → ε
- langkah (b) menambahkan produksi S → b (pencoretan simbol nullable X pada
produksi S → Xb) dan produksi S → aa (pencoretan simbol nullable Y pada
produksi S → aYa)
• Himpunan produksi setelah dilakukan eliminasi produksi hampa adalah :
Q = {S → aXbaYabaa, X → Y, Y → bX}
2. Eliminasi produksi unitas
Produksi unitas berbentuk A → B, dimana A,B ∈ VN
• Jika ada produksi berbentuk : A → B , atau derivasi A ⇒ X1 ⇒ X2 ⇒ ... ⇒ B ,
dan jika ada produksi non-unitas dari B berbentuk : B → α1 α2 ...αn , maka
eliminasi yang dilakukan akan menghapus produksi A → B dan menghasilkan
produksi : A → α1 α2 ...αn .
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 27
• Tidak dilakukan eliminasi terhadap derivasi tertutup karena tidak akan menghasilkan
produksi baru. Bentuk derivasi tertutup adalah : A ⇒ X1 ⇒ X2 ⇒ ... ⇒ A
Contoh 10 :
Lakukan eliminasi produksi unitas terhadap himpunan produksi berikut :
Q = {S → Abb, A → Bb, B → Sa}
Solusi :
Untuk memudahkan, pisahkan produksi unitas dan non-unitas :
Produksi unitas : S → A, A → B, B → S
Produksi non unitas : S → bb, A → b, B → a
Proses eliminasi yang dilakukan adalah :
S → A dan A → b menghapus S → A dan menghasilkan S → b
S ⇒ A ⇒ B dan B → a menghasilkan S → a
A → B dan B → a menghapus A → B dan menghasilkan A → a
A ⇒ B ⇒ S dan S → bb menghasilkan A → bb
B → S dan S → bb menghapus B → S dan menghasilkan B → bb
B ⇒ S ⇒ A dan A → b menghasilkan B → b
Perhatikan bahwa derivasi S ⇒ A ⇒ B ⇒ S (derivasi tertutup) dan produksi S → bb
akan menghasilkan produksi S → bb yang jelas bukan merupakan produksi baru.
Karena itu terhadap derivasi ini tidak dilakukan eliminasi.
3. Penerapan batasan bentuk ruas kanan produksi
Penerapan batasan bentuk ruas kanan produksi adalah mengubah semua bentuk
produksi ke dalam 2 bentuk berikut : A → a dan A → B1 B2 ... Bn , n ≥ 2.
Contoh 11:
Terapkan batasan bentuk ruas kanan produksi terhadap himpunan produksi berikut :
Q = {S → Aa, A → bAa}
Solusi :
- produksi S → Aa diubah menjadi : S → AXa , X a → a
- produksi A → bAa diubah menjdi : A → XbA Xa , X a → a, Xb → b
sehingga himpunan produksi menjadi :
Q = {S → AXa , A → XbA Xa , X a → a, Xb → b}
4. Penerapan batasan panjang ruas kanan produksi
Penerapan batasan panjang ruas kanan produksi adalah mengubah semua bentuk
produksi sehingga panjang untai ruas kanannya ≤ 2.
Contoh 12 :
Terapkan batasan panjang ruas kanan produksi terhadap himpunan produksi berikut :
Q = {S → ABCDABC, B → XbB X a }
Solusi :
- produksi S → ABCD diubah menjadi : S → AT1 , T1 → BT2 , T2 → CD
- produksi S → ABC diubah menjadi : S → AT3 , T3 → BC
- produksi B → XbB X a diubah menjadi : B → XbT4 , T4 → B X a
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 28
sehingga himpunan produksi menjadi :
Q = {S → AT1 , T1 → BT2 , T2 → CD, S → AT3 , T3 → BC, B → XbT4 ,
T4 → B X a }
• Contoh 13 : Penyelesaian Konversi CFG ke CNF
Diberikan Q = {S → AACD , A → aAbε , C → aCa , D → aDabDbε }
Transformasikan himpunan produksi tersebut ke dalam bentuk CNF-nya.
1. Eliminasi Produksi Hampa
Dari bentuk Q di atas, maka simbol nullable adalah A dan D. Dua langkah
eliminasi yang dilakukan adalah :
- penghilangan produksi hampa A → ε dan D → ε
- pembentukan produksi hampa dari produksi yang mengandung simbol nullable :
• dari S → AACD dibentuk : S → ACDAACACCDC
• dari A → aAb dibentuk : A → ab
• dari D → aDabDb dibentuk : D → aabb
Dengan demikian Q berubah menjadi :
Q = {S → AACDACDAACACCDC ,
A → aAbab , C → aca , D → aDabDbaabb }
2. Eliminasi Produksi Unitas
Q hasil langkah pertama di atas mengandung satu produksi unitas : S → C. Proses
eliminasi yang dilakukan adalah :
S → C dan C → aca menghapus S → C dan menghasilkan S → aca
Dengan demikian Q berubah menjadi :
Q = {S → AACDACDAACACCDaca ,
A → aAbab , C → aca , D → aDabDbaabb }
3. Penerapan Batasan Bentuk Ruas Kanan
Setelah langkah 2, ternyata Q masih mengandung produksi-prosuksi yang tidak
ber-bentuk A → a dan A → B1 B2 ... Bn (n ≥ 2). Produksi-produksi tersebut
adalah :
S → aC, A → aAbab, C → aC, D → aDabDbaabb. Bentuk-bentuk
produksi ini diubah sebagai berikut :
S → aC menjadi S → X a C dan Xa → a
A → aAbab menjadi A → X a A Xb X a Xb dan X a → a, Xb → b
C → aC menjadi C → X a C dan Xa → a
D → aDabDbaabb menjadi D → X a D X a XbD Xb X a Xa XbXb
dan Xa → a, Xb → b
Bentuk Grammar sampai langkah 3 ini adalah :
Q = { S → AACDACDAACACCD X a Ca , A → X a A Xb X a Xb ,
C → X a Ca , D → X a D X a XbD Xb X a X a Xb Xb ,
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 29
X a → a , Xb → b}
4. Penerapan Batasan Panjang Ruas Kanan
Bentuk Q terakhir masih mengandung produksi-produksi dengan panjang untai
ruas kanan ≥ 2. Produksi-produksi tersebut adalah : S → AACDACDAAC ,
A → Xa AXb , D → Xa DXa XbDXb . Bentuk-bentuk produksi ini diubah
sebagai berikut :
S → AACD menjadi : S → A T1 , T1 → A T2 , T2 → CD
S → ACD menjadi : S → A T2 , T 2 → CD
S → AAC menjadi : S → A T 3 , T 3 → AC
A → X a AXb menjadi : A → X a T 4 , T 4 → AXb
D → X a DXa menjadi : D → X a T 5 , T 5 → DXa
D → XbDXb menjadi : D → XbT 6 , T 6 → DXb
Bentuk grammar sampai langkah 4 ini adalah bentuk CNF, yaitu :
Q = {S → A T1 A T2 A T 3 ACCDXa Ca,
T1
→ A T2 , T2 → CD , T 3 → AC ,
A → X a T 4 X a Xb , T 4 → A Xb ,
C → X a Ca,
D → X a T 5 XbT 6 X a X a Xb Xb , T 5 → DXa , T 6 → DXb ,
Xa
→ a, Xb → b }
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 30
5.3. Automata Pushdown (APD)
• Definisi : PDA adalah pasangan 7 tuple M = (Q, Σ, Γ, q 0 , Z 0 , δ, A), dimana :
Q : himpunan hingga stata, Σ : alfabet input, Γ : alfabet stack, q 0 ∈ Q : stata awal,
Z0 ∈ Γ : simbol awal stack, A ⊆ Q : himpunan stata penerima,
fungsi transisi δ : Q × (Σ ∪ {ε}) × Γ → 2 Q × Γ* (himpunan bagian dari Q × Γ*)
• Untuk stata q ∈ Q, simbol input a ∈ Σ, dan simbol stack X∈ Γ, δ(q, a, X) = (p, α)
berarti : PDA bertransisi ke stata p dan mengganti X pada stack dengan string α.
• Konfigurasi PDA pada suatu saat dinyatakan sebagai triple (q, x, α), dimana :
q ∈ Q : stata pada saat tersebut, x ∈ Σ* : bagian string input yang belum dibaca,
dan α ∈ Γ* : string yang menyatakan isi stack dengan karakter terkiri menyatakan
top of stack.
• Misalkan (p, ay, Xβ) adalah sebuah konfigurasi, dimana : a ∈ Σ, y ∈ Σ*, X ∈ Γ,
dan β ∈ Γ*. Misalkan pula δ(p, a, X) = (q, γ) untuk q ∈ Q dan γ ∈ Γ*. Dapat kita
tuliskan bahwa : (p, ay, Xβ) ⇒ (q, y, γβ).
Contoh 14 (PDA Deterministik):
PDA M = (Q, Σ, Γ, q 0 , Z 0 , δ, A) pengenal palindrome L = {xcx T x ∈ (ab)*},
dimana x T adalah cermin(x), mempunyai tuple : Q = {q 0 , q1 , q 2 }, A = { q 2 },
Σ = {a, b, c}, Γ = {a, b, Z 0 }, dan fungsi transisi δ terdefinisi melalui tabel berikut :
No. Stata Input TopStack Hasil No. Stata Input TopStack Hasil
1 q 0 a Z 0 (q 0 , aZ 0 ) 7 q 0 c Z 0 (q 1 , Z 0 )
2 q 0 b Z 0 (q 0 , bZ 0 ) 8 q 0 c a (q 1 , a)
3 q 0 a a (q 0 , aa) 9 q 0 c b (q 1 , b)
4 q 0 b a (q 0 , ba) 10 q 1 a a (q 1 , ε)
5 q 0 a b (q 0 , ab) 11 q 1 b b (q 1 , ε)
6 q 0 b b (q 0 , bb) 12 q 1 ε Z0 (q 2 , ε)
Sebagai contoh, perhatikan bahwa fungsi transisi No. 1 dapat dinyatakan sebagai :
δ(q 0 , a, Z 0 ) = (q 0 , aZ 0 ). Pada tabel transisi tersebut terlihat bahwa pada stata q 0
PDA akan melakukan PUSH jika mendapat input a atau b dan melakukan transisi
stata ke stata q 1 jika mendapat input c. Pada stata q1 PDA akan melakukan POP.
Berikut ini pengenalan dua string oleh PDA di atas :
1. abcba : (q 0 , abcba, Z 0 ) ⇒ (q 0 , bcba, aZ 0) (1)
⇒ (q 0 , cba, baZ 0) (4)
⇒ (q 1 , ba, baZ 0) (9)
⇒ (q 1 , a, aZ 0 ) (11)
⇒ (q 1 , ε, Z 0) (10)
⇒ (q 2 , ε, Z 0 ) (12) (diterima)
2. acb : (q 0 , acb, Z 0 ) ⇒ (q 0 , cb, aZ 0) (1)
⇒ (q 1 , b, aZ 0) (8), (crash → ditolak)
3. ab : (q 0 , ab, Z 0 ) ⇒ (q 0 , b, aZ 0) (1)
⇒ (q 0 , ε, baZ 0) (4) (crash → ditolak)
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 31
Penerimaan dan penolakan tiga string di atas dapat dijelaskan sebagai berikut :
1. string abcba diterima karena tracing sampai di stata penerima (q 2 ) dan string
“abcba” selesai dibaca (string yang belum dibaca = ε)
2. string acb ditolak karena konfigurasi akhir (q1 , b, a Z 0 ) sedangkan fungsi transisi
δ(q 1 , b, a) tidak terdefinsi
3. string ab ditolak karena konfigurasi akhir (q 0 , ε, baZ 0 ) sedangkan fungsi transisi
δ(q 0 , ε, b) tidak terdefinsi
Ilustrasi graf fungsi transisi PDA di atas ditunjukkan melalui gambar berikut :
b, Z 0 /bZ 0 a, a/ε
a, Z 0 /aZ 0 a, a/aa
c, a/a
c, b/b
q0
c, Z0 / Z 0 q1 ε, Z 0 / Z 0 q2
a, b/ab b, b/bb
b, a/ba b, b/ε
• Notasi (p, ay, Xβ) ⇒ (q, y, γβ) dapat diperluas menjadi : (p, x, α) ⇒* (q, y, β),
yang berarti konfigurasi (q, y, β) dicapai melalui sejumlah (0 atau lebih) transisi.
• Ada dua cara penerimaan sebuah kalimat oleh PDA, yang masing-masing terlihat
dari konfigurasi akhir, sebagaimana penjelasan berikut :
Jika M = (Q, Σ, Γ, q 0 , Z 0 , δ, A) adalah PDA dan x ∈Σ*, maka x diterima dengan
stata akhir (accepted by final state) oleh PDA M jika : (q 0 , x, Z 0 ) ⇒* (q, ε, α)
untuk α ∈ Γ * dan q ∈ A. x diterima dengan stack hampa (accepted by empty
stack) oleh PDA M jika : (q 0 , x, Z 0 ) ⇒* (q, ε, ε) untuk q ∈ Q.
Contoh 15 (PDA Non-Deterministik):
PDA M = (Q, Σ, Γ, q 0 , Z 0 , δ, A) pengenal palindrome L = {xx T x ∈ (ab)*}
mempunyai komponen tuple berikut : Q = {q 0 , q 1 , q 2 }, A = { q 2 }, Σ = {a, b},
Γ = {a, b, Z 0 }, dan fungsi transisi δ terdefinisi melalui tabel berikut :
No. St. In. TS Hasil No. St. In. TS Hasil
1 q 0 a Z 0 (q 0 , aZ 0 ),(q1 , Z 0 ) 7 q 0 ε Z 0 (q 1 , Z 0 )
2 q 0 b Z 0 (q 0 , bZ 0 ),(q 1 , Z 0 ) 8 q 0 ε a (q 1 , a)
3 q 0 a a (q 0 , aa),(q1 , a) 9 q 0 ε b (q 1 , b)
4 q 0 b a (q 0 , ba),(q1 , a) 10 q 1 a a (q 1 , ε)
5 q 0 a b (q 0 , ab),(q1 , b) 11 q 1 b b (q 1 , ε)
6 q 0 b b (q 0 , bb),(q 1 , b) 12 q 1 ε Z 0 (q 2 , ε)
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 32
Pada tabel transisi tersebut terlihat bahwa pada stata q 0 PDA akan melakukan PUSH
jika mendapat input a atau b dan melakukan transisi stata ke stata q1 jika mendapat
input ε. Pada stata q1 PDA akan melakukan POP. Contoh 14 dan 15 menunjukkan
bahwa PDA dapat dinyatakan sebagai mesin PUSH-POP.
Berikut ini pengenalan string “baab” oleh PDA di atas :
1. (q 0 , baab, Z 0 ) ⇒ (q 0 , aab, bZ 0 ) (2 kiri)
⇒ (q 0 , ab, abZ 0) (5 kiri)
⇒ (q 1 , ab, abZ 0) (3 kanan)
⇒ (q 1 , b, bZ 0 ) (11)
⇒ (q 1 , ε, Z 0) (10)
⇒ (q 2 , ε, Z 0 ) (12) (diterima)
2. (q 0 , baab, Z 0 ) ⇒ (q 1 , baab, Z 0) (2 kanan) (crash → ditolak)
3. (q 0 , baab, Z 0 ) ⇒ (q 0 , aab, bZ 0) (2 kiri)
⇒ (q 0 , ab, abZ 0) (5 kiri)
⇒ (q 0 , b, aabZ 0) (3 kiri)
⇒ (q 1 , b, aabZ 0) (4 kanan) (crash → ditolak)
4. (q 0 , baab, Z 0 ) ⇒ (q 0 , aab, bZ 0) (2 kiri)
⇒ (q 0 , ab, abZ 0) (5 kiri)
⇒ (q 0 , b, aabZ 0) (3 kiri)
⇒ (q 0 , ε, baabZ 0) (4 kiri)
⇒ (q 1 , ε, baabZ 0) (9) (crash → ditolak)
VI. PENGANTAR KOMPILASI
6.1. Translator
Translator (penerjemah) adalah sebuah program yang menerjemahkan sebuah program
sumber (source program) menjadi program sasaran (target program).
input : program sumber translator output : program sasaran
Jenis-jenis translator berdasarkan bahasa pemrograman yang bersesuaian dengan input
dan outputnya adalah :
Jenis Translator Bahasa Pemrograman
Input Output
Assembler Bahasa Rakitan Bahasa mesin
Compiler (Kompilator) Bahasa tingkat tinggi Bahasa tingkat rendah
6.2. Kompilator dan komponennya
Black box sebuah kompilator dapat digambarkan melalui diagram berikut :
program sumber kompilator program sasaran
pesan-pesan kesalahan
(error messages)
sedangkan diagram rincinya adalah sebagai berikut :
Program Program
Sumber Sasaran
ANALISA SINTESA
Penganalisa Penganalisa Penganalisa Pembentuk Pengoptimal
Leksikal Sintaks Semantik Kode Kode
(Scanner) (Parser)
Tabel
Proses kompilasi dikelompokkan ke dalam dua kelompok besar :
1. analisa : program sumber dipecah-pecah dan dibentuk menjadi bentuk antara (intermediate
representation)
2. sintesa : membangun program sasaran yang diinginkan dari bentuk antara
Program sumber merupakan rangkaian karakter. Berikut ini hal-hal yang dilakukan oleh
setiap fase pada proses kompilasi terhadap program sumber tersebut :
1. Penganalisa leksikal :
membaca program sumber, karakter demi karakter. Sederetan (satu atau lebih)
karakter dikelompokkan menjadi satu kesatuan mengacu kepada pola kesatuan
kelompok karakter (token) yang ditentukan dalam bahasa sumber. Kelompok karakter
yang membentuk sebuah token dinamakan lexeme untuk token tersebut. Setiap token
yang dihasilkan disimpan di dalam tabel simbol. Sederetan karakter yang tidak
mengikuti pola token akan dilaporkan sebagai token tak dikenal (unidentified token).
Contoh : Misalnya pola token untuk identifier I adalah : I = huruf(hurufangka)*.
Lexeme ab2c dikenali sebagai token sementara lexeme 2abc atau abC tidak
dikenal.
2. Penganalisa sintaks :
memeriksa kesesuaian pola deretan token dengan aturan sintaks yang ditentukan
dalam bahasa sumber. Deretan token yang tidak sesuai aturan sintaks akan dilaporkan
sebagai kesalahan sintaks (sintax error). Secara logika deretan token yang bersesuaian
dengan sintaks tertentu akan dinyatakan sebagai pohon parsing (parse tree).
Contoh : Misalnya sintaks untuk ekspresi if-then E adalah : E → if L then, L → IOA,
I = huruf(hurufangka)*, O → <=><=>=, A → 01...9. Ekspresi
if a2 < 9 then adalah ekspresi sesuai sintaks; sementara ekspresi if a2 < 9 do
atau if then a2B < 9 tidak sesuai. Perhatikan bahwa contoh ekspresi terakhir
juga mengandung token yang tidak dikenal.
3. Penganalisa semantik :
memeriksa token dan ekspresi dengan acuan batasan-batasan yang ditetapkan.
Batasan-batasan tersebut misalnya :
a. panjang maksimum token identifier adalah 8 karakter,
b. panjang maksimum ekspresi tunggal adalah 80 karakter,
c. nilai bilangan bulat adalah -32768 s/d 32767,
d. operasi aritmatika harus melibatkan operan-operan yang bertipe sama.
4. Pembangkit kode (atau pembangkit kode antara):
membangkitkan kode antara (intermediate code) berdasarkan pohon parsing. Pohon
parse selanjutnya diterjemahkan oleh suatu penerjemah, misalnya oleh penerjemah
berdasarkan sintak (syntax-directed translator). Hasil penerjemahan ini biasanya
merupakan perintah tiga alamat (three-address code) yang merupakan representasi
program untuk suatu mesin abstrak. Perintah tiga alamat bisa berbentuk quadruples
(op, arg1, arg2, result), tripels (op, arg1, arg2). Ekspresi dengan satu argumen
dinyatakan dengan menetapkan arg2 dengan - (strip, dash).
5. Pengoptimal kode :
melakukan optimasi (penghematan space dan waktu komputasi), jika mungkin, terhadap
kode antara.
Refrensi : Asep Juarna, Catatan Teori Bahasa dan Automata,
Subscribe to:
Posts (Atom)