Finite Automata

 Finite State Automata (FSA) adalah contoh mesin otomata bahasa regular yang dinyatakan dalam 5 tupel, yaitu:

• Q = Himpunan state
• ∑ = Himpunan simbol input
• ծ = Fungsi transisi
• S = State awal (Initial State)
• F = Himpunan Finish state

Non-Deterministic Finite Automata (NFA) juga memiliki 5 tupel seperti FSA. Bedanya dengan FSA yang hanya memiliki satu simbol input di setiap state-nya, Non-Deterministic Finite Automata bisa memiliki lebih dari satu simbol input di setiap state-nya. Reduksi Jumlah State Finite State Automata berfungsi untuk memilih state otomata praktis yang ditandai dengan jumlah state yang paling sedikit.

Reduksi artinya mengurangi jumlah state pada FSA tanpa mengurangi kemampuan dari suatu mesin otomata dengan cara menentukan distinguishable (Bisa dibedakan) dan indistinguishable (tidak bisa dibedakan).

Ekuivalensi Non-Deterministic Finite Automata(NFA) ke Deterministic Finite Automata (DFA)

Ekuivalensi atau bersesuaian pada mesin automata artinya mesin tersebut dapat menerima bahasa yang sama.

Dari suatu mesin Non Deterministic Finite Automata (NFA) dapat dikonversi atau dibuat menjadi suatu mesin Deterministic Finite Automata (DFA) yang memiliki kemampuan menerima Bahasa yang sama (ekuivalen).

Berikut contoh konversi dari Non Deterministic Finite Automata menjadi Deterministic Finite Automata: 

• Berikut table transisi dan diagram transisi untuk NFA :
• 
  
  

  Dapat dilihat dari gambar di atas ada suatu state yang diberi inputan menuju ke beberapa state, yaitu S0 yang diberi inputan b bisa menuju ke S0 dan S1

• Lalu dikonversi menjadi DFA, dengan cara membuat state baru berupa gabungan dari S0 dan S1.
• Lalu untuk state {S0,S1} jika diberi inputan a maka hasilnya adalah gabungan dari hasil S0 dan S1 yang diberi inputan a yaitu {S0,S1}.
• Lalu untuk state {S0,S1} jika diberi inputan b maka hasilnya adalah gabungan dari hasil S0 dan S1 yang diberi inputan b yaitu {S0,S1}.
• Berikuta table transisi dan diagram transisi untuk DFA nya :
• 
  
  
  
• 
  
  
•