2

بِسْمِ اللّهِ الرَّحْمَنِ الرَّحِيْم

Assalamu’alaikum Wr. Wb

 

 

1. Penegertian Finite Automata

Finite Automata merupakan suatu model komputer dengan jumlah memory yang sangat terbatas (model komputasional yang paling sederhana)

Finite Automata :

  • Mesin yang terdiri dari finite number of State.
  • Salah satu sebagai intitial state
  • Dan minimal satu accepted state.
  • Mesin akan menerima input stream berupa symbol / alphabet yang datang secara sequential.
  • Mesin akan berubah dari state satu ke state lain berdasar simbol input dan current state.
  • Deterministic à tidak diperkenankan ambigu.
  • Finite refers to fakta bahwa mesin terdiri dari state yang finite.
  • Esensi DFA adalah recognizer string (menerima atau menolak)
  • Mungkin saja di DFA menerima string kosong. Jika hal ini terjadi, maka initial state adalah accepted state.

 

Definisi Formal dari Deterministik Finite Automata

Sebuah finite automata didefinisikan dalam 5-tuple (Q,Σ, δ,q0,F) dimana

  1. Q adalah himpunan terbatas dari states,
  2. Σhimpunan terbatas alphabet,
  3. δ: Q ×Σ à Q fungsi transisi, dinotasikan ke δ(q,a) à p
  4. q0 ∈ Q adalah start state, dan
  5. F⊆Q adalah himpunan accepted states (atau final states).

 

BeST

 

 

2. Jenis Finite Automata

a. Deterministik Finite Automata

“Deterministik” à setiap input alphabet/simbol dari suatu state hanya akan bertransisi ke satu state lain. Atau dengan kata lain deterministik tidak ambigu dalam menentukan next state.

Contoh Deterministik

  • Mesin Ganjil.
  • Dari q0, tidak ada kerancuan jika menerima input 1 (akan ke q1), dan sebagainya.

Contoh Deterministik

 

b.  Non-Deterministik Finite Automata

“Non-Deterministrik” à setiap input alphabet/simbol dari suatu state mungkin akan bertransisi ke lebih dari satu state lain.

Contoh Non-Deterministik

  • Lihat bahwa dari q0, akan muncul kerancuan jika menerima input 0 (akan ke q0 atau q1).

Contoh Non-Deterministik

Post a Comment Blogger

  1. Salam Perdana dari Auek Sigli...Lanjutkan terus rakan

    ReplyDelete
    Replies
    1. Salam juga... Salam persahabatan dr Blog Si Taufik :)

      Delete

 
Top