FINITE STATE AUTOMATA

Finite State Automata atau Otomata Hingga dikemukakan McCulloch dan Pitts (1940) untuk memodelkan neuron nets, dan juga digunakan untuk merancang switcing circuit.

Otomata Hingga dapat dinyatakan sebagai pengenal bahasa, bahasa yang dikenali adalah bahasa sederhana namun mempunyai aspek penerapan sangat penting di ilmu informatika / komputer, yaitu bahasa Regular, yang didefinisikan sebagai pasangan 5 tupel, yaitu :
K = Himpunan Stata, digambarkan dengan lambang lingkaran
V = Himpunan Input, label yang terdapat pada panah transisi
S = Stata awal, yang ditandai dengan gambar panah di depan stata
M = Fungsi Transisi, memetakan Stata dengan inputnya menuju ke stata tujuan.
Fungsi Transisi dapat disajikan dalam bentuk tabel transisi atau diilustrasikan
dalam bentuk graf
Z = Himpunan Stata Penerima, yang ditandai lingkaran ganda, apabila tracing input berhenti di salah satu stata penerima maka kalimat tersebut dikenali oleh mesin tersebut

Otomata Hingga dibagi menjadi 2 jenis, yaitu :
- Otomata Hingga Deterministik (Deterministic Finite Automata)
- Otomata Hingga Nondeterministik (Nondeterministic Finite Automata)

Otomata Hingga yang biasa digunakan dalam hal ini merupakan Otomata Hingga Deterministik, untuk yang lainnya akan disebutkan secara lengkap namanya.

Jika ada dua buah mesin OTOMATA hingga yang mana keduanya sama-sama dapat menerima atau mengenali bahasa yang sama, maka keduanya dapat dikatakan equivalen. Namun untuk lebih jelasnya ada algoritma yang mengaturnya, yaitu :
1. Pastikan nama stata pada kedua otomata hingga tersebut berbeda (tidak sama).
2. Buat tabel antara pasangan stata (stata AHD1, stata AHD2) dengan input-inputnya
3. Pasangan stata pertama diisi dengan stata awal masing-masing AHD
4. Perhatikan nilai-nilai pasangan stata pada baris pertama, apakah ada pasangan stata baru
yang belum terdaftar di kolom stata? jika ada, tempatkan pasangan stata tersebut sebagai
pasangan stata baru, kemudian lakukan sesuai aturan fungsi transisinya.
5. Lakukan langkah ke-4 sampai tidak ditemukannya pasangan stata baru. Dan kedua AHD
tersebut dinyatakan equivalen atau sama-sama dapat menerima bahasa yang sama.

Contoh :
1. Jika diketahui :
K = {A, B}, V = { a }, S = A, Z = { B }
M(A, a) = B
M(B, a) = A
- Gambarkan grafnya
- Tentukan bahasa yang dihasilkan, L(G)?

2. Jika diketahui :
K = {A, B}, V = { a }, S = A, Z = { B }
M(A, a) = B
M(B, a) = B
- Gambarkan grafnya & Tentukan L(G) nya

3. Apakah kedua otomata hinggga diatas equivalen? Buktikan!