automata [bahasa dan kompilasi]
DESCRIPTION
fggfTRANSCRIPT
![Page 1: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/1.jpg)
Bahasa dan Kompilasi
AutomataYuda Syahidin
![Page 2: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/2.jpg)
AutoMata model matematika terdiri dari beberapa state suatu mesin yang menerima inputan
yang apat diterima atau tidak
![Page 3: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/3.jpg)
Bila mesin mendapat untai / string input :ada diterimaadu diterimaadd ditolak
Contoh mesin AutoMata sederhana
![Page 4: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/4.jpg)
Bila mesin mendapat untai / string input :ada diterimaadu diterimaadd ditolak
Contoh mesin AutoMata sederhana
![Page 5: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/5.jpg)
VENDING MACHINE
Misalkan Vending Machine akan mengeluarkan sebatang coklat yang berharga Rp. 25,‐, Masukan dari mesin berupa himpunan uang logam (koin) yaitu {koin Rp. 5, koin Rp. 10,‐, koin Rp. 25,‐}Keluaran dari mesin yaitu suatu tanda bahwa sebatang coklat dikeluarkan dari vending machine jika masukan dapat diterima mesin yaitu uang sejumlah Rp. 25,‐, Model mesin diatas dapat menerima sejumlah berhingga barisan‐barisan seharga 25 yaitu{(25), (10,5,10), (10,10,5), (10,5,5,5), (5,5,5,10), (5,5,5,5,5)}
![Page 6: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/6.jpg)
Finite State Automata
Finite State Automata (Otomata dengan state berhingga)
Memiliki state yang banyaknya berhingga dan dapat berpindah‐pindah dari suatu state ke state yang lain
Perubahan state ini dinyatakan dengan fungsi transisi
FSA tidak memiliki tempat penyimpanan sehingga kemampuan mengingatnya terbatas.
![Page 7: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/7.jpg)
Finite State Automata
Pengecekan Parity Ganjil
![Page 8: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/8.jpg)
Finite State Automata
Pengecekan Parity Ganjil
![Page 9: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/9.jpg)
Finite State Automata
Pengecekan Parity Ganjil
![Page 10: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/10.jpg)
Jenis Finite State
Automata
1. DFA (Deterministic Finite Automata) otomata berhingga yang pasti (tetap/tertentu)
2. NDFA (Non‐Deterministic Finite Automata) otomata berhingga yang tidak pasti
![Page 11: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/11.jpg)
DFA (DETERMINISTIC FINITE AUTOMATA)
![Page 12: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/12.jpg)
DFA (DETERMINISTIC FINITE AUTOMATA)
![Page 13: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/13.jpg)
DFA (DETERMINISTIC FINITE AUTOMATA)
![Page 14: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/14.jpg)
DFA (DETERMINISTIC FINITE AUTOMATA)
![Page 15: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/15.jpg)
DFA (DETERMINISTIC FINITE AUTOMATA)
![Page 16: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/16.jpg)
NDFA (NON DETERMINISTIC FINITE AUTOMATA)
DFA setiap rancangan state input selalu tepat ada satu state berikutnya
NFA untuk setiap pasangan state input, bisa memiliki 0 (nol) atau lebih pilihan untuk state berikutnya
![Page 17: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/17.jpg)
NDFA (NON DETERMINISTIC FINITE AUTOMATA)
contoh
Keterangan :Suatu string diterima oleh DFA bila terdapat suatu urutan transisi sehubungan dengan input string tersebut dari state awal sampai dengan state akhir.
Untuk NFA harus dicoba semua kemungkinan yang ada sampai terdapat satu yang mencapai state akhir.Suatu string x dinyatakan diterima oleh bahasa NFA, M= (Q, Σ, δ, S, F) bila{x | δ (S,x) memuat sebuah state di dalam F}
![Page 18: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/18.jpg)
NDFA (NON DETERMINISTIC FINITE AUTOMATA)
soal
![Page 19: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/19.jpg)
NDFA (NON DETERMINISTIC FINITE AUTOMATA)
solusi
![Page 20: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/20.jpg)
NDFA (NON DETERMINISTIC FINITE AUTOMATA)
Soal
![Page 21: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/21.jpg)
NDFA (NON DETERMINISTIC FINITE AUTOMATA)
Solusi
![Page 22: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/22.jpg)
NDFA (NON DETERMINISTIC FINITE AUTOMATA)
Soal
Buat diagram NDFA-nya!
Q =
∑ = {a,b,c}
S=
F=
![Page 23: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/23.jpg)
NDFA (NON DETERMINISTIC FINITE AUTOMATA)
Solusi
![Page 24: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/24.jpg)
NDFA (NON DETERMINISTIC FINITE AUTOMATA)
Soal
Berdasarkan diagram NDFA periksalah string berikut ini : aa, ab,bb,ba !
![Page 25: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/25.jpg)
NDFA (NON DETERMINISTIC FINITE AUTOMATA)
Soal
Buat NFA
![Page 26: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/26.jpg)
NDFA (NON DETERMINISTIC FINITE AUTOMATA)
Soal
Buat Table Transisinya
q3
q4
q1 q2
0,1
0,10
0
11
1
![Page 27: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/27.jpg)
Equivalensi Finite Automata
• Finite Automata dikatakan ekuivalen apabila menerima bahasa yang sama.
• Dari sebuah mesin NFA dapat dibuat mesin DFA yang ekuivalen yaitu mampu menerima bahasa yang sama.
![Page 28: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/28.jpg)
Konstruksi Mesin DFA dari NFA
![Page 29: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/29.jpg)
Konstruksi Mesin DFA dari NFA
![Page 30: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/30.jpg)
Konstruksi Mesin DFA dari NFA
![Page 31: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/31.jpg)
Konstruksi Mesin DFA dari NFA
![Page 32: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/32.jpg)
Konstruksi Mesin DFA dari NFA
![Page 33: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/33.jpg)
Konstruksi Mesin DFA dari NFA
![Page 34: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/34.jpg)
Konstruksi Mesin DFA dari NFA
![Page 35: AutoMata [Bahasa Dan Kompilasi]](https://reader033.vdokumen.com/reader033/viewer/2022061412/563dbb31550346aa9aab0ac5/html5/thumbnails/35.jpg)
Thank You