Simulic
Bahasa Indonesia

Mesin keadaan hingga – lampu lalu lintas, DFA, NFA, dan bahasa reguler

InformatikaAlgoritma dan pemecahan masalahUsia 15–16

Memuat…

Gunakan di kelas saya ✨ Sesuaikan dengan AI Laporkan masalah

Jalankan langkah demi langkah contoh mesin keadaan (lampu lalu lintas, mesin penjual otomatis, pintu putar) dengan serangkaian peristiwa dan amati keadaan saat ini, keluaran, serta tabel jejak; tambahkan, seret, dan hubungkan keadaan untuk menggambar mesin Anda sendiri. Mode Akseptor menguji kata mana yang diterima oleh DFA atau NFA (bilangan biner yang habis dibagi 3, kata yang berakhiran ab), lengkap dengan tabel transisi keadaan, ekspresi reguler dan tata bahasa reguler yang ekuivalen, serta konversi NFA ke DFA. Sebuah catatan membandingkan setiap model dengan sistem nyata untuk membahas abstraksi.

Pelajaran: Mesin keadaan hingga: keadaan, transisi, dan keluaran; automata hingga deterministik dan nondeterministik; ekspresi reguler dan tata bahasa reguler

Yang ditunjukkan

Mesin keadaan hingga memiliki himpunan keadaan yang berhingga, sebuah keadaan awal, alfabet masukan, dan transisi berbentuk keadaan + simbol → keadaan berikutnya. Mesin ini tidak mengingat apa pun selain keadaannya saat ini. Mesin Mealy menghasilkan keluaran pada transisinya, mesin Moore melekatkan keluaran pada keadaannya, dan akseptor menjawab ya atau tidak: apakah sebuah kata termasuk dalam suatu bahasa? Bahasa yang diterima automata hingga tepat sama dengan bahasa reguler, yang juga dapat dideskripsikan oleh ekspresi reguler dan tata bahasa reguler. Setiap NFA (automata hingga nondeterministik) dapat diubah menjadi DFA yang ekuivalen dengan konstruksi subset.

Cara menggunakan

Dalam mode Mesin dengan keluaran, pilih Contoh mesin lalu klik Langkah atau Jalankan untuk memasukkan simbol pada pita satu per satu; tombol simbol mengirim peristiwa tambahan. Dalam mode Akseptor, pilih Contoh automata, ketik Kata yang dibaca dan telusuri langkah demi langkah, lalu gunakan Uji atau Daftar kata diterima. Buka Edit mesin untuk menambah, menyeret, dan menghubungkan keadaan, atau klik Ubah NFA ke DFA.

Parameter yang dapat diubah

  • Mode Mesin dengan keluaran, Akseptor
  • Contoh mesin (mode Mesin dengan keluaran) Lampu lalu lintas, Mesin penjual otomatis, Pintu putar
  • Contoh automata (mode Akseptor) DFA: bilangan biner habis dibagi 3, NFA: kata berakhiran ab, DFA: kata berakhiran ab, DFA: banyak angka 1 genap (bit paritas)
  • Kata yang dibaca (kosong = kata contoh)
  • Kecepatan jalan 0,5–4 simbol/s
  • Buka panel Edit mesin

Pertanyaan untuk dijelajahi

  1. Detail apa saja dari lampu lalu lintas nyata yang dihilangkan dari model, dan mengapa hal itu dapat diterima?
  2. Jika ditelusuri keadaan demi keadaan, apakah kata 110 diterima oleh automata habis dibagi 3?
  3. Mengapa NFA untuk kata berakhiran ab memerlukan lebih sedikit transisi daripada DFA yang ekuivalen?

Simulasi terkait