Finite Automata

Finite Automata adalah mesin automata dari suatu Bahasa regular. Finite Automata memiliki jumlah state yang banyaknya berhingga dan dapat berpindah-pindah dari suate state ke state yang lainnya. 

Finite  State  Automata/otomata  berhingga  state,  selanjutnya  disebut  sebagai  FSA  yaitu suatu model matematika dari suatu sistem yang menerima inputdan outputdiskrit. FSA merupakan mesin otomata dari bahas regular. Suatu FSA memiliki state yang banyaknya   berhingga   dan   dapat   berpindah-pindah   dari   suatu   state   ke   state   lain.   Perubahan   state   ini   dinyatakan   oleh   fungsi   transisi.   FSA   tidak   memiliki   tempat   penyimpanan,  sehingga  kemampuan  ‘mengingatnya’  terbatas,  hanya  bisa  mengingat  state yang terkini. Contoh FSA antara lain elevator, text editor, analisa leksikal, protokol komunikasi  jaringan  dan  pencek  parity.  FSA  berdasar  pada  pendefinisian  kemampuan  berubah  state-statenya  bisa  dibagi  menjadi  Deterministic  Finite  Automata  (DFA)  dan  Non-deterministic Finite Automata(NFA). 

Secara formal FSA dinyatakan oleh 5 tupel atau M = (Q, ∑, δ, S, F) dimana:

Q = himpunan state/kedudukan 

∑ = himpunan simbol input/masukan/abjad 

δ  = fungsi transisi

S  = state awal/kedudukan awal (initial state), S є Q

F  =  himpunan  state  akhir,  F  ∩  Q  (jumlah  state  akhir  pada  suatu  FSA  bisa  lebih  dari  satu)

1. Deterministic Finite Automata (DFA) 

Deterministic   Finite   Automata/otomata   berhingga   deterministik,   selanjutnya   disebut  sebagai  DFA.  Pada  DFA,  dari  suatu  state  ada  tepat  satu  state  berikutnya  untuk  setiap  simbol  masukan  yang  diterima.  Suatu  string  x  dinyatakan  diterima  bila  δ(S,  x)  berada pada state akhir/final state.

Berikut contoh dari Deterministic Finite Automata :

2. Non Deterministic Finite Automata (NFA).

Non-deterministic Finite Automata, selanjutnya disebut sebagai NFA. Pada NFA, dari  suatu  state  bisa  terdapat  0  atau  1  atau  lebih  busur  keluar  (transisi)  berlabel  simbol  input  yang  sama.  Suatu  string  diterima  oleh  NFA  bila  terdapat  suatu  urutan  transisi  sehubungan dengan input string tersebut dari state awal menuju state akhir. Untuk NFA, maka   harus   mencoba   semua   kemungkinan   yang   ada   sampai   terdapat   satu   yang   mencapai state akhir.

Berikut contoh dari Non Deterministic Finite Automata (NFA) : 

Berdasarkan contoh Deterministic Finite Automata (DFA) dan Non Deterministic Finite Automata (NFA) yang ada di atas, terlihat perbedaan antara DFA dan NFA yaitu :

•  Pada Deterministic Finite Automata, jika suatu state diberi inputan maka state tersebut akan selalu tepat menuju satu state
• Pada Non Deterministic Finite Automata, jika suatu state diberi inputan maka mungkin saja bisa menuju ke beberapa state berikutnya. Dapat dilihat di S0, jika diberi inputan b bisa menuju ke S1 dan S2.

Sumber : 

https://socs.binus.ac.id/2019/12/21/teknik-kompilasi-perbedaan-dfa-dan-nfa/

https://media.neliti.com/media/publications/226255-telaah-teoritis-finite-state-automata-de-8b056b07.pdf