Sebuah bahasa dinyatakan regular jika terdapat finite state automata yang dapat menerimannya

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to upgrade your browser.

Ekspresi Regular dan Hubungannya dengan FSA

Hubungan FSA dengan ER Sebuah bahasa dinyatakan regular jika terdapat finite state automata yang dapat menerimanya. Bahasa-bahasa yang diterima oleh FSA bisa dinyatakan secara sederhana dengan ekspresi regular (regular expression). Ekspresi regular memberikan suatu pola (pattern) atau template untuk untai/string dari suatu bahasa.

Contoh Finite State Automata untuk mengenal bilangan bulat /integer tidak bertanda Misal : 0..9 disimbolkan sebagai digit, maka ERnya adalah : (digit)(digit)*

Notasi ER * :berarti bisa tidak muncul, bisa juga muncul berhingga kali (0-n) + : berarti minimal muncul satu kali (1-n) + : berarti union/ atau bisa diganti dengan notasi  . : berarti konkatenasi, biasanya tanpa ditulis titiknya, misal ab sama dengan a.b

Contoh ER ER : ab*cc acc, abcc, abbcc, abbbcc, dst ER : 010* 01, 010, 0100, 01000, dst ER : a+d ad, aad, aaad, aaaad, dst ER : a*  b* a, b, aa, bb, dst ER : 01*+0 0, 01, 011, dst

Hubungan ER dan FSA

Contoh ER : 010* ER : 0 (1 U 0) ER : 0 (1 U 0)* ER : 01*0 ER : 0*10* ER : a* ER : a(ba)*

Latihan Buatlah FSA dari ER: 1) c * (a  bc)* 2) 10 + (0 + 11) 0*1

Teori Bahasa dan Automata Ekspresi Regular Ekuivalensi Non Deterministic Finite Automata ke Deterministic Finite Automata

Ekspresi Regular – Introduction Sebuah bahasa dinyatakan regular jika terdapat finite state automata yang dapat menerimanya Bahasa-bahasa yang diterima oleh suatu finite state automata bisa dinyatakan secara sederhana dengan ekspresi regular (regular expression)  ER. Memberikan suatu pola (pattern) atau template untuk string dari suatu bahasa String yang menyusun suatu bahasa regular akan cocok (match) dengan pola bahasa itu Penerapan ekspresi regular yang tampak misalnya string search pada suatu file, biasanya fasilitas ini ada pada text editor.

Ekspresi Regular – Introduction Contoh : Suatu field masukan hanya menerima input bilangan (0..9). q1 q0 q2 0,1,2,…9 0,1,…9 selain FSA menerima bilangan integer tak bertanda Ekrspresi Regular yang dihasilkan adalah (digit) (digit)* dengan digit 0..9

Ekspresi Regular – Introduction ER juga dapat diaplikasikan untuk melakukan analisis leksikal dalam sebuah kompilator. Yaitu mengidentifikasikan unit-unit leksikal (token) yang dikenal dalam program. Token-token pada suatu bahasa pemrograman kebanyakan tanpa kecuali dinyatakan sebagai sebuah ER . Contoh: Suatu identifier baik huruf besar atau huruf kecil yang kemudian diikuti huruf atau digit, dengan tanpa pembatasan jumlah panjang bisa dinyatakan sebagai: (huruf)(huruf+digit)* q1 q0 huruf atau digit huruf

Notasi ER Terdapat 5 notasi dalam ER yaitu: ‘*’ , ‘+’ , ‘+’ , ‘’ , ‘.’ * (karakter asterisk), berarti bisa tidak muncul, bisa juga muncul berhingga kali (0-n) + (pada posisi superscript/ diatas) berarti minimal muncul satu kali (1-n) + atau  berarti union . (titik) berarti konkatensi, biasanya titik bisa dihilangkan, misal ab bermakna seperti a.b

Notasi ER - Contoh ER: ab*cc Contoh string: abcc, abbcc, abbbcc, abbbbcc, acc, (b bisa tidak muncul atau muncul sejumlah berhingga kali) ER: 010* Contoh string : 01, 010, 0100, 01000 (jumlah 0 diujung bisa tidak muncul, bisa muncul berhingga kali) ER: a*d Contoh string : d, ad, aad, aaad ER: a+d Contoh string: ad, aad, aaad --- (a minimal muncul sekali)

Notasi ER -Contoh ER: a*b* (ingat ‘’ berarti atau) Contoh string : a, b, aa, bb, aaa, bbb, aaaa, bbbb ER: (ab) --- Contoh string: a, b ER: (ab)* Contoh string : a, b, ab, ba, abb, bba, aaaa, bbbb (string yang memuat a atau b) ---- * perhatikan : notasi ‘’ kadang dituliskan juga sebagai ‘+’ --- ER: 01*+0 Contoh string: 0, 01, 011, 0111, 01111, (string yang berawalan dengan 0, dan selanjutnya boleh diikuti deretan 1)

Konstruksi NFA Dari ER Yang Ditentukan q2 q0 q1 b a q0 q1 0,1 NFA untuk ER: ab q1 q0 q2 a b untuk ER: 0 (10)* NFA untuk ER: a b

Ekuivalensi NFA ke DFA Dari sebuah mesin Non-deterministic Finite Automata dapat dibuat mesin Deterministic Finite Automata-nya yang ekivalen (bersesuaian) Ekivalen disini artinya mampu menerima bahasa yang sama  L(M1) = L(M2) q2 q1 q0 1 0,1 q1 q0 0,1

Ekuivalensi NFA ke DFA – Steps Membuat tabel transisi Mulai dari state awal Ikuti transisinya untuk membentuk state-state baru Untuk setiap state yang terbentuk diikuti lagi transisinya sampai ter’cover’ semua

Ekuivalensi NFA ke DFA – Contoh q1 q0 0,1 1 Mesin otomata NFA Buat Tabel Transisi  1 q0 q0, q1 q1 q1 

Ekuivalensi NFA ke DFA – Contoh Mulai dari state awal (q0) q0 Telusuri state berikutnya state q0 bila memperoleh input 0 menjadi state q0, q1 state q0 bila memperoleh input 1 menjadi state q1 q0, q1 q0 q1 1 Hasil dari penelusuran q0 * Setiap state dituliskan sebagai himpunan state

Ekuivalensi NFA ke DFA – Contoh Ikuti transisinya untuk membentuk state-state baru state q1 bila memperoleh input 0 menjadi state  state q1 bila memperoleh input 1 menjadi state q0, q1 state q0, q1 bila memperoleh input 0 menjadi state q0, q1, ini di peroleh dari  (q0,0)= q0, q1 di gabung dengan  (q1,0) =, maka hasilnya  (q0, q1, 0) =q0, q1 state q0, q1 bila memperoleh input 1 menjadi state q0, q1, ini di peroleh dari  (q0,1)= q1 di gabung dengan  (q1,1) = q0, q1, maka hasilnya  (q0, q1, 1) = q0, q1 * Setiap state dituliskan sebagai himpunan state

Ekuivalensi NFA ke DFA – Contoh q0, q1 q0 q1 1  0,1 Hasil setelah penusuran q1 dan q0, q1 *  merupakan sebuah state Telusuri state  State  menerima input 0 atau 1 menjadi state , atau  (,1)=  q0, q1 q0 q1 1  0,1

Ekuivalensi NFA ke DFA – Contoh Dari NFA, kita tahu bahwa himpunan state akhjr adalah q1, maka pada DFA yg dihasilkan state-state akhir merupakan semua state yg mengandung q1. F = {{q1 }, {q0, q1 }} q0 1  0,1 q1 q0, q1 Mesin DFA yang ekivalen dengan NFA

Ekuivalensi NFA ke DFA – Contoh Pembuktian : String ‘001’ Dari diagram NFA kita bisa lihat bahwa ∂(q0,001) dapat diterima oleh NFA tsb. Untuk DFA kita lihat: ∂(q0,001) = ∂(q0, q1,01)= ∂ (q0, q1,1)= q0, q1 Karena state q0, q1 termasuk state akhir, maka berarti string tersebut diterima.

Sebuah bahasa dinyatakan regular jika terdapat finite state automata yang dapat menerimanya. Bahasa-bahasa yang diterima oleh FSA bisa dinyatakan secara sederhana dengan ekspresi regular (regular expression). Ekspresi regular memberikan suatu pola (pattern) atau template untuk untai/string dari suatu bahasa.

5 Otomata merupakan suatu sistem yang terdiri atas sejumlah berhingga state di mana state menyatakan informasi mengenai?

Automata merupakan suatu sistem yang terdiri atas sejumlah berhingga state, dimana state menyatakan informasi mengenai input yang lalu, dan dapat juga dianggap sebagai memori mesin. Input pada mesin automata dianggap sebagai bahasa regular yang harus dikenali oleh mesin.

Apa perbedaan DFA dan NFA?

Perbedaan di antara keduanya adalah bahwa DFA menerima sebuah input Page 2 STRING (Satuan Tulisan Riset dan Inovasi Teknologi) p-ISSN: 2527 – 9661 Vol. 5 No. 1 Agustus 2020 e-ISSN: 2549 – 2837 29 dimana state tujuan dari input tersebut adalah satu, sedangkan NFA dapat menuju beberapa state tujuan untuk input yang sama.

Suatu FSA dimana keputusannya terbatas pada diterima atau ditolak disebut dengan?

Suatu keterbatasan dari FSA yang sudah dipelajari sebelumnya adalah: keputusannya terbatas pada diterima atau ditolak. Otomata tsb biasa disebut dengan accepter (dalam hal ini FSA).

Apa yg dimaksud dengan Distinguishable dan Indistinguishable?

1. Distinguishable yang berarti dapat dibedakan. 2. Indistinguishable yang berarti tidak dapat dibedakan.

Apakah yang dimaksud dengan FSA?

Finite State Automata/otomata berhingga state, selanjutnya disebut sebagai FSA yaitu suatu model matematika dari suatu sistem yang menerima input dan output diskrit. FSA merupakan mesin otomata dari bahas regular.

7 Apa yang Anda ketahui dari Finite State Automata?

Finite automata adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata di mana sistem dapat berada di salah satu dari sejumlah berhingga konfigurasi internal disebut state.

Apa yang dimaksud dengan Moore State Machine?

Dalam teori komputasi sebagai prinsip dasar komputer, mesin Moore adalah otomasi fase berhingga (finite state automaton) di mana keluarannya ditentukan hanya oleh fase saat itu (dan tidak terpengaruh oleh bagian masukan/input).

Apa itu untai string?

1.2 Untai (String) Untai, kadang-kadang disebut kata atau word, adalah barisan berhingga simbol-simbol yang berasal dari suatu alfabet.

Bagaimana cara kerja Finite State Automata FSA?

Prinsip kerja Finite State Automata adalah sebagai berikut: (1) Menerima input string, (2) Membaca (menyerap substring) karakter awal dengan kontrol berada pada state awal, (3) Dengan kontrol dan karakter awal yang telah dibaca, state akan berpindah ke state baru, (4) Proses berlanjut sampai semua string terserap habis …