![Page 1: Pendahuluan - Materi 1 Teori Bahasa dan Automata](https://reader036.vdokumen.com/reader036/viewer/2022081807/55aa8e541a28abb0558b46dc/html5/thumbnails/1.jpg)
TEORI BAHASA & OTOMATA
STIKOM Artha Buana
Teknik Informatika
2014
Ir. Ahmad Haidaroh, M.Kom.
![Page 2: Pendahuluan - Materi 1 Teori Bahasa dan Automata](https://reader036.vdokumen.com/reader036/viewer/2022081807/55aa8e541a28abb0558b46dc/html5/thumbnails/2.jpg)
Apa itu?
• Mempelajari alat penghitung abstrak, atau
disebut “mesin”
![Page 3: Pendahuluan - Materi 1 Teori Bahasa dan Automata](https://reader036.vdokumen.com/reader036/viewer/2022081807/55aa8e541a28abb0558b46dc/html5/thumbnails/3.jpg)
Sebelum Komputer (1930)
A. Turing mempelajari mesin abstrak (Mesin
Turing) yang memiliki kemampuan seperti
komputer pada saat ini.
![Page 4: Pendahuluan - Materi 1 Teori Bahasa dan Automata](https://reader036.vdokumen.com/reader036/viewer/2022081807/55aa8e541a28abb0558b46dc/html5/thumbnails/4.jpg)
Sebelum Komputer (1930) lanj.
• Tujuan Pak Turing:
Mendeskripsikan secara tepat batasan
antara yang dapat dilakukan dan yang
tidak dapat dilakukan mesin penghitung.
![Page 5: Pendahuluan - Materi 1 Teori Bahasa dan Automata](https://reader036.vdokumen.com/reader036/viewer/2022081807/55aa8e541a28abb0558b46dc/html5/thumbnails/5.jpg)
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
![Page 6: Pendahuluan - Materi 1 Teori Bahasa dan Automata](https://reader036.vdokumen.com/reader036/viewer/2022081807/55aa8e541a28abb0558b46dc/html5/thumbnails/6.jpg)
Visualisasi Otomata
![Page 7: Pendahuluan - Materi 1 Teori Bahasa dan Automata](https://reader036.vdokumen.com/reader036/viewer/2022081807/55aa8e541a28abb0558b46dc/html5/thumbnails/7.jpg)
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.
![Page 8: Pendahuluan - Materi 1 Teori Bahasa dan Automata](https://reader036.vdokumen.com/reader036/viewer/2022081807/55aa8e541a28abb0558b46dc/html5/thumbnails/8.jpg)
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
![Page 9: Pendahuluan - Materi 1 Teori Bahasa dan Automata](https://reader036.vdokumen.com/reader036/viewer/2022081807/55aa8e541a28abb0558b46dc/html5/thumbnails/9.jpg)
Konsep Sentral Teori Otomata
• Alfabet
• String
• Pangkat Alfabet
• Pangkat Bintang Kleen
• Konkatenasi
• Bahasa
![Page 10: Pendahuluan - Materi 1 Teori Bahasa dan Automata](https://reader036.vdokumen.com/reader036/viewer/2022081807/55aa8e541a28abb0558b46dc/html5/thumbnails/10.jpg)
Mesin Otomata
• FSA : Finite State Automata
• PDA : Pushdown Automata
• Mesin Turing
![Page 11: Pendahuluan - Materi 1 Teori Bahasa dan Automata](https://reader036.vdokumen.com/reader036/viewer/2022081807/55aa8e541a28abb0558b46dc/html5/thumbnails/11.jpg)
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
![Page 12: Pendahuluan - Materi 1 Teori Bahasa dan Automata](https://reader036.vdokumen.com/reader036/viewer/2022081807/55aa8e541a28abb0558b46dc/html5/thumbnails/12.jpg)
Penilaian
Kehadiran & Keaktifan : 20% UTS: 20%
Tugas: 30% UAS: 30 %
![Page 13: Pendahuluan - Materi 1 Teori Bahasa dan Automata](https://reader036.vdokumen.com/reader036/viewer/2022081807/55aa8e541a28abb0558b46dc/html5/thumbnails/13.jpg)
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