FINITE STATE AUTOMATA

FINITE STATE AUTOMATA (FSA)

 

"Assalamualaikum wr.wb Selamat Pagi,Siang,Sore atau malam brothers semua,kali ini saya akan membahas tentang Materi Grammar dan Bahasa pada matakuliah Teori bahasa Otomata. so check this out brothers!!"

PENGERTIAN FSA

Finite State Automata (FSA) adalah suatu mesin abstrak yang digunakan untuk merepresentasikan penyelesaian suatu persoalan dari suatu sistem diskrit. Sebagai sebuah mesin maka FSA akan bekerja jika diberikan suatu masukan. Hasil proses adalah suatu nilai kebenaran diterima atau tidaknya masukan yang diberikan. FSA memiliki state yang banyaknya berhingga, jika diberikan suatu simbol input maka dapat terjadi suatu perpindahan dari sebuah state ke state lainnya. Perubahan state tersebut dinyatakan oleh suatu simbol transisi. Mekanisme FSA tidak memiliki memori sehingga selalu mendasarkan prosesnya pada posisi state “saat ini”. Misalnya pada mekanisme kontrol pada sebuah lift, selalu didasari pada posisi lift saat itu pada suatu lantai, pergerakan ke atas atau ke bawah dan sekumpulan permintaan yang belum terpenuhi.

dalam FSA di bagi menjadi 2 jenis yaitu 

DFA (Deterministic FSA) -> memiliki hasil yang pasti

NFA (Non Deterministic FSA) -> memiliki hasil yang tidak pasti

Secara formal FSA didefinisikan dengan 5 tuple : M = (Q, Σ, δ, S, F), dimana :

Q : himpunan state/kedudukan

Σ  : himpunan simbol input

∂  : fungsi transisi

S : State awal (initial state)

F : himpunan state akhir (Final State)

Contoh FSA

 

 Contoh Soal FSA

FSA untuk mengecek parity ganjil

• Q ={Gnp, Gjl} diagram transisi
• ∑ = {0,1}

S = Gnp, F = {Gjl}

 

PENGERTIAN DFA

Deterministic Finite Automata (DFA) adalah salah satu jenis dari  Finite Automata(FA) yang berguna sebagai  pengenal bahasa regular. Karakteristik kunci dari DFA adalah tidak membolehkan membaca  satu atau lebih dari satu transisi untuk satu simbol masukan berisi String berupa  karakter/abjad yang sama.Dengan kata lain untuk memasukan simbol yang sama DFA tidak bisa mentransisikannya ke  beberapa state yang berbeda.Jika digunakan tabel transisi untuk merpresentasikan fungsi transisi DFA,maka masing-masing isian di tabel transisi adalah   satu state tunggal (berhingga) dan dapat berpindah ke state  lain berdasarkan input dan fugnsi transisi. Konsekuensinya,pada DFA lebih dapat menentukan apakah suatu string masukkan diterima,karena hanya terdapat paling banyak satu jalur dari state awal.

 

Mesin DFA

A deterministic finite automaton (DFA) M = (Q, Σ, δ, S, F), dimana :

Q : himpunan state/kedudukan

Σ  : himpunan simbol input

∂  : fungsi transisi, dimana ∂ € Q x Σ -> Q

S  : State awal (initial state)

F : himpunan state akhir (Final State)

Contoh Soal

Q = {q0, q1, q2}  
δ diberikan dalam tabel berikut :

Kalimat yang diterima oleh DFA : a, b, aa, ab, ba, aba, bab, abab, baba
Kalimat yang dittolak oleh DFA  : bb, abb, abba

PENGERTIAN NFA

Nondeterministic Finite Automata (NFA) adalah salah satu bagian dari otomata berhingga atau Finite State Automata (FSA). Pada Nondeterministic Finite Automata (NFA) dimungkinkan satu simbol menimbulkan transisi ke lebih dari satu kondisi dan memberikan beberapa kemungkinan gerakan sehingga keluarannya tidak dapat dipastikan. Selain itu dimungkinkan juga terjadinya transisi spontan atau transisi –ε.

Mesin NFA

A Non deterministic finite automaton (DFA) M = (Q, Σ, δ, S,Q0, F), dimana :

Q : himpunan state/kedudukan

Σ  : himpunan simbol input

Q0 € Q : initial state

∂  : fungsi transisi, dimana ∂ = Q x (Σ u Ɛ) -> P (Q)

S  : State awal (initial state)

F : himpunan state akhir (Final State)

 Contoh Soal 

Telusurilah, apakah kalimat-kalimat berikut diterima NFA di atas :
ab, abc, aabc, aabb
Jawab :

1. δ(q,ab) =>δ(q,b) => δ(q ,b) => {q, q} => {q} = {q, q, q}

        Himpunan state TIDAK mengandung state AKHIR. kalimat ab tidak diterima

2. δ(q,abc) => δ(q,bc) => δ(q ,bc) => { δ(q,c) => δ(q,c)} => δ(q, c)

         {{ q, q}=>{ q}}=>{ q} = {q, q, q,q}

        Himpunan state TIDAK mengandung state AKHIR .kalimat abc tidak diterima