Pengenalan Konsep Bahasa dan Automata Teori Bahasa dan Automata
Viska Mutiawani - Informatika FMIPA Unsyiah
1
Bentuk komputasi yang dikenal saat ini
CPU
memory
2
Detil bentuk komputasi berdasarkan memory temporary memory input CPU output Program memory
3
Example:
f ( x) x
3
temporary memory input CPU output Program memory hitung hitung
xx 2
x x 4
f ( x) x temporary memory
3
input
x2 CPU output Program memory hitung hitung
xx 2
x x 5
temporary memory
f ( x) x
3
z 2*2 4 f ( x) z * 2 8 input
x2 CPU output Program memory hitung hitung
xx 2
x x 6
temporary memory
f ( x) x
3
z 2*2 4 f ( x) z * 2 8 input
x2 CPU
f ( x) 8 Program memory hitung hitung
output
xx 2
x x 7
Automaton temporary memory Automaton input CPU output Program memory
8
Automaton temporary memory Automaton input
output transisi
state
CPU+Program Memory = State + Transisi 9
Beberapa Jenis Automata Automata dibedakan berdasarkan temporary memory
• Finite Automata:
tidak ada temporary memory
• Pushdown Automata: stack
• Turing Machines:
random access memory
10
Memory sangat berpengaruh pada kekuatan komputasi: Memory yang semakin fleksibel berakibat pada munculnya solusi bagi masalah komputasi yang semakin kompleks
11
Finite Automaton temporary memory
Finite Automaton
input
output Contoh: Elevators, Vending Machines, Lexical Analyzers (kekuatan komputasi rendah)
12
Pushdown Automaton Temp. memory
Stack
Push, Pop
Pushdown
input
Automaton output Contoh: Parsers for Programming Languages (kekuatan komputasi sedang) 13
Turing Machine Temp. memory
Random Access Memory
Turing
input
Machine output Contoh: Algoritma apapun (kekuatan komputasi tinggi) 14
Kekuatan Automata Masalah sederhana
Masalah yang lebih kompleks
Masalah sangat kompleks
Finite
Pushdown
Turing
Automata
Automata
Machine
Kekuatan
Kekuatan
Lebih kecil
lebih besar Menyelesaikan masalah yang semakin rumit/kompleks
15
Turing Machine merupakan model komputasi yang paling kuat
Tanya: dapatkah Turing Machine menyelesaikan semua masalah?
Jawab: Tidak (masih ada masalah yang belum terselesaikan) 16
Otomata • 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. 17
• Asal mula ilmu komputer – Turing machine
• Compiler design – Lexical analysis (finite state automata), syntactical analysis (pushdown automata)
• Fondasi dari model checking – Buchi automata, Rabin tree automata
• Fondasi dari pemproses web data (dokumen XML) – Automata over unranked trees 18
Teori Automata • Abstract dan fundamental – Dibandingkan bahasa pemrograman, teori automata bersifat lebih abstract. Sehingga memudahkan jawaban secara matematis, namun tetap merefleksikan esensi dari komputasi.
19
Pionir Teori Automata
20
Sejarah Automata
21
Teori Bahasa • Teori bahasa membicarakan bahasa formal (formal language), terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor)
22
• 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. 23
• Bahasa Natural/manusia bersifat sebaliknya; grammar diciptakan untuk meresmikan katakata yang hidup di masyarakat. Dalam pembicaraan selanjutnya ‘bahasa formal’ akan disebut ‘bahasa’ saja.
24
• Teori Otomata dan bahasa formal, berkaitan dalam hal : – Pembangkitan kalimat/generation : menghasilkan semua kalimat dalam bahasa L berdasarkan aturan yang dimilikinya – Pengenalan kalimat / recognition : menentukan suatu string (kalimat) termasuk sebagai salah satu anggota himpunan L.
25
