Makalah Finite State Automata

Finite State Automata

OLEH

KELOMPOK 1

FAHMI RAHMAT AZIS

RINALDI SYARFIANTO

RAE AWALIAGUS RIDWANA

TEKNIK INFORMATIKA

FAKULTAS SAINS TEKNOLOGI

UIN SUSKA RIAU

2014/2015

KATA PENGANTAR

Assalamu’alaikum warahmatullahi wabarakatuh.

Puji dan syukur kami panjatkan ke hadirat Allah SWT atas segala berkat, rahmat, taufik, serta hidayah-Nya yang tiada terkira besarnya, sehingga penulis dapat menyelesaikan makalah dengan judul ”Finite State Automata (FSA)”. tepat pada waktunya.

Tugas ini ditujukan untuk memenuhi tugas mata kuliah Teori Bahasa dan Otomata. Dalam penyusunannya, penulis memperoleh banyak bantuan dari berbagai pihak, karena itu penulis mengucapkan terima kasih kepada Teman-teman yang telah membantu Penulis dalam menyelesaikan makalah ini .

Penulis menyadari bahwa makalah ini masih banyak kekurangan dan kelemahannya, baik dalam isi maupun sistematikanya. Hal ini disebabkan oleh keterbatasan pengetahuan dan wawasan penulis. Oleh sebab itu, penulis sangat mengharapkan kritik dan saran untuk menyempurnakan makalah ini.

Akhirnya, penulis mengharapkan semoga makalah ini dapat memberikan manfaat, khususnya bagi penulis dan umumnya bagi pembaca.

Akhir kata penulis berharap agar makalah ini bermanfaat bagi semua pembaca.

Pekanbaru,      Maret  2015

Tim Penulis

Bab 1

Pendahuluan

1.1  Latar Belakangan

Teori bahasa dan otomata merupakan salah satu mata kuliah yang wajib dijurusan-jurusan informatika maupun ilmu komputer. Diasumsikan para pembaca telah terbiasa dengan notasi-notasi yang digunakan disini, misalnya mengenai hinpunan, yang telah diperoleh dari kuliah-kuliah sebelumnya. Meskipun demikian bagi mereka diluar disiplin informatika dapat pula segera memahaminya karena telah diusahakan untuk sebisa mungkin memberikan penjelasan yang memadai untuk setiap hal baru yang disampaikan.

Dalam teori bahasa dan otomata terdapat salah satu materi berjudul Finite State Automata (FSA). Dimakalah ini kami akan fokus untuk menjelaskan berbagai hal mengenai FSA. Sub-sub dari FSA ini seperti Deterministic Finite Automata (DFA), Non- deterministic Finite Automata,ekuivalensi antar Deterministic Finite Automata,  dan reduksi jumlah State pada Finite State Automata juga akan kami jelaskan.

1.2  Rumusan Masalah

1.      Bagaimana penerapan Finite State Automata ?

2.      Jelaskan tentang Deterministic Finite Automata !

3.      Jelaskan tentang Non- deterministic Finite Automata !

4.      Jelaskan tentang ekuivalensi antar Deterministic Finite Automata !

5.      Jelaskan tentang reduksi jumlah State pada Finite State Automata !

Bab 2

Pembahasan

2.1 Penerapan Finite State Automata

            FiniteState Automata/state otomata berhingga, selanjutnya kita tersebut sebagai FSA, bukanlah mesin fisik tetapi suatu model matematika dari suatu sistem yang menerima input dan output diskrit. Finite state automata memiliki state ke state lain. Perubahan state ini dinyatakan oleh fungsi transisi. Jenis otomata ini tidak memiliki tempat penyimpanan sehingga kemampuan ‘mengingatnya’ terbatas. Mekanisme kontrol pada suatu elevator / lift adalah contoh yang bagus untuk suatu otomata. Mekanisme tersebut tidak ‘mengingat’ semua permintaan sebelumnya tetapi hanya posisi lift saat itu pada suatu lantai, pergerakan (keatas atau bawah). Dan sekumpulan permintaan yang belum terpenuhi. Dalam ilmu komputer kita akan menemui banyak contoh dari sistem finitestate automata. teori mengenai finitestate automata adalah suatu tool yang berguna untuk merancang sistem tersebut. Mekanisme kerja suatu finitestate automata bisa diaplikasikan pada analisis leksikal, text-editor, protokol komunikasi jaringan (misal protokol kermit), dan pendek pariti.

            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

δ = fungsi transisi δ : Q × Σ			S ∈ Q
S = state awal / initial state ,
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.

2.2 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 = {q₀ , q₁ , q₂ , q₃ }

Σ = {0,1}

S = q₀

F = { q₀}

 Fungsitransisi

	δ	0	1
	q0	q2	q1
	q1	q3	q0
	q2	q0	q3
δ( q0,011)= δ(	q3	q1	q2
	q2,11) =δ( q3	,1)= q2	Ditolak

δ( q₀,1010)= δ( q₁,010) =δ( q₃,10)=δ( q₂,0)= q₀     Diterima

Contoh lain DFA : Variabel dalam bahasa pascal diawali oleh huruf (besar/kecil), dan diikuti dengan huruf atau angka.

2.3 Nondeterministic Finite Automata

Perbedaan dengan NFA: fungsi transisi dapat memiliki 0 atau lebih fungsi transisi

G = ({q₀ , q₁ , q₂ , q₃, q₄ }, {0,1}, δ , q₀ , { q₂ , q₄}}

 

♦            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 {aⁿ | 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 (q₀,q₄), (q₁,q₄), (q₂,q₄), (q₃,q₄).

3.      Pasangan sisanya (q₀,q₁), (q₀,q₂), (q₀,q₃), (q₁,q₂) (q₁,q₃) (q₂,q₃)

Prosedur Reduksi FDA

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 (q₁,q₂), (q₁,q₃) dan (q₂,q₃).

2.      q₁,q₂,q₃ketiganya dapat digabung dalam satu state q₁₂₃

3.      Menyesuaikan transisi, sehingga DFA menjadi

2.4 Ekuivalensi antar Deterministic Finite Automata

            Misalkan terhadap 2 buah Deterministic Finite Automata, M1 dan M2, yang masing masing menerima bahasa L(M1) dan L(M2). Jika L(M1) = L(M2) maka 2 DFA tersebut dikatakan ekivalen. Sebagai contoh DFA M1 dan M2 memiliki diagram transisi seperti pada gambar 3.5 dan 3.6

           

2.5 Reduksi Jumlah State Pada Finite State Automata

Untuk suatu bahasa regular kemungkinan ada sejumlah DFA yang dapat menerimanya. Perbedaannya umumnya adalah pada jumlah state yang dimiliki oleh otomata-otomata yang saling ekivalen tersebut.

Tentunya secara praktis FSA dengan jumlah state yang lebih sedikit merupakan FSA yang paling efisien.

Untuk mendapatkan FSA yang efisien maka perlu dievaluasi dan direduksi jumlah state dari FSA tersebut dengan tidak mengurangi kemampuan semula dalam menerima suatu bahasa.

Setiap pasangan state didalam suatu FSA dapat dikelompokan atas :

·       indistinguishable state

·       distinguishable state

Distinguishable state adalah pasangan state yang dapat dibedakan, sedangkan indistinguishable state adalah pasangan state yang tidak dapat dibedakan.

Untuk state-state yang indistinguishable pada prinsipnya dapat digabungkan menjadi satu state. Reduksi jumlah state dapat dilakukan dengan pendekatan tersebut.

InDistinguishable State

Dua buah state p dan q dari sebuah FSA  dikatakan indistinguishable jika :

         δ (q, w) Î F    begitu pula    δ (p, w) Î F  

dan 

        δ (q, w) ÏF    begitu pula  δ (p, w) ÏF  

untuk  semua  w Î ∑*  

Distinguishable State

Dua buah state p dan q dari sebuah FSA  dikatakan distinguishable jika ada string w Î ∑*  sedemikian sehingga :

         δ (q, w) Î F       sedangkan  δ (p, w) Ï F  

Relasi-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             juga indistinguishable

maka    p, q, dan  r       indistinguishable

Dalam melakukan eveluasi state, didefinisikan suatu relasi :

            Untuk Q adalah 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

Implementasi reduksi

 

Implementasi  reduksi state dari suatu FSA dapat dilakukan sebagai berikut :

1. Hapuslah semua state tidak dapat dicapai dari state awal  (useless state)
2. Indentifikasi state-state yang indistinguishable dan gabungkan

Secara lebih detil tahapan-tahapanya adalah sebagai berikut :

1.      Hapuslah semua useless state

2.      Buatlah semua pasangan state (p, q) yang distinguishable, dimana  p Î F dan q ÏF. Catat semua pasangan-pasangan state tersebut.

3.      Untuk semua state lakukan pencarian state lainnya yang distinguishable dengan aturan:

“Untuk semua (p, q) dan semua a Î ∑, hitunglah  δ (p, a) = p_adan δ (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, adalah state-state indistinguishable.

5.      Beberapa state yang indistinguishable dapat digabungkan menjadi satu state.

6.      Sesuaikan transisi dari state-state gabungan tersebut.

Sebagai contoh adalah sebagai berikut :

Secara bertahap dilakukan reduksi sebagai berikut :

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.

·         Untuk pasangan (q0, q3)

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

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

                                                                          (q0, q3) adalah distinguishable.

·         Untuk pasangan (q1, q2)

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

δ(q1, 1) = q4   dan   δ(q2, 1) = q4   à  q4 Î F,  maka (q1,q2) mungkin

  indistinguishable.

·         Untuk pasangan (q1, q3)

δ(q1, 0) = q2   dan   δ(q3, 0) = q2   à  belum teridentifikasi  dan  q2 ÏF

δ(q1, 1) = q4   dan   δ(q3, 1) = q4   à  q4 Î F,  maka (q1,q3) mungkin

indistinguishable.

·         Untuk pasangan (q2, q3)

δ(q2, 0) = q1   dan   δ(q3, 0) = q2   à  belum teridentifikasi  dan  q1, q2 ÏF

δ(q2, 1) = q4   dan   δ(q3, 1) = q4   à  q4 Î F,  maka (q1,q2) mungkin

  indistinguishable.

Karena berdasarkan relasi-relasi yang ada, tidak dapat dibuktikan (q1, q2), (q1, q3) dan (q2, q3) distinguishable,  sehingga disimpulkan pasangan-pasangan state tersebut indistinguishable.

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

Berdasarkan langkah 1 s/d 4, dapat digambarkan DFA yang sudah direduksi statenya sebagai berikut.

Kedua mesin sebelum dan sesudah direduksi akan tetap menerima bahasa yang sama.

DAFTAR PUSTAKA

·           Utdirartatmo firrar.2005.Teori Bahasa dan Otomata.Yogyakarta:Graha Ilmu

DAPATKAN MAKALAH  FINITE STATE AUTOMATA.DOC

Share Artikel :

Facebook Twitter Google+

Berlanggan

Berlangganan posting: Daftarkan alamat email Anda untuk memperoleh umpan posting terbaru langsung ke kotak masuk pesan dari FajriAndaviar.