finite state automata deterministic finite automata · definisi finite state automata • model...
TRANSCRIPT
Finite State AutomataDeterministic Finite Automata
©B.Very Christioko, S.Kom
Definisi Finite State Automata
• Model matematika yang dapat menerima inputdan mengeluarkan output
• Memiliki state yang berhingga banyaknya dandapat berpindah dari satu state ke statelainnya 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, pencekparity.
©B.Very Christioko, S.Kom
Contoh
©B.Very Christioko, S.Kom
Misal input : 1101Genap 1 Ganjil 1 Genap 0 Genap 1 Ganjil diterima mesin
Misal input : 1100Genap 1 Ganjil 1 Genap 0 Genap 0 Genap ditolak mesin
Syarat diterima / ditolak
Syarat string diterima:• Seluruh simbol selesai diinputkan dan berhenti
pada state akhir(final).
Syarat string ditolak:• Seluruh simbol selesai diinputkan dan berhenti
pada state bukan akhir(final).• Simbol belum selesai diinputkan tetapi sudah
berhenti (macet) pada state tertentu (baik statefinal/bukan final)
• Finite State Automata dinyatakan oleh5 tuple M=(Q , Σ , δ , S , F )▫ Q = himpunan state▫ Σ = himpunan simbol input▫ δ = fungsi transisi δ : Q × Σ▫ S = state awal / initial state , S ∈ Q▫ F = state akhir, F ⊆ Q
©B.Very Christioko, S.Kom
Contoh diatas,• Q = {Genap, Ganjil}• Σ = {0,1}• S = Genap• F = {Ganjil }
©B.Very Christioko, S.Kom
Deterministic Finite Automata (DFA)
• Deterministic Finite Automata (DFA) : darisuatu state ada tepat satu state berikutnyauntuk setiap simbol masukan yang diterima
• Contoh : Pengujian untuk menerima bit stringdengan banyaknya 0 genap, serta banyaknya 1genap.▫ 0011 : diterima.▫ 10010 : ditolak, karena banyaknya 0 ganjil
©B.Very Christioko, S.Kom
• Diagram transisi-nya :
©B.Very Christioko, S.Kom
• DFA nyaQ = {q 0 , q 1 , q 2 , q 3 }Σ = {0,1}S = q 0F = { q 0 }
• fungsi transisi:
δ( q0 ,011)= δ( q2 ,11) =δ( q3 ,1)= q2 Ditolakδ( q0 ,1010)= δ( q1 ,010) =δ( q3 ,10)=δ( q2 ,0)= q0 Diterima
©B.Very Christioko, S.Kom
Contoh Kasus
• Slide Sri Handayaningsih, S.T., M.T. - FormalLanguages Finite Automata (klik disini)
©B.Very Christioko, S.Kom
Latihan:
• Buku “Teori Bahasa dan Otomata” FirrarUtdirartatmo, Bab 2 halaman 33.
• Soal 1▫ Soal 5a▫ Soal 5b▫ Soal 5c
• Soal 2▫ Soal 6a▫ Soal 6b▫ Soal 6c
©B.Very Christioko, S.Kom
δ( q0 ,011)= δ( q2 ,11) =δ( q3 ,1)= q2 Ditolakδ( q0 ,1010)= δ( q1 ,010) =δ( q3 ,10)=δ( q2 ,0)=
q0 Diterima