Mesin Moore & Mesin Mealy

Perbaikan Latihan Ekuivalensi dan Ekuivalensi NFA - DFA

Latihan Ekuivalensi

Ekuivalensi Antar Deterministic Finite Automata ( Reduksi )

Ekuivalensi Antar Deterministic Finite Automata

Untuk suatu bahasa regular, kemungkinan ada sejumlah Deterministic Finite Automata yang dapat menerimanya. Perbedaannya hanyalah jumlah state yang dimiliki otomata-otomata yang saling ekuivalen tersebut. Tentu saja, dengan alasan kepraktisan, kita memilih otomata dengan jumlah state yang lebih sedikit.

Sasaran kita di sini 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 :

1. Distinguishable yang berarti dapat dibedakan.

2. Indistinguishable yang berarti tidak dapat dibedakan.

Dua DFA M1 dan M2 dinyatakan ekivalen apabila L(M1) = L(M2)

Reduksi Jumlah State Pada FSA

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

Pasangan State dapat dikelompokkan berdasarkan:

1. Distinguishable State (dapat dibedakan)

    Dua state  p dan q dari suatu DFA dikatakan indistinguishable apabila:

                δ(q,w) Î F dan  δ(p,w) Î F   atau   δ(q,w) ∉ F dan  δ(p,w) ∉ F

                untuk semua w Î S*

2. Indistinguishable State ( tidak dapat dibedakan)

    Dua state  p dan q dari suatu DFA dikatakan distinguishable jika ada string w Î S*  hingga:

                                                  δ(q,w) Î F dan  δ(p,w) ∉ F

Reduksi Jumlah State Pada FSA – Relasi

Pasangan dua buah state memiliki salah satu kemungkinan : distinguishable atau indistinguishable tetapi tidak kedua-duanya. 

Dalam hal ini terdapat sebuah relasi :

Jika         p dan q    indistinguishable,

dan         q  dan r    indistinguishable

maka      p,  r          indistinguishable 

dan         p,q,r         indistinguishable

Dalam melakukan eveluasi state, didefinisikan suatu relasi :

     Untuk Q yg merupakan himpunan semua state

• D  adalah  himpunan state-state distinguishable,  dimana D Ì Q
• N  adalah himpunan state-state indistinguishable, dimana N Ì Q
• maka     x Î N  jika  x Î Q  dan x ∉  D

Reduksi Jumlah State Pada FSA – Step

Langkah - langkah untuk melakukan reduksi ini adalah :

1. Hapuslah semua state yg tidak dapat dicapai dari state awal  (useless state)
2. Buatlah semua pasangan state (p, q) yang distinguishable, dimana p Î  F dan q ∉ F. Catat semua pasangan-pasangan state tersebut.
3. Cari state lain yang distinguishable dengan aturan:                                                              Untuk semua (p, q) dan semua a Î ∑, hitunglah  δ (p, a) = p_a dan δ (q, a) = q_a  . Jika pasangan (p_a, q_a) adalah pasangan state yang distinguishable maka pasangan (p, q) juga termasuk pasangan yang distinguishable.
4. Semua pasangan state yang tidak termasuk sebagai state yang distinguishable merupakan state-state indistinguishable.
5. Beberapa state yang indistinguishable dapat digabungkan menjadi satu state.
6. Sesuaikan transisi dari state-state gabungan tersebut.

Reduksi Jumlah State Pada FSA - Contoh

                              Sebuah Mesin DFA

1. State  q5 tidak dapat dicapai dari state awal dengan jalan apapun (useless state).  Hapus state q5

2. Catat state-state distinguishable, yaitu :                                                                                    

• q4 Î F sedang q0, q1, q2, q3 ∉ F sehingga pasangan                                                              
• (q0, q4) (q1, q4) (q2, q4) dan (q3, q4) adalah distinguishable.

3. Pasangan-pasangan state lain yang distinguishable diturunkan berdasarkan pasangan dari langkah 2, yaitu :                                                                                                                                

• Untuk pasangan (q0, q1)                                                                                                      

          δ(q0, 0) = q1   dan   δ(q1, 0) = q2   à  belum teridentifikasi                                                                     δ(q0, 1) = q3   dan   δ(q1, 1) = q4   à  (q3, q4) distinguishable   

          maka         (q0, q1) adalah distinguishable.                                                                                               

• Untuk pasangan (q0, q2)

          δ(q0, 0) = q1   dan   δ(q2, 0) = q1   à  belum teridentifikasi 

          δ(q0, 1) = q3   dan   δ(q2, 1) = q4   à  (q3, q4) distinguishable                     

          maka         (q0, q2) adalah distinguishable.

4. Setelah diperiksa semua pasangan state  maka terdapat state-state yang distinguishable : (q0,q1), (q0,q2), (q0,q3),  (q0,q4), (q1,q4),  (q2,q4), (q3,q4). Karena berdasarkan relasi-relasi yang ada, tidak dapat dibuktikan (q1, q2), (q1, q3) dan (q2, q3) distinguishable,  sehingga disimpulkan pasangan-pasangan state tersebut indistinguishable.

5. Karena q1 indistinguishable dengan q2,  q2 indistinguishable dengan q3, maka dapat disimpulkan q1, q2, q3 saling indistinguishable dan dapat dijadikan satu state.

6. Berdasarkan hasil diatas  maka hasil dari DFA yang direduksi menjadi:

PERTEMUAN 5 & 6 TENTANG NFA DAN DFA

Definisi Otomata

Otomata adalah Suatu bentuk/model matematika yang memiliki fungsi-fungsi dari komputer digital yaitu :

1. menerima input,
2. menghasilkan output
3. bisa memiliki penyimpanan sementara
4. mampu membuat keputusan dalam mentransformasikan input ke output

Otomata terdiri dari sejumlah berhingga state (kedudukan). Perpindahan state satu ke yang lain berdasar input dan fungsi transisi. Otomata membuat keputusan apakah input diterima atau tidak.

Contoh 1 :  

Memiliki 6 state: q0, q1, q2, q3, q4, q5
State awal: q0 ditandai dengan panah masuk tanpa state sebelumnya
State akhir: {q3. q4} ditandai dengan lingkaran dobel
Himpunan input: {a, d, u}

Q = {q0, q1, q2, q3, q4, q5}
Σ = {a, d, u}
S = q0

F = {q3, q4}
δ = fungsi transisi
δ(q0, a) = q1
δ(q1, d) = q2
δ(q2, a) = q3
δ(q2, u) = q4
δ(q2, d) = q5

Contoh 2: Mesin jaja Definisi formal FSA

 

Q = {q0, q5, q10, q15, q20, q25}
Σ = {5, 10, 15}
S = q0

F = {q25}
δ = fungsi transisi
δ(q0, 5) = q5

δ(q0, 25) = q25

δ(q0, 10) = q10

δ(q5, 5) = q10

δ(q5, 10) = q15

δ(q10, 5) = q15

δ(q10, q10) = q20

δ(q15,10) = q25

δ(q15, 5) = q20

δ(q20, 5) = q25

 

 

DEFINISI FORMAL FSA

M = (Q,Σ,δ,S,F) di mana :
Q = himpunan state
Σ = abjad, himpunan simbol input/masukan
δ = fungsi transisi, δ : Q x Σ à Q
S = state awal / initial state
F = himpunan state akhir/final state

JENIS FSA

• Deterministik (DFSA/DFA) Pada setiap input, hanya ada satu keadaan (state) tujuan dari keadaan saat ini.
• Nondeterministik (NFSA/NFA)
  pada setiap input terdapat lebih dari satu keadaan tujuan dari keadaan saat ini.
  
  

Deterministic Finite Automata(DFA)
Dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima

D-FSA/DFA

• Himpunan keadaan (Q).
• Himpunan simbol input (S)
• Fungsi transisi (d), memuat satu keadaan asal dan satu simbol input dan satu keadaan tujuan. Keadaan awal (q0)merupakan salah satudari Q.
• Himpunan keadaan final atau yang diterima, dinotasikan dengan F (FÍQ)

5-TUPLE D-FSA

DFSA A, terdiri atas 5 tuple, yaitu:

A = (Q, S,d, q0, F)

Notasi Lain DFSA

1. Diagram Transisi / State Diagram

• Tiap keadaan merupakan simpul
• Tiap keadaan q Î Q dan tiap simbol a Î S, dituliskan sebagai d(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 keadaan q dan isi dari kolom input a menunjukkan keadaan d

Contoh:

DFSA yang dapat menerima string berakhiran 01

A = ({q0, q1, q2}, {0,1}, d, q0, {q2})

dengan fungsi transisi d diberikan dalam bentuk tabel:

Contoh DFSA :
M = (Q, S, d, s, F), dimana :

Q = {q0, q1},
S = {a,b},
S = q0,
F = {q0}

 

 

 

 

 

 

 

Jika M diberi input aabba,dengan state awal (q0,aabba),maka :
(q0,aabba) ├M (q0,abba)
├M (q0,bba)
├M (q1,ba)
├M (q0,a)
├M (q0,e)

Karena (q0,aabba) ├*M (q0,e),jadi aabba diterima oleh M

Contoh: DFSA yang dapat menerima semua string berakhiran 01

Contoh : diberikan input pada mesin DFSA 110111, lakukan tracer :
(q0,110111) ├M (q0,10111)
├M (q0,0111)
├M (q1,111)
├M (q1,11)
├M (q1,1)
├M (q1,e)

Karena berhenti bukan di q2, maka 110111 tidak diterima oleh mesin DFSA

Contoh: DFSA yang dapat menerima semua string berakhiran 01

 

 

 

Contoh : diberikan input pada mesin DFSA 10110, lakukan tracer :
(q0,10110) ├M (q0,0110)
├M (q1,110)
├M (q1,10)
├M (q1,0)
├M (q2,e)
Karena berhenti di q2, maka 10110 diterima oleh mesin DFSA

DFA nya
Q = {q0 , q1 , q2 , q3 }
S = {0,1}
S = q0
F = { q0}

Contoh : diberikan string 011 dan 1010, buktikan bahwa string tersebut diterima atau ditolak !
d(q0,011) = d(q2,11) = d(q3,1) = q2 Ditolak
d(q0,1010)                 = d(q1,010)
                                   = d(q3,10)
                                   =d(q2,0)
                                   = d(q0,e) Diterima

Contoh Soal: DFA

Σ = {0,1}

Q = {a, b, c, d}

S = {a}

F = {b, c}

Fungsi transisi δ : Q x Σ à Q, yang didefinisikan sebagai :

δ = {((a,0),b), ((a,1),d), ((b,0),c), ((b,1),d), ((c,0),d), ((c,1),c), ((d,0),a), ((d,1),b)}

Fungsi transisi dapat ditulis dalam bentuk tabel

 

FINITE STATE OTOMATA

A. PENGERTIAN

FSA (Finite State Automata) merupakan tool yang sangat berguna dalam perancangan lexical analyzer, yaitu bagian dari kompilator yang mengelompokan karakter-karakter ke dalam sebuah token, yang berupa unit terkecil seperti nama, variabel, dan keyword. FSA dipakai untuk penganalisa leksikal dan dipakai juga dalam text editor, pemrosesan teks, dan program file-searching

FSA dapat juga sebagai :

• Model matematika suatu sistem yang menerima input dan output diskrit
• Mesin automata dari bahasa Regular
• Tidak memiliki tempat penyimpanan sehingga kemampuan mengingat terbatas (contoh: elevator/lift)
• Aplikatif - berguna untuk merancang sistem
  nyata.
• Aplikasi meliputi : analisis leksikal, text-editor, protokol komunikasi jaringan (kermit) dan parity checker (pengecek parity).

FSA atau AH (Automata Hingga) didefinisikan sebagai pasangan 5 tupel à M = (Q, ∑, δ, S, F).

1. Q : himpunan hingga state
2. ∑ : himpunan hingga simbol input (alfabet)
3. δ : fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input. Fungsi transisi ini biasanya diberikan dalam bentuk tabel.
4. S Î Q : state AWAL
5. F Í Q : himpunan state AKHIR

 

 

Mesin ini memiliki 6 state (q0,q1,q2,q3,q4,q5). State awal q0, q3 dan q4 adalah state akhir, sedangkan simbol input adalah (a,d,u)


CONTOH

Contoh : FSA untuk mengecek parity ganjil

Q ={Gnp, Gjl}

∑ = {0,1}

TABEL TRANSISI

S = Gnp, F = {Gjl}

CONTOHGjl Gjl Gnp
Seorang petani dengan seekor serigala, kambing dan seikat rumput berada pada suatu sisi sungai. Tersedia hanya sebuah perahu kecil yang hanya dapat dimuati dengan petani tersebut dengan salah satu serigala, kambing atau rumput. Petani tersebut harus menyeberangkan ketiga bawaannya kesisi lain sungai. Tetapi jika petani meninggalkan serigala dan kambing pada suatu saat, maka kambing akan dimakan serigala. Begitu pula jika kambing ditinggalkan dengan rumput, maka rumput akan dimakan oleh kambing. Mungkinkah ditemukan suatu cara untuk melintasi sungai tanpa menyebabkan kambing atau rumput dimakan.

 

 

 

 

 

Tugas Teori Bahasa & Otomata

Tugas Teori Bahasa & Otomata

GRAMMAR DAN BAHASA

PENGERTIAN GRAMMAR

Grammar adalah sebagai kumpulan dari himpunan-himpunan variabel, simbol-simbol 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 simbol-simbol ruas kanan aturan produksi. Simbol-simbol tersebut dapat berupa simbol terminal (Vt) atau simbol NON-Terminal (Vn)/Variabel.

Simbol Vn adalah simbol yang masih dapat diturunkan, biasanya identik dengan huruf besar (‘A’,’B’,’C’).

Simbol Vt adalah simbol yang sudah tidak dapat diturunkan lagi, biasanya identik dengan huruf kecil (‘a’,’b’,’c’).

Dengan menerapkan aturan produksi, suatu grammar bisa menghasilkan sejumlah string.

Contoh aturan produksi :

E à T | T+E | T * E
T à a

Dari aturan produksi di atas, menghasilkan suatu variabel a atau variabel ekspresi a+a atau a*a

E à T
T à a

E à T+E
E à a+T
E à a+a

E à T*E
E à a*T
E à a*a

Grammar G didefinisikan sebagai pasangan 4 tuple : VT , VN , S, dan Q, dan dituliskan sebagai G(V_T , V_N, S, Q), dimana :

1. V_T   : himpunan  simbol-simbol  terminal   (atau  himpunan token-token, atau alfabet)
2. V_N   : himpunan simbol-simbol non terminal
3. S Є V_N   : simbol awal (atau simbol start)
4. Q  : himpunan produksi

Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (α → β), Noam Chomsky mengklasifikasikan 4 tipe grammar :

• Grammar tipe ke-0 : Unrestricted Grammar (UG)

           Ciri : α, β Є (V_T | V_N )*, |α|> 0 atau |α|> |β|

• Grammar tipe ke-1 : Context Sensitive Grammar (CSG)

            Ciri : α, β Є (V_T | V_N )*, 0 < |α| ≤ |β|