Teori Bahasa dan Otomata

 Non Deterministic Finite Automata (NFA) ke E-Move      Suatu gambar Non-Deterministc Finite Automata (NFA) yang mengandung ε-Move ( ε dapat dianggap “empty” artinya dapat tidak dibaca inputannya atau diperbolehkan langsung menuju state berikutnya tanpa membaca inputan ε).  Contoh gambar Non-Deterministic Finite Automata mengandung ε-Move : Berdasarkan gambar diatas maka dapat di ambil kesimpulan :  - Dari q0 tanpa membaca input dapat langsung berpindah ke state q1  - Dari q2 tanpa membaca input dapat langsung berpindah ke state q3  Kegunaan transisi ε ini adalah memudahkan dalam mengkombinasikan Finite State Automata. ε – Clouser untuk suatu Non-Deterministic Finite Automata dengan ε-Move  ε–closure merupakan himpunan state-state yang dapat dicapai dari suatu state tanpa membaca input. ε–closure sendiri dapat disingkat nantinya menjadi ε–cl. Contoh pada gambar berikut : Langkah-langkah ε – Clouser untuk suatu Non-Deterministic Finite Automat...

 Ekuivalensi dari NFA ke DFA     Ekuivalen artinya sama, pada bahasan materi ini artinya dapat menerima string yang sama baik itu menggunakan mesin Non-Deterministc Finite Automata (NFA) maupun Deterministc Finite Automata (DFA). Sebuah mesin Non-Deterministc Finite Automata (NFA) dapat dibuat menjadi mesin Deterministic Finite Automata(DFA) yang dapat menerima string yang sama. Ada beberapa tahap yang dapat ditempuh untuk melakukan ekuivalensi Non-Deterministc Finite Automata (NFA) ke Deterministc Finite Automata (DFA) :  Buat tabel transisi dari Non-Deterministc Finite Automata (NFA)  Telusuri state berikutnya dengan memanfaatkan tabel transisi ditambah dengan state { }  Tentukan finish baru jika ada, dengan melihat seluruh state yang mengandung finish awal.  Contoh kasus diberikan gambar Non-Deterministc Finite Automata (NFA) berikut :  Diketahui :  Q = {qo,q1}  Σ = {0,1}  S = q0  F = {q1} Buatlah Deterministic Finite Automa...

 Ekuivalensi Antar Deterministic Finite Autamata      Ekuivalensi Antar Deterministic Finite Automata adalah mengurangi jumlah state dari suatu Finite State Automata, dengan tidak mengurangi kemampuannya semula untuk menerima suatu bahasa. Ada dua buah istilah baru yang perlu kita ketahui yaitu :  • Distinguishable yang berarti dapat dibedakan.  • Indistinguishable yang berarti tidak dapat dibedakan. Contoh Ekuivalensi antar DFA:     Berdasarkan gambar diatas dapat diambil kesimpulan bahwa walaupun kedua gambar DFA diatas bebeda tetapi hasil output yang diterimanya tetap sama yaitu hanya dapat menerima inputan yang mengandung a.           Reduksi dilakukan untuk mengurangi jumlah state tanpa mengurangi kemampuan untuk menerima suatu bahasa seperti semula (efisiensi). State pada FSA dapat direduksi apabila terdapat  useless state  Hasil dari FSA yang direduksi merupakan ekivalensi dari FSA semula. P...

 Finite State Automatic     Finite State Automata atau yang dikenal dengan istilah FSA merupakan suatu model mesin otomata dari bahasa reguler. Suatu Finite State Automata dapat memiliki state banyak berhingga yang dapat berpindah-pindah dari suatu state ke state lainnya. Jenis otomata ini tidak memiliki tempat penyimpanan, sehingga kemampuan mengingatnya terbatas.  FSA dipakai untuk penganalisa leksikal dan dipakai juga dalam text editor, pemrosesan teks, dan program file-searching.      Beberapa hal yang harus diketahui berkenaan dengan symbol gambar sebelum memulai materi FSA (Finite State Automata) adalah :  Lingkaran menyatakan state/kedudukan Label pada lingkaran merupakan nama state Busur menyatakan transisi, yaitu perpindahan state/kedudukan Label pada busur merupakan simbol input Lingkaran diawali sebuah busur tanpa label yang artinya state awal Lingkaran ganda menyatakan state akhir/final state FSA atau AH (Automata Hingga) didefinisikan...

 Non Deterministic (NFA)      Non-Deterministic Finite Automata merupakan bagian dari FSA. Non-Deterministic Finite Automata/NFA maksudnya Dari suatu state bisa terdapat 0, 1 atau lebih busur keluar (transisi) berlabel simbol input yang sama. Contohnya : Q = {q0,q2}  ∑ = {a,b}  S = q0  F = {q2}

 Deterministic (DFA)     Deterministic   Finite   Automata   merupakan   bagian   dari   FSA.   Deterministic   Finite   Automata/DFA maksudnya dari suatu state ada tepat satu state berikutnya untuk setiap   simbol   masukan   yang diterima.  DFA, terdiri atas 5 tuple, yaitu : A = ( Q, ∑, δ, S, F ). Notasi Lain DFA : 1. Diagram Transisi / State Diagram  • Tiap keadaan merupakan simpul  • Tiap keadaan q  ∈  Q dan tiap simbol a  ∈   ∑ , dituliskan sebagai  δ (q,a) = p.  Artinya, diagram transisi memiliki panah dari q ke p, yang berlabel a.  • Keadaan awal (q0 ) ditandai dengan adanya panah tanpa sumber.  • Simpul yang menjadi keadaan final ditandai dengan lingkaran bergaris tepi ganda  2. Tabel Transisi  • Representasi daftar dari suatu fungsi  • Baris menunjukkan keadaan dan kolom menunjukkan input.  • Isi dari baris menunjukkan keadaa...

 Grammar dan Bahasa Grammar adalah sebagai kumpulan dari himpunanhimpunan variabel, simbolsimbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi.  Aturan produksi merupakan pusat dari grammar yang menspesifikasikan bagaimana suatu grammar melakukan transformasi suatu string atau karakter ke bentuk lainnya.     Semua aturan produksi dinyatakan dalam bentuk “α → β “ (bisa dibaca α menghasilkan β, atau dibaca α menurunkan β). α merupakan simbol-simbol pada ruas kiri aturan produksi, sedangkan β merupakan simbolsimbol ruas kanan aturan produksi.  Grammar (G) didefinisikan sebagai pasangan 4 tuple :  VT , VN , S, dan Q, dan dituliskan sebagai G(VT , VN , S, Q), dimana :  VT : himpunan simbol-simbol terminal (atau himpunan token-token, atau alfabet)  VN : himpunan simbol-simbol non terminal  S : simbol awal (atau simbol start)  Q : himpunan produks Analisa Penentuan Type Grammar Grammar G1 dengan Q1 = {S → aB, B → bB...

 Hirarki Chomsky Secara umum tata bahasa dirumuskan sebagai berikut:  a  ->  b  yang berarti  a  menghasilkan  b  atau  a  menurunkan  b . Simbol variabel / non teminal adalah simbol yang masih bisa diturunkan dan ditandai dengan huruf besar seperti A, B, C, dst. Simbol terminal adalah simbol yang sudah tidak bisa diturunkan dan ditandai dengan huruf kecil seperti a, b, c, d, dst. Contoh Aturan Produksi T -> a         dibaca "T menghasilkan a" E -> T | T + E         dibaca "E Menghasilkan T"  atau                         "E Menghasilkan T dan E"     Simbol | menyatakan 'atau', digunakan untuk mempersingkat penulisan aturan produksi yang mempunyai ruas kiri yang sama. Tipe 0 / Unrestricted / Natural Language Aturan: Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variabel T...

 Pengantar Teori Bahasa dan Otomata Bahasa Bahasa bisa juga disebut sebagai rangkaian simbol-simbol yang mempunyai makna Otomata Otomata merupakan suatu sustem yang terdiri atas sejumlah state, dimana state menyatakan informasi mengenai input. Otomata juga dianggap sebagai mesin otomatis (bukkan mesin fisik) yang merupakan suatu model matematika daru suatu sistem yang menerima input dan menghasilkan output Bahasa & Otomata Hubungan di antara bahasa dan otomata adalah bahasa dijadikan sebagai input oleh suatu mesin otomata, selanjutnya mesin otomata akan membuat keputusan yang mengindikasikan apakah input itu  diterima  atau  ditolak . Misalnya, kita memiliki sebuah mesin sederhana yang menerima input kata dalam bahasa indonesia, hal ini bisa dilihat pada gambar disamping. Pada gambar disamping, bila mesin mendapat string input berikut: 1. ada : diterima 2. adu : diterima 3. add : ditolak Penjelasannya adalah: Sebuah string input diterima bila mencapai state akhir...

 Lutfi Rizky Budi Kurnianto 202131158 Teori Bahasa dan Otomata 1.     Pengantar Teori Bahasa dan Otomata Url:      https://lutfirizkybudikurniantotbo.blogspot.com/2023/06/pengantar-teori-bahasa-dan-otomata.html 2.     Hirarki Chomsky Url:      https://lutfirizkybudikurniantotbo.blogspot.com/2023/06/hirarki-chomsky.html 3.     Grammar dan Bahasa Url:      https://lutfirizkybudikurniantotbo.blogspot.com/2023/06/grammar-dan-bahasa.html 4.     Finite State Automata Deterministic (DFA):  https://lutfirizkybudikurniantotbo.blogspot.com/2023/06/deterministic-dfa.html FSA Pengantar:  https://lutfirizkybudikurniantotbo.blogspot.com/2023/06/finite-state-automatic.html   Non deterministic (NFA):  https://lutfirizkybudikurniantotbo.blogspot.com/2023/06/non-deterministic-nfa.html 5.     Ekuivalensi Antar Deterministic Finite Automata Url:      https://lutfirizky...