Sebuah bahasa dinyatakan regular jika terdapat Finite state automata yang dapat

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.

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 …

Sebuah bahasa dinyatakan regular jika diterima oleh finite state automata

Bahasa yang diterima oleh finite state automata dinyatakan / didefinisikan dengan ekspresi regular.

Ekspresi reguler memberikan suatu pola (pattern) atau template untuk / string dari suatu bahasa.

Contoh bahasa:

  • L1 = {a,aab,aaabb,aaaabbb, … }
  • L2= {w:w dan terdiri dari tepat satu huruf a dan satu huruf b }
  • L7 = {w:w = anbcn | n > 1}

Sebuah grammar G:

VN = {S}

VT= {a}

S=S

Contoh ER

-ER : ab*cc

string yang dibangkitkan : acc, abccabbcc, abbbcc,abbbcc

  • ER : 010*
  • String yang dibangkitkan :01,010,0100,01000
  • ER : a*d
  • String yang dibangkitkan : d,ad,aad,aaad
  • ER : a+d
  • string yang dibangkitkan ad,aad,aaad

Pengenalan Regular

  • 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) string  dari suatu bahasa.

Hubungan ER dengan FSA

  • Untuk setiap ER ada satu NFA dengan transisi  ε  (NFA ε-move) yang ekivalen.
  • Sementara untuk setiap DFA ada satu ER dari bahasa yang diterima oleh DFA.
  • Hubungannya dapat digambarkan sebagai berikut

Notasi Ekspresi Regular

Notasi yang digunakan untuk ER adalah :

  • * (asterisk) : bisa tidak muncul, bisa juga muncul  berhingga kali (0-n)
  • +   (SuperScript) : minimal muncul satu kali (1-n)
  • + atau U (union ): atau
  • . (konkatenasi) : titik bisa saja tidak di tuliskan
  •   misalnya: ab sama  dengan a.b

semua string yang berawal dengan string 0 atau 1, diikuti sembarang jumlah 0

Contoh ekspresi regular (ER) :

 Contoh string yang dibangkitkan : abcc, acc, abbcc, abbbcc (b bisa tidak

 muncul atau muncul sejumlah berhingga kali)

 Contoh string yang dibangkitkan : 01, 010, 0100,01000 (0 bisa tidak

 muncul atau muncul sejumlah berhingga kali)

 Contoh string yang dibangkitkan : d, ad, aad, aaad

 Contoh string yang dibangkitkan :  ad,aad, aaad,aaaad

5. ER : a*∪ b* (ingat ∪ berarti atau)

Contoh string yang dibangkitkan : a, b, aa, bb, aaa, bbb, aaaa, bbbb

Contoh string yang dibangkitkan : a, b

Contoh string yang dibangkitkan : 0, 01, 011, 0111, 01111

Language dari (0 È 1)0*

0* = {0}* à semua string yang anggotanya   simbol 0.

L = {00, 10, 000, 100, 0000, 1000, … }

Carilah seluruh string pada L((a|b)*b(a|ab)*) dengan panjang string kurang dari 4

Jawab :

{L((a|b)*b(a|ab)*) ,|x|= 4}

            L((a|b)*b(a|ab)*) : himpunan string yang mengandung paling sedikit satu substring ‘b’

Dengan jumlah string kurang dari 4, makamaksimaldari 3 digit

             0 digit= –

            1 digit = b

            2 digit = ab; ba

            3 digit = baa; aba; aab;

String pada L((a|b)*b(a|ab)*) = b;ab;ba;aab;aba;baa;

  1. Tentukan ekspresi reguler pembentuk bahasa pada ∑= {a,b,c}, yaitu
  2. L(r) = { w є ∑* | w memiliki tepat sebuah simbol ‘a’ }
  3. L(r) = { w є ∑* | w mengandung tepat 3 buah simbol ‘a’}
  4. L(r) = { w є ∑* | w mengandung kemunculan masing-masing simbol minimal satu kali}

Jawab      :

  1. L(r) = { w є ∑* | w memiliki tepat sebuah simbol ‘a’ }

Jawab  :

r = a (b|c) (b|c)*

  1. L(r) = { w є ∑* | w mengandung tepat 3 buah simbol ‘a’}

Jawab  :

r = aaa (b|c) (b|c)*

  1. L(r) = { w є ∑* | w mengandung kemunculan masing masing simbol minimal satu kali}

Jawab  :

r = abc

  1. Tentukan ekspresi reguler pembentuk bahasa pada S = {0,1}, yaitu
  2. L(r) ={ w є ∑* | w diakhiri dengan string 01 }
  3. L(r) ={ w є ∑ * | w tidak diakhiri dengan string 01 }
  4. L(r) ={ w є ∑ * | w mengandung simbol ‘0’ sebanyak genap }
  5. L(r) ={ w є ∑ * | kemunculan string ’00’ pada w sebanyak kelipatan 3 }

Jawab      :

  1. L(r) = { w Î∑* | w diakhiridengan string 01 }

Jawab : (0|1)*01, ekspresi regular diakhiri dengan 01

                  ER: 111101;00001;10101001;

  1. L(r) ={ w Î∑* | w tidak diakhiri dengan string 01 }

Jawab :ekspresi regular tidak di akhiri dengan string 01

                  ER: 1110; 0011; 0110;

  1. L(r) ={ w Î∑* | w mengandung simbol ‘0’ sebanyakgenap }

Jawab :ekspresi regular dengan mengandung 0 sebanyak genap, bisaada 2, 4 ,6, ….

Mengandung 0 sebanyak 2, ER: 1010;

                  Mengandung 0 sebanyak 4, ER : 011000; 00001;0000;

                  Mengandung 0 sebanyak 6, ER : 001001001;

  1. L(r) ={ w Î∑* | kemunculan string ’00’ pada w sebanyak kelipatan 3 }
  1. Tentukan ekspresi reguler pembentuk bahasa pada ∑ = {a,b}, yaitu L(r) = { w є ∑* | |w| mod 3 = 0 }

Jawab :

Membuat contoh ekspresi regular yang terdiri dari {a,b} dengan panjang string kelipatan 3, karna |w| mod 3 = 0.

Maka, denganpanjang string 3 = ER: aba; aab; bba; bab;….

Jika dengan panjang string 6= ER; aabbab; babbaa; abbaab;……

Jika dengan panjang string 9= ER: aababaaab; babbaabba;…..

Dan seterusnya ,…

Latihan 3.2

Buktikan kesamaan ekspresi regular berikut :

Jawab :

(a|b)*  = {ε, “a”, “b”, “aa”, “ab”, “ba”, “bb”, “aaa”, …}

Dengan diketahui a*= ε| a| aa| aaa| aaaa| …..,

Sedangkan b* = ε|b|bb|bbb|bbbb|…

Jadi(a|b)*  yang merupakan gabungan concate dari a* dan b* maka

(a|b)*  =(ε | a| b| aa| ab| ba| bb | aaa| …)

Dengan diketahui: a*= ε| a| aa| aaa| aaaa| …..,

Maka(a*|b)*    = (ε| a| aa| aaa| aaaa| …..|b)*

                        = (ε| a|b | aa|bb | aaa|bbb | aaaa| bbbb …..)

Maka terbukti, (a*|b)* = (a|b)*

Jawab :

Diketahui (a|b)*          = ε| a| b| aa| bb| aaa| bbb| ab| abb| aab| ba ….

            Dengan b* = ε| b| bb| bbb| bbbb| …..

(a|b*)= (a| ε| b| bb| bbb| bbbb| …..)

Maka (a|b*)*   = (a| ε| b| bb| bbb| bbbb| …..)*

ε| a| b| aa| bb| aaa| bbb| ab| abb| aab| ba ….

Maka terbukti, (a|b*)* = (a|b)*

Jawab : Dengan a* = ε| a| aa| aaa| aaaa| …..

  • (a b)*=  (eï(ab)ï(abab)ï…)

            maka (a* b)     = (ε b| ab| aab| aaab| aaaab| …..,)

                        = (b| ab| aab| aaab| aaaab|…)

            (a* b)* = (b| ab| aab| aaab| aaaab|…)*

                        = (eïa|b | abïaabï…)

(a* b)* a*        =(eïa|b | abïaabï…)   a*

                        = (eïa|b | abïaabï…)  (ε| a| aa| aaa| aaaa| …..)

                        = (e | a | b | aa | aaa | ab | aab | …)

  • (b a)*=  (eï(ba)ï(baba)ï…)

Maka (b a*)*   = (eï(ba)ï(baba)ï…)  *

                                    =  (eïb | a | ba ïbaaï…)

a* (b a*)*        = a*  (eïa|b | abïaabï…)

            =  (ε| a| aa| aaa| aaaa| …..) (eïb | a | ba ïbaaï…)

            = (e | a | b | aa | aaa | ab | aab | …)

Jawab  :

Dengan diketahui a* = ε| a| aa| aaa| aaaa| …..,

Dan (a a*)       = a(ε| a| aa| aaa| aaaa| …..) (ԑ|a)

                                    = (ε a| aa| aaa|aaaa|…) (ԑ|a)

                                    = (a|aa|aaa|aaaa|…) (ԑ|a)

= (ε| a| aa| aaa| aaaa| …..) =>a*

Maka terbukti, (a a*) (ԑ|a) = a*

Buatlah DFA yang ekuivalen dengan NFA disamping!

Pertama buatlah tabel transisinya

Kedua kita buat tupel dari tabel tersbut agar lebih detail

Lalu kita mulai membuat DFA nya

Dimulai dari state awal q0

State {q0} bila memperoleh input 0 menjadi state {q0, q1}.

State {q0} bila memperoleh input 1 menjadi state {q1}.

Ekivalensi Non-Deterministic Automata (NFA)  ke Deterministic Finite Automata (DFA)

State {q1} memperoleh input 0 menjadi state ∅
State {q1} bila memperoleh input 1 menjadi state {q0, q1}.

Pada state {q0,q1} awalnya belum mempunyai busur dan pada DFA,sebuah state harus mempunyai busur sebanyak himpunan inputnya,karena itu kita tentukan terlebih dahulu arah busurnya dan busurnya ada 2.

δ({q0,q1},0)  = {q0,0} ε {q1,0}

δ({q0,q1},1) = {q0,1} ε {q1,1}

Jadi arah busur pada state {q0,q1} mengarah ke state itu sendiri.

Kemudian khusus pada state himpunan kosong (Ø) hanya menerima inputan dari statenya sendiri,jadi busur pada himpunan kosong mengarah ke state himpunan kosong.

Ekivalensi Non-Deterministic Automata (NFA)  ke Deterministic Finite Automata (DFA)

Terakhir untuk menentukan final state pada DFA ini adalah dengan melihat NFA yang ekuivalen dengan DFA ini yaitu soal awal,

Kita ketahui Bahwa final state adalah q1,jadi pada DFA,final statenya adalah semua state yang ada hubungannya dengan q1 yaitu {q0,q1} dan {q1}

Ekivalensi Non-Deterministic Automata (NFA)  ke Deterministic Finite Automata (DFA)