Finite Automata

 

Finite Automata

Finite automata adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata di mana sistem dapat berada di salah satu dari sejumlah berhingga konfigurasi internal disebut state. Beberapa contoh sistem dengan state berhingga antara lain pada mesin minuman otomatis atau vending machine, pengatur lampu lalu lintas dan lexical analyser. 

Suatu finite automata terdiri dari beberapa bagian. Finite automata mempunyai sekumpulan state dan aturan-aturan untuk berpindah dari state yang satu ke state yang lain, tergantung dari simbol nya. Finite automata mempunyai state awal, sekumpulan state dan state akhir. Finite automata merupakan kumpulan dari lima elemen atau dalam bahasa matematis dapat disebut sebagai 5-tuple. 

DEFINISI

Otomata Hingga (AH)/Automata Hingga (AH)/Finite Automata (FA) didefinisikan sebagai pasangan 5 tupel: (K, VT , M, S, Z).
𝐾 : himpunan hingga stata,
𝑉𝑇 : himpunan hingga simbol input (alfabet)
𝑀 : fungsi transisi, menggambarkan transisi stata AH akibat pembacaan simbol input. Fungsi transisi ini biasanya diberikan dalam bentuk tabel.
𝑆 ∈ 𝐾 : stata awal
𝑍 ⊂ 𝐾 : himpunan stata penerima

Terdiri dari 2 jenis:
1. Deterministic FA (DFA), dimana transisi stata FS merupakan akibat dari pembacaan sebuah simbol bersifat tertentu; dan
2. Non-Deterministic FA (NFA), dimana transisi stata FS merupakan akibat dari pembacaan sebuah simbol bersifat tak tentu.

DETERMINISTIC FINITE AUTOMATA (DFA).

Contoh Kasus: Diketahui sebuah DFA sebagai berikut F(K,Vt,M,S,Z) dimana:

K    = {q0,q1,q2}
Vt   = {a,b}
S     = {q0}                                      M diberikan dalam tabel berikut:
Z     = {q0,q1}

Ilustrasi graph untuk DFA F adalah sebagai berikut:

Problem: telusurilah, apakah string abababaa diterima DFA F?
Jawab: M(q0, abababaa) ⇒ M(q0, bababaa) ⇒ M(q1,ababaa) ⇒M(q0, babaa) ⇒ M(q1, abaa) ⇒ M(q0, baa) ⇒ M(q1, aa) ⇒ M(q0, a) ⇒ M(q0) atau q0.

Non-Deterministic Finite Automata (NFA).

Contoh kasus: Diketahui sebuah NFA sebagai berikut F(K,Vt,M,S,Z) dimana:

𝐾 = {q0, q1, q2, q3, q4}                    
𝑉t = {a, b, c}
𝑆 = {q0}                                         M Diberikan dalam tabel berikut:
𝑍 = {q4}                               

Perbedaan antara NFA dan DFA :

1. Pada NFA memungkinkan satu simbol menimbulkan transisi ke lebih dari satu state, dapat dikatakan juga bahwa pada DFA untuk setiap state s dan simbol a hanya ada paling banyak satu buah label a yang meninggalkan state s.

2. Pada NFA memungkinkan transisi spontan atau transisi-ǫ yang selanjutnya akan diistilahkan dengan ǫ-NFA. 

NFA sebagai pengenal bahasa reguler 

Suatu NFA dikatakan menerima string x jika dan hanya jika terdapat beberapa jalur dalam diagram transisi dari state awal ke salah satu state akhir, sedemikian hingga semua simbol di dalam x akan terurai (Mogensen, 2010). Jika x adalah string alfabet Σ pada NFA (contohnya x dalam Σ * ) diterima oleh NFA jika minimal terdapat satu jalur yang eksis yang berkorespondensi pada x dalam NFA, yang dimulai dari start state dan berakhir pada final state. Sedangkan dalam DFA, karena hanya terdapat satu buah jalur yang berkorespondensi pada x dalam Σ * hal ini cukup untuk melakukan pengecekan apakah sebuah jalur yang dimulai dari initial state berakhir pada salah satu final state atau tidak untuk mengetahui apakah x diterima oleh suatu DFA atau tidak. 

Oleh karena itu, jika x adalah suatu string dibuat dari simbol dalam Σ dalam NFA, contohnya x ada dalam Σ * kemudian x diterima oleh NFA jika terdapat paling sedikit satu buah jalur yang terbentuk dan berkorespondensi dengan x dalam NFA, yang berawal dari initial state dan berakhir pada salah satu anggota himpunan final state dalam NFA. Karena x merupakan anggota Σ * dan terdapat kemungkinan nol, satu atau lebih transisi dari sebuah state pada sebuah simbol masukan dapat 19 didefinisikan fungsi transisi baru(δ1) di mana fungsi transisi tersebut memetakan 2Q × Σ * hingga 2Q dan jika δ1({q0, x}) = P di mana P adalah suatu himpunan yang terdiri dari minimal satu anggota himpunan dari F, sehingga x diterima oleh NFA. Jika x dituliskan dengan wa di mana a adalah simbol terakhir dalam x dan w adalah string yang terbuat dari simbol yang tersisa dalam x maka 

    δ1({q0} , x) = δ1(δ1({q0} , w)). Sejak δ1 didefinisikan dengan pemetaan dari 2Q × Σ * hingga 2Q maka δ1(p, a) = ∪ ForEach q in Pδ(q, a).

source : 
http://library.binus.ac.id/eColls/eThesisdoc/Bab2/2011-2-00004-MTIF%20Bab2001.pdf
https://ocw.upj.ac.id/files/Handout-INF305-TM5-Finite-Automata.pdf