Tugas TEKNIK BAHASA DAN OTOMATA

Finite State Automata (FSA)

♦ model matematika yang dapat menerima input dan mengeluarkan output
♦ Memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasar input dan fungsi transisi
♦ Tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.
♦ Mekanisme kerja dapat diaplikasikan pada : elevator, text editor, analisa leksikal, pencek parity.

Contoh pencek parity ganjil



Misal input : 1101
Genap 1 Ganjil 1 Genap 0 Genap 1 Ganjil
diterima mesin
Misal input : 1100
Genap 1 Ganjil 1 Genap 0 Genap 0 Genap
ditolak mesin
Def 1. Finite State Automata dinyatakan oleh 5 tuple
M=(Q , Σ , δ , S , F )
Q = himpunan state
Σ = himpunan simbol input 6
δ = fungsi transisi δ : Q × Σ
S = state awal / initial state , S ∈ Q
F = state akhir, F ⊆ Q
Contoh diatas,
Q = {Genap, Ganjil}
Σ = {0,1}
S = Genap
F = {Ganjil }




atau δ(Genap,0) = Genap
δ(Genap,1) = Ganjil
δ(Ganjil,0) = Ganjil
δ(Ganjil,1) = Genap

Jenis FSA
Deterministic Finite Automata (DFA) : dari suatu state ada tepat satu state berikutnya
untuk setiap simbol masukan yang diterima
Non-deterministic Finite Automata (NFA) : dari suatu state ada 0, 1 atau lebih state
berikutnya untuk setiap simbol masukan yang diterima
Deterministic Finite Automata
♦ Contoh : pengujian parity ganjil.
♦ Contoh lain : Pengujian untuk menerima bit string dengan banyaknya 0 genap,
serta banyaknya 1 genap.
♦ 0011 : diterima.
♦ 10010 : ditolak, karena banyaknya 0 ganjil
♦ Diagram transisi-nya :

♦ DFA nya
Q = {q0 , q1 , q2 , q3 }
Σ = {0,1}
S = q0
F = { q0}
fungsi transisi

δ( q0,011)= δ( q2,11) =δ( q3,1)= q2 Ditolak
δ( q0,1010)= δ( q1,010) =δ( q3,10)=δ( q2,0)= q0 Diterima
♦ Contoh lain DFA : Variabel dalam bahasa pascal diawali oleh huruf (besar/kecil),
dan diikuti dengan huruf atau angka.



♦ Contoh DFA lainnya :



















Nondeterministic Finite Automata (NFA)

♦ Perbedaan dengan NFA: fungsi transisi dapat memiliki 0 atau lebih fungsi transisi
♦ G = ({q0 , q1 , q2 , q3, q4 }, {0,1}, δ , q0 , { q2 , q4}}

♦ String diterima NFA bila terdapat suatu urutan transisi berdasar input, dari state awal ke state akhir.
♦ harus mencoba semua kemungkinan.





♦ Contoh : string 01001
Def 2. Dua buah FSA disebut ekuivalen apabila kedua FSA tersebut menerima bahasa
yang sama
Contoh : FSA yang menerima bahasa {an | n≥0 }


Def 3. Dua buah state dari FSA disebut indistinguishable (tidak dapat dibedakan)
apabila :
δ(q,w)∈F sedangkan δ(p,w)∉F dan
δ(q,w) ∉F sedangkan δ(p,w) ∈F untuk semua w ∈ Σ*
Def 4. Dua buah state dari FSA disebut distinguishable (dapat dibedakan) bila terdapat
w ∈ Σ* sedemikian hingga:
δ(q,w)∈F sedangkan δ(p,w)∉F dan
δ(q,w) ∉F sedangkan δ(p,w) ∈F untuk semua w ∈ Σ*

Prosedur menentukan pasangan status indistinguishable
1. Hapus semua state yang tak dapat dicapai dari state awal.
2. Catat semua pasangan state (p,q) yang distinguishable, yaitu {(p,q) | p ∈ F ∧ q ∉ F}
3. Untuk setiap pasangan (p,q) sisanya,
untuk setiap a∈ Σ, tentukan δ(p,a) dan δ(q,a)
Contoh
1. Hapus state yang tidak tercapai -> tidak ada
2. Pasangan distinguishable (q0,q4), (q1,q4), (q2,q4), (q3,q4).
3. Pasangan sisanya (q0,q1), (q0,q2), (q0,q3), (q1,q2) (q1,q3) (q2,q3)

Catatan : jumlah pasangan seluruhnya :

Prosedur Reduksi DFA
1. Tentukan pasangan status indistinguishable.
2. Gabungkan setiap group indistinguishable state ke dalam satu state dengan relasi pembentukan group secara berantai : Jika p dan q indistingishable dan jika q dan r indistinguishable maka p dan r indistinguishable, dan p,q serta r indistinguishable semua berada dalam satu group.
3. sesuaikan transisi dari dan ke state-state gabungan.
Contoh
1. pasangan status indistinguishable (q1,q2), (q1,q3) dan (q2,q3).
2. q1,q2,q3 ketiganya dapat digabung dalam satu state q123
3. Menyesuaikan transisi, sehingga DFA menjadi








Ekuivalensi NFA-DFA

♦ Ada apa dengan NFA ? konsep yang sulit diimplemen-tasikan. Komputer
sepenuhnya deterministic.
♦ Kenapa dipelajari ? Lebih dekat ke sistem nyata
♦ Contoh : permainan catur, banyak alternatif pada suatu posisi tertentu ->
nondeterministic
♦ Non deterministik dapat menyelesaikan problem tanpa backtrack, namun dapat
diekuivalensikan ke DFA.
Algoritma
1. Buat semua state yang merupakan subset dari state semula. jumlah state menjadi 2Q
2. Telusuri transisi state–state yang baru terbentuk, dari diagram transisi.
3. Tentukan state awal : {q0}
4. Tentukan state akhir adalah state yang elemennya mengandung state akhir.
5. Reduksi state yang tak tercapai oleh state awal.
Contoh Ubahlah NFA berikut menjadi DFA
M={{q0,q1}, {0,1}, δ, q0,{q1}} dengan tabel transisi

1. State yang akan dibentuk : {}, {q0} {q1},{q0,q1}
2. Telusuri state

3. State awal : {q0}
4. State akhir yang mengandung q1, yaitu {q1},{q0,q1}









Contoh : Ubahlah NFA berikut menjadi DFA
M={{q0,q1 ,q2}, {p,r}, δ, q0,{q1}} dengan tabel transisi

1. State yang akan dibentuk : {}, {q0} {q1},{q2}, {q0,q1}, {q0,q2}, {q1,q2}, {q0,q1,q2}

2. Telusuri state:

3. State awal : {q0}
4. State akhir yang mengandung q1, yaitu {q1},{q1,q2}



5. Reduksi {q0,q1}{q0,q2}{q0,q1,q2 } sehingga FSA menjadi
NFA dengan ε-move
Def 1. ε-move adalah suatu transisi antara 2 status tanpa adanya input. Contoh gambar :
transisi antara status q1 ke q3
Def 2. ε-closure adalah himpunan state yang dapat dicapai dari suatu state tanpa adanya input. Contoh gambar :
ε-closure(q0) = [q0,q1,q3]
ε-closure(q1) = [q1,q3]
ε-closure(q3) = [q3]

Ekuivalensi NFA dengan ε-move ke NFA
tanpa ε-move
1. Buat tabel transisi NFA dengan ε-move
2. Tentukan ε-closure setiap state
3. Carilah fungsi transisi /tabel transisi yang baru, rumus :
δ’(state,input)=ε-closure(δ(ε-closure(state,input))
4. Tentukan state akhir ditambah dengan state yang ε-closure nya menuju state akhir,
rumusnya 14
F’ = F ∪ {q | (ε-closure(q) ∩ F ≠ ∅}
Contoh
Tabel transisi-nya

ε-closure dari FSA tersebut
ε-closure(q0) = [q0,q1]
ε-closure(q1) = [q1]
ε-closure(q2) = [q2]
ε-closure(q3) = [q3]
Cari tabel transisi yang baru (δ’) :
Hasilnya menjadi

Penggabungan FSA
Bila diketahui L1 adalah bahasa yang diterima oleh M1 dan L2 adalah bahasa yang
diterima oleh M2 maka
1. FSA M3 yang dapat menerima L1+L2 dibuat dengan cara
♦ Tambahkan state awal untuk M3, hubungkan dengan state awal M1 dan state awal M2 menggunakan transisi ε
♦ Tambahkan state akhir untuk M3, hubungkan dengan state-state akhir M1 dan state-state akhir M2 menggunakan transisi ε
2. FSA M4 yang dapat menerima L1L2 dibuat dengan cara
♦ State awal M1 menjadi state awal M4
♦ State-state akhir M2 menjadi state-state akhir M4
♦ Hubungkan state-state akhir M1 dengan state awal M2 menggunakan transisi ε
Contoh FSA M1 dan M2










FSA M3

FSA M4