Teori Bahasa dan Automata : Finite State Automata

  1. Setiap Finite Automata memiliki keadaan dan transisi yang terbatas.
  2. Transisi dari satu keadaan ke keadaan lainnya dapat bersifat deterministik atau non-deterministik.
  3. Setiap Finite Automata selalu memiliki keadaan awal.
  4. Finite Automata dapat memiliki lebih dari satu keadaan akhir. jika setelah pemrosesan seluruh string, keadaan akhir dicapai, artinya otomata menerima string tersebut.
  1. Himpunan berhingga (finite) status (state) Satu buah status sebagai status awal (initial state), biasa dinyatakan q0. Beberapa buah status sebagai status akhir (final state).
  2. Himpunan berhingga simbol masukan
  3. Fungsi transisi Menentukan status berikutnya dari setiap pasang status dan sebuah simbol masukan.
  • State (himpunan status berhingga)
  • Fungsi transisi
  • Diagram transisi

Ekuivalensi Antar Deterministic Finite Automata (DFA)

Reduksi Jumlah State Pada FSA

  • D adalah himpunan state-state distinguishable, dimana D Ì Q
  • N adalah himpunan state-state indistinguishable, dimana N Ì Q
  • maka x Î N jika x Î Q dan x ∉ D

--

--

Interested and learn about programming, web development, and machine learning

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Agung Prabowo

Agung Prabowo

Interested and learn about programming, web development, and machine learning