FSA (Finite State Automata) & DFA (Deterministic Finite Automata)

-

 FSA (Finite State Automata) & 

DFA (Deterministic Finite Automata)


Definisi Formal FSA 


M = (Q, Σ, 8, S, F) 

dimana : 
Q = himpunan state
Σ = abjad, himpunan simbol input/masukan
8 = fungsi transisi, 8 = Q * Σ -> Q
S = state awal / initial state
F = himpunan state akhir / final state

Jenis DFA

  • Deterministik (DFSA/DFA)
Pada setiap input, hanya ada satu keadaan (state) tujuan dari keadaan saat ini.
  • Non - Deterministik (NFSA/NFA)
Pada setiap input terdapat lebih dari satu keadaan tujuan dari keadaan saat ini.

Contoh DFA 

  • Contoh DFA yang dapat menerima string berakhiran 01 


  • A = ({q0, q1, q2}, {0, 1}, 8, q0, {q2}) dengan fungsi transisi 8 diberikan dalam bentuk table :


Contoh Lainnya :









Komentar

Posting Komentar

Postingan populer dari blog ini

NFA (Nondeterministic Finite Automata) Dengan E-Move

-
Gambar
 NFA (Nondeterministic Finite Automata) Dengan E-Move Proses Perpindahan State Tanpa Membawa Nilai Input Apapun (empty). NFA Dengan E-Move              NFA dengan E-Move (transisi E-Move), diperbolehkan merubah state tanpa membaca input. Disebut dengan E-Move karena tidak bergantung pada 1 input saat melakukan transisi (perpindahan). E-Move Berada Pada Transisi State         Sebuah transisi mempunyai nilai/output/E-Move. Suatu E-Move untuk state q1 ke q2 yang terhubung dapat berpindah tanpa menghasilkan inputan apapun pada transisinya. Contoh : Tanpa membaca inputan : q0 dapat berpindah ke q1 q1 dapat berpindah ke q2 q4 dapat berpindah ke q1 E-Clouser  E-Closure adalah himpunan state yang dapat di capai dari suatu state tanpa membaca input. E-Closure (q0) = himpunan state yang dapat dicapai dari state q0 tanpa membaca input. Pada suatu state yang tidakk memiliki E-Move maka E-Closure nya adalah state itu sendiri....
Baca selengkapnya

Ekuivalensi NFA (Nondeterministic Finite Automata) Ke DFA (Deterministic Finite Automata)

-
Gambar
Ekuivalensi NFA (Non-deterministic Finite Automata) ke DFA (Deterministic Finite Automata)          Dari sebuah mesin Non-deterministic Finite Automata dapat dibuat mesin DFA yang ekivalen. Ekivalen artinya mampu menerima bahasa yang sama. Simulasi NFA ke DFA Cara simulasi NFA ke DFA adalah dengan menbuat state DFA berkorespondensi dengan set state di NFA. DFA yang dibentuk mencatat semua state yang mungkin pada NFA setelah membaca input tertentu. FSA (Finite State Automata)  FSA terdiri dari : 1. DFA (Deterministic Finite Automata) 2. NFA (Non-deterministic Finite Automata) Ciri DFA dan NFA 1. Ciri DFA (Deterministic Finite Automata) 2. Ciri NFA (Non-deterministic Finite Automata) Proses Ekuivalensi NFA Ke DFA Buat tabel transisi diagram tersebut Buat diagram transisi untuk FSA diatas Setiap State dituliskan sebagai humpunan state {} Buat tabel transisi baru Buat diagram transisi ekuivalensi NFA ke DFA Contoh Lainnya :
Baca selengkapnya