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