Deterministik Finite Automata

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

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).

 

 

 

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.

 

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).