PENGERTIAN AUTOMATA DAN TEORI BAHASA

Automata

Arti menurut American Heritage Dictionary:

1. a robot

2. one that behaves in an automatic or mechanical fashion

Arti dalam dunia matematika

Berkaitan dengan teori mesin abstrak, yaitu mesin sekuensial yang menerima input, dan

mengeluarkan output, dalam bentuk diskrit.

Contoh :

¨ Mesin Jaja / vending machine

¨ Kunci kombinasi

¨ Parser/compiler

Jika disimpulkan maka pengertian Automata adalah mesin abstrak yang dapat mengenali

(recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa

tertentu.

Automata berasal dari bahasa Yunani automatos, yang berarti sesuatu yang bekerja

secara otomatis (mesin).

Teori Bahasa

Teori Otomata dan bahasa formal, berkaitan dalam hal pembangkitan kalimat/generation

yaitu, menghasilkan semua kalimat dalam bahasa L berdasarkan aturan yang dimilikinya. Dan

pengenalan kalimat / recognition yaitu, menentukan suatu string(kalimat) termasuk sebagai salah

satu anggota himpunan L.

Teori bahasa membicarakan bahasa formal (formal language), terutama untuk

kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor).

Jadi 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.

JENIS DAN BAGIAN AUTOMATA DAN TEORI BAHASA FORMAL

Automata Hingga (AH)

AH didefinisikan sebagai pasangan 5 tupel : (Q, V T , σ, q0, F):

• Q     : himpunan hingga stata

• VT  : himpunan hingga simbol input (alfabet)

• σ     : fungsi transisi, menggambarkan transisi stata AH akibat pembacaan simbol input.

Fungsi transisi ini biasanya diberikan dalam bentuk tabel.

• q0 ∈ Q   : stata awal

• F ⊂ Q     : 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.

.                 σ (AHD) : Q × V T → Q

- AHN : transisi stata AH akibat pembacaan sebuah simbol bersifat tak tentu.

.                  σ (AHN) : Q × V T → 2Q

Automata Hingga Deterministik (AHD)

Berikut ini sebuah contoh AHD F(Q, V T , σ, q0, Z), dimana :

Q = {q0, q1, q2}   diberikan dalam tabel berikut :

Gambar1.  Tabel AHD

Ilustrasi graf untuk AHD F adalah sebagai berikut :

Lambang stata awal adalah node dengan anak panah.

Lambang stata awal adalah node ganda.

Gambar 2.   Grafik AHD

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. sebuah kalimat diterima oleh AHD jika tracingnya berakhir di salah satu stata

penerima.

.

Automata Hingga Nondeterministik (AHN)

Berikut ini sebuah contoh AHN F(Q, V T , σ, q0, Z), dimana :

Q = {q 0 , q1, q 2 ,q 3 , q 4 }        diberikan dalam tabel berikut :

Gambar3.   Tabel AHN

Ilustrasi graf untuk AHN F adalah sebagai berikut :

Gambar4.  Grafik AHN

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 σ sebuah AHN dapat diperluas sebagai berikut :

1. σ (q, ε) = {q} untuk setiap q ∈ Q

2. σ (q, t T) = ∪ σ (p i , T) dimana t ∈ V T , T adalah V T *, dan σ (q, t) = {p i }

3. σ ({q1, q2, …, qn}, x) = ∪ σ (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.

MODEL KOMPILATOR

Compiler adalah suatu program yang menerjemahkan bahasa program ( source code)

kedalam bahasa objek (obyek code). Compiler menggabungkan keseluruhan bahasa program,

mengumpulkannya dan kemudian menyusunnya kembali.

Komplier memerlukan waktu untuk membuat suatu program dapat di eksekusi oleh

computer, program yang dieksekusi oleh compiler adalah dapat berjalan lebih cepat disbanding

program yang diperoduksi oleh interpreter, disamping itu juga bersifat independen. Contoh

program yang menggunakan compiler adalah Visual Basic, Visual Delvi, dan Pascal.

TAHAPAN DALAM COMPILER

TAHAP ANALISIS (front end, bertugas mendekomposisi program sumber)

Analisis leksikal atau analisis linier atau pembacaan sekilas (scanning). Aliran karakter

yang membentuk program sumber dibaca dari kiri ke kanan dan dikelompokkan dalam  token.

Analisis sintaktik atau analisis hirarki. Token yang diperoleh pada analisis leksikal disusun dan

dikelompokkan dalam suatu hirarki tertentu yang secara keseluruhan mempunyai arti tertentu.

Analisis sematik.

Disini dilakukan pengecekan pada struktur akhir yang telah diperoleh dan diperiksa kesesuaianya

dengan komponen yang ada.

TAHAP SINTESIS (back end, bertugas membentuk dan mengoptimasi kode)

Proses pembentukan kode (code generator).

Bentuk antara dari bahasa sumber  berupa suatu pohon sintaks diterjemahkan ke dalam

suatu bahasa asembli atau bahasa mesin

Proses optimasi kode (code optimizer).

Hasil pembentukan kode yang diperoleh kemudian dibuat lebih kompak lagi dengan

melakukan beberapa teknik optimasi supaya dapat diperoleh program yang lebih efisien

Assambler

Bahasa assembly adalah sebuah program yang terdiri dari instruksi-instruksi yang

menggantikan kode-kode biner dari bahasa mesin dengan “mnemonik” yang mudah diingat.

Misalnya sebuah instruksi penambahan dalam bahasa mesin dengan kode “10110011” yang

dalam bahasa assembly dapat dibuat dalam instruksi mnemonik ADD, sehingga mudah diingat

dibandingkan dengan angka 0 dan 1, dalam setiap instruksi membutuhkan suatu operand baik

berupa data langsung maupun suatu lokasi memori yang menyimpan data yang bersangkutan.

Bahasa assembly sering juga disebut kode sumber atau kode simbolik yang tidak dapat

dijalankan oleh prosesor, sedangkan assembler adalah suatu program yang dapat menerjemahkan

program bahasa assembly ke program bahasa mesin. bahasa mesin adalah kumpulan kode biner

yang merupakan instruksi yang bisa dijalankan oleh komputer. Program bahasa mesin sering

disebut sebagai kode objek.

Interpreter

Interpreter adalah Perangkat lunak yang mampu mengeksekusi code program (yang

ditulis oleh programmer) lalu menterjemahkannya ke dalam bahasa mesin, sehingga mesin

melakukan instruksi yang diminta oleh programmer tersebut. Perintah-perintah yang dibuat oleh

programmer tersebut dieksekusi baris demi baris, sambil mengikuti logika yang terdapat di

dalam kode tersebut.

Proses ini sangat berbeda dengan compiler, dimana pada compiler, hasilnya sudah

langsung berupa satu kesatuan perintah dalam bentuk bahasa mesin,dimana prose penterjemahan

dilaksanakan sebelum program tersebut dieksekusi.

Interpreter atau dalam bahasa Indonesia dikenal sebagai Juru Bahasa berbeda dengan

Translator atau penterjemah dalam segi media yang dipakai untuk menerjemahkan. Interpreter

akan menterjemahkan bahasa sumber ke dalam bahasa sasaran secara langsung atau orally

sementara translator akan menerjemahkan bahasa sumber ke bahasa sasaran secara tertulis.

Java dijalankan menggunakan interpreter yaitu Java Virtual Machine (JVM). Hal ini

menyebabkan source code Java yang telah dikompilasi menjadi Java bytecodes dapat dijalankan

pada platform yang berbeda-beda.

KOMPONEN KOMPILASI

Penganalisa

Leksikal(scanner

)

Penganalisa

Sintaks(parser)

Penganalisa

Semantik

Pembangkit Kode antara

Pembentukkode

Pengoptimalkode

Program

Sumber

Program

Sumber

Program

Sasaran

Program

Sasaran

TABEL

SIMBOL

TABEL

SIMBOL

ANALISA SINTESA

Bagan pokok proses kompilasi

Blok Diagram

METODE PARSING

Parsing adalah konsturksi atau pembentukan Pohon Sintaks untuk suatu kalimat (ekspresi).Bila

terdapat lebih dari satu pohon sintaks untuk sebuah grammar

maka dikatakan grammar tersebut Ambiguous

ada beberapa Metode Parsing antara lain :

1.Parsing top-downparsing top-down adalah 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.

2. Parsing bottom-upParsing bottom-up adalah 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).1.Parsing top-downAda 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.

1. Program Sumber ditulis dalam bahasa sumber, misal Pascal, Assembler, dsb2. Program Sasaran dapat berupa bahasa pemrograman lain

atau bahasa mesin pada

suatu komputer3. Scanner : Memecah program sumber menjadi besaran leksik/token4. Parser : Memeriksa kebenaran dan urutan kemunculan token5. Penganalisa semantik : Melakukan analisa semantik,

biasanya dalam realisasi akan

digabungkan Dengan intermediate code generator (bagian yang berfungsi

membangkitkan kode antara)7. Pengoptimal Kode : Memperkecil hasil dan mempercepat proses8. Tabel : Menyimpan semua informasi yang berhubungan dengan proses kompilasi

Keterangan

Metoda Brute-ForceKelas 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 produksiMetoda 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.

Metoda Recursive-DescentKelas 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.

2.Parsing Bottom-UpSalah 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.Parsing Grammar Preseden SederhanaProsedur 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.

OTOMATA DAN TEORI BAHASA FORMAL

TUGAS SISTEM KOMBINASI

OLEH :

TAUFIK HADAYATTULLAH

09101152630221

PROGRAM STUDI TEKNIK INFORMATIKA

FAKULTAS ILMU KOMPUTER

UNIVERSITAS PUTRA INDONESIA “YPTK”

PADANG

2014