TEORI BAHASA & OTOMATA

STIKOM Artha Buana

Teknik Informatika

2014

Ir. Ahmad Haidaroh, M.Kom.

Apa itu?

• Mempelajari alat penghitung abstrak, atau

disebut “mesin”

Sebelum Komputer (1930)

A. Turing mempelajari mesin abstrak (Mesin

Turing) yang memiliki kemampuan seperti

komputer pada saat ini.

Sebelum Komputer (1930) lanj.

• Tujuan Pak Turing:

Mendeskripsikan secara tepat batasan

antara yang dapat dilakukan dan yang

tidak dapat dilakukan mesin penghitung.

Yang dipelajari

• Konsep Sentral Teori Otomata

• Mesin Otomata

Otomata : 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 Otomata adalah teori mengenai mesin-mesin abstrak, dan berkaitan

erat dengan teori bahasa formal. ada beberapa hal yang berkaitan dengan

Otomata, yaitu Grammar. Grammar adalah bentuk abstrak yang dapat

diterima (accept) untuk membangkitkan suatu kalimat otomata

berdasarkan suatu aturan tertentu

Visualisasi Otomata

Tujuan Belajar OtomataTeori dasar untuk ilmu pembuatan compiler, parser, intepreter.

Kompilator (Inggris: compiler) adalah sebuah program komputer yang berguna

untuk menerjemahkan program komputer yang ditulis dalam bahasa pemrograman

tertentu menjadi program yang ditulis dalam bahasa pemrograman lain.

Terlepas dari pengertiannya yang demikian relatif luas, istilah kompilator biasa

digunakan untuk program komputer yang menerjemahkan program yang ditulis

dalambahasa pemrograman tingkat tinggi (semacam bahasa

Pascal, C++, BASIC, FORTRAN, Visual Basic, Visual C#, Java, xBase, atau

COBOL) menjadi bahasa mesin, biasanya dengan bahasa Assembly sebagai

perantara.

Dalam komputasi, parser adalah salah satu komponen dalam sebuah interpreter atau

kompiler, yang memeriksa sintaks yang benar dan membangun struktur data (sering

beberapa jenis pohon parse, sintaks abstrak pohon atau struktur hirarkis lainnya) yang

tersirat dalam token masukan. Program pendeteksi kombinasi tombol sering menggunakan

penganalisis leksikal terpisah untuk membuat token dari urutan karakter masukan. Parser

dapat diprogram dengan tangan atau mungkin (semi-) otomatis dihasilkan (dalam beberapa

bahasa pemrograman) dengan alat (seperti Yacc) dari tata bahasa yang ditulis dalam

bentuk Backus-Naur.

Kompilator itu sendiri, yang menerima kode sumber dan menghasilkan

bahasa tingkat rendah (assembly)

Assembler, yang menerima keluaran kompilator dan menghasilkan

berkas objek dalam bahasa mesin

Linker, yang menerima berkas objek keluaran assembler untuk kemudian

digabungkan dengan pustaka-pustaka yang diperlukan dan menghasilkan

program yang dapat dieksekusi (executable)

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

Konsep Sentral Teori Otomata

• Alfabet

• String

• Pangkat Alfabet

• Pangkat Bintang Kleen

• Konkatenasi

• Bahasa

Mesin Otomata

• FSA : Finite State Automata

• PDA : Pushdown Automata

• Mesin Turing

Materi Satu Semester

1. Pendahuluan

2. FSA (Finite State Automata)

3. Ekspresi Reguler

4. Sifat Bahasa Reguler

5. Pumping Lemma

6. CFG (Context Free Grammar)

7. PDA (Push Down Automata)

8. Mesin Turing

9. Review

Penilaian

Kehadiran & Keaktifan : 20% UTS: 20%

Tugas: 30% UAS: 30 %

Referensi

• Hopcroft, J.E; Motwani, R; Ullman, J.D. 2001.

Introduction to Automata Theory, Languages,

and Computation (2nd ed). USA:

Pearson/Addison Wesley.

• Sipser, M. 1997. Introduction to the theory of

computation. Boston: International Thomson

Publishing.

• http://www.univ-

orleans.fr/lifo/Members/Mirian.Halfeld/mi-

TLComp.html