Pengenalan Finite State Automata (FSA)

Pembukaan

• Salam pembuka: Assalamualaikum warahmatullahi wabarakatuh
• Penyampaian materi tentang FSA atau Finite State Automata.

Apa itu FSA?

• FSA adalah mesin abstrak dalam bentuk sistem model matematika.
• Memproses masukan dan keluaran diskret.
• Dapat mengenali bahasa paling sederhana.
• Digunakan untuk menentukan apakah suatu bahasa dapat diterima atau tidak.
• Juga dapat digunakan untuk memproduksi bahasa sesuai modelnya.

Mekanisme Kerja FSA

• Diterapkan dalam:
  • Analisis leksikal
  • Text editor
  • Protokol komunikasi jaringan
• Analisis leksikal adalah proses penerjemahan kode dari bahasa tingkat tinggi ke bahasa mesin.
  • Menentukan variabel, keyword, nilai, dan operator dalam kode.

Contoh Mesin Automata

• Mesin pengecek parity ganjil:
  • Mengidentifikasi apakah jumlah angka 1 dalam input ganjil atau genap.
  • Contoh input: 0, 0, 1 menghasilkan output diterima (ganjil).

Simbol dan Gambar Mesin

• Initial State: Ditandai dengan busur tanpa asal state.
• State: Ditunjukkan dengan lingkaran.
• Label pada Lingkaran: Nama state (contoh: event, odd).
• Busur: Menyatakan transisi antar state.
• Lingkaran Ganda: Menyatakan final state.

Pernyataan Formal FSA

• FSA dinyatakan dalam 5 tuple: M = (K, Σ, δ, K₀, F)
  • K: Himpunan state
  • Σ: Himpunan simbol input
  • δ: Fungsi transisi
  • K₀: Initial state
  • F: Himpunan final state (bisa lebih dari 1)

Contoh Derivasi Input

• Contoh diterima: Input 1101 - berakhir di final state (ganjil).
• Contoh ditolak: Input 101 - berakhir di state event (bukan final state).

Klasifikasi FSA

• FSA dikelompokkan menjadi dua jenis:
  • Deterministic Finite State Automata (DFSA)
  • Non-Deterministic Finite State Automata (NFSA)

Penutup

• Terima kasih telah menyimak.
• Ajak untuk like, subscribe, dan share.
• Salam penutup: Assalamualaikum warahmatullahi wabarakatuh.