PERTEMUAN 14BAHASA FORMAL DAN MESIN STATUS

TERHINGGATERHINGGA

Bahasa FormalSuatu dasar translasi bahasa berhubungan dengan pengolahanbahasa. Di mana dalam translasi bahasa terdapat istilah bahasaformal dan bahasa natural.

Bahasa natural adalah bagian dari komunikasi manusia. Cont :bahasa Inggris, Indonesia dll

Bahasa Formal adalah suatu bahasa yang harus mengikutiBahasa Formal adalah suatu bahasa yang harus mengikutiaturan bahasa pemrograman dan bahasa matematisseperti aljabar dan logika proposisi. Karena aturantersebut akan mengkonstruksi programing translatoruntuk bahasa pemrograman.

Cont: language translator yaitu compiler untuk bahasapemrograman. Yang pada dasarnya tugas translatoradalah mengenali individual building block dari bahasayang akan ditranslasi.

Proses translasi : Source Program menjadi object program1. Proses mengenali runtunan multisimbol di dalam

program ditangani oleh compiler yang disebut lexicalanalyser yaitu sub modul yang menerima source

parserCode generator Object

program

analyser yaitu sub modul yang menerima sourceprogram sebagai string dari simbol dan menghasilkanstring token. Token menyatakan objek tunggal yangdipresentasikan oleh lebih dari satu simbol dari inputstring.

2. Selanjutnya translator menganalisa pola dari token,misal if-then, if-then-else, atau perulangan loop. Analisisyang dilakukan disebut dengan parsing dan dilakukanoleh modul di dalam compiler yang disebut paser.

3. Ketika paser mengenali struktur di dalam program, makamodul selanjutnya adalah code generator untukmenghasilkan versi translasi dari bagian program.Setelah semua bagian translasi dibentuk, maka dibentukversi translasi program yang disebut object program.

Tatabahasa Struktur FrasaDua hal penting untuk menspesifikasikan bahasa yaitu:1. Jika diberikan spesifikasi suatu bahasa, secara

otomatis akan membangkitkan satu atau lebih string didalam bahasa itu.

2. Jika diberikan spesifikasi suatu bahasa, tentukanapakah suatu string tertentu akan termasuk di dalambahasa itu atau tidak.

Suatu tatabahasa frasa dapat digunakan untukmenspesifikasikan suatu bahasa, yang terdiri dari empatunsur yaitu:

1. Himpunan terminal T, yaitu lambang atau simbol yangdigunakan untuk membuat kalimat dalam bahasa,misal: objek/benda, dan kata sifat.

2. Himpunan nonterminal N, yaitu lambang antara yang2. Himpunan nonterminal N, yaitu lambang antara yangdigunakan untuk mendeskrepsikan struktur kalimat,misal: kalimat, frasa kata benda, kata-benda, kata-sandang dll

3. Himpunan produksi P, yaitu kaidah tatabahasa yangmengatur bagaimana kalimat di dalam bahasa itu dapatdibentuk, misal: α β dalam hal ini a dan β adalahrangkaian terminal dan non terminal.

4. Di antara semua nonterminal di dalam N, ada sebuahnonterminal khusus yang disebut sebagai simbol awal(starting symbol)

Jenis Tatabahasa dan jenis bahasaDalam bahasan ini akan digunakan A dan B untukDalam bahasan ini akan digunakan A dan B untukmenyatakan nonterminal, a dan b untuk menyatakanterminal dan α dan β untuk menyatakan string terminal dannonterminal.Tatabahasa jenis -3 jika semua produksi di dalam

tatabahasa berbentuk :A a atau A BaA aB

Di dalam setiap produksi, string kirinya selalu berupa sebuahnonterminal tunggal, sedangkan string kanannya berupa sebuahterminal atau sebuah terminal yang diikuti dengan sebuahnonterminal.

Tatabahasa jenis-2 jika semua produksi di dalam tatabahasaberbentuk A αdi dalam setiap produksi, string kirinya selalu berupa sebuahdi dalam setiap produksi, string kirinya selalu berupa sebuahnonterminal tunggal.

Tatabahasa jenis-1 jika semua produksi di dalam tatabahasaberbentuk α βpanjang β selalu lebih besar atau sama dengan α. Misalnya:A ab

A aAaAb aBCb

Tatabahasa jenis-0 yaitu tatabahasa struktur frasa tanpapembatasan seperti yang telah didefinisikan oleh jenis 1, 2, 3.Semua bahasa pemrograman dapat dispesifikasi olehtatabahasa struktur frasa dan kebanyakan merupakan bahasajenis-2 misal: BASIC, Fortran, Pascal).

Automata Terhingga (finite automata)Automata terhingga dan bahasa reguler adalah level terendahAutomata terhingga dan bahasa reguler adalah level terendahdari hirarki mesin dan bahasa. Salah satu aplikasinya adalahkonstruksi pengkompilasi (compiler), yaitu pengenalan string darisimbol di kode sumber program yang harus direpresentasikansebagai objek tunggal seperti nama variabel, konstanta danreserved word.Salah satu bentuk bentuk penggambaran untuk representasistrukturnya adalah diagram transisi (diagram status ataujaringan transisi)

Mesin Status TerhinggaSuatu mesin status terhingga mempunyai ciri-ciri sebagaiberikut:

1. Himpunan terhingga status-status S={s0,s1, s2,…}2. Unsur khusus di dalam himpunan S, yaitu s0 yang

dinamakan status awal.dinamakan status awal.3.Himpunan terhingga huruf-huruf masukan I={i0,i1,i2,…}4.Himpunan terhingga huruf-huruf keluaran

O={o0,o1,o2,…}5. Fungsi transisi yaitu fungsi f dari S x I ke S6. Fungsi keluaran yaitu fungsi g dari S ke O

Sinyal (huruf) keluaranMasukan

Suatu mesin status terhingga mempunyai sejumlahterhingga status. Setelah diterimanya sebuah huruf

Mesin

Pemroses

Informasi

terhingga status. Setelah diterimanya sebuah hurufmasukan, mesin akan memasuki status lain berdasarkanfungsi transisinya.

Mesin Status Terhingga sebagai Model Sistem FisikMesin status terhingga dapat digunakan untukmemodelkan suatu sistem fisik, seperti cont: vendingmachine, mesin hitung modulo-3.

Mesin Status Terhingga sebagai Pengenal BahasaMesin status terhingga dapat digunakan untuk memodelkansuatu alat untuk mengenali (menerima) kalimat-kalimat di dalamsuatu bahasa.

Misalkan: O ={0,1} adalah simbol keluaran sebuah mesin statusterhingga. Bernilai 1 artinya status menerima, dan bernilai 0artinya status menolak.artinya status menolak.Mesin TuringPada tahun 1936 seorang mtematikawan berkebangsaan Inggrisbernama Alan Turing, mengusulkan suatu model sederhanayang mempunyai kemampuan sebuah komputer grneral-purpose. Mesin Turing mengenali kelas bahasa yang disebutsebagai himpunan terenumerasi rekursif dan dapat digunakanuntuk menghitung kelas fungsi bilangan bulat yang dikenalsebagai fungsi rekursif parsial.

Komponen mesin turing :1. Pengendali status terhingga2. Pita masukan dengan sifat:

- panjangnya tak terhingga (dari ujung kiri terbatas, ujungkanan tidak terbatas)- dapat dibaca dan ditulis.

Pada keadaan awal n sel pertama dari pita masukan berisirangkaian simbol yang harus dikenali. Sel-sel lain disebelahkanan rangkaian simbol berisi simbol kosong.

Perilaku mesin Turing bergantung pada simbol masukan yangberada pada posisi kepala (head) baca/tulis dan statuspengendalinya. Aksi-aksi yang dapat dilakukan yaitu:

1. Berubah status2. Menuliskan simbol pada sel pita masukan. Aksi penulisan ini

akan mengubah simbol yang sebelumnya berada pada seltersebut.

3. Menggerakkan head ke kiri dan ke kanan.