Aplikasi Automata JFLAP

 Definisi JFLAP

JFLAP mendefinisikan otomaton terbatas (FA) M Quadraple M = (Q, Σ, Δ, q_s, F) mana
Q adalah seperangkat terbatas Serikat {q_saya | saya adalah bulat nonnegative}
Σ adalah alfabet input terbatas
Δ adalah fungsi transisi, δ: D → 2^Q dimana D adalah subset terbatas dari Q × Σ *
q_s (adalah anggota Q) adalah keadaan awal
F (adalah subset dari Q) adalah serangkaian Serikat akhir

Catatan bahwa definisi ini termasuk automata terbatas deterministik (DFAs), yang kita akan membahas segera, dan automata terbatas nondeterministic (NFAs), yang kami akan menyentuh pada kemudian.

Membangun berbagai jenis automata di JFLAP cukup mirip, jadi mari kita mulai dengan membangun DFA untuk bahasa L = {b^mn : m ≥ 0, n > 0, n aneh}. Itu adalah, kita akan membangun DFA yang mengakui bahwa bahasa sejumlah yang diikuti oleh sejumlah aneh b' s. (contoh-contoh yang diambil dari JFLAP: bahasa Formal yang interaktif dan Automata paket oleh Susan Rodger dan Thomas Finley.)

Jendela Editor fileex

Untuk memulai FA baru, mulai JFLAP dan klik Robot terbatas pilihan dari menu.

Mulai FA baru

Ini seharusnya memunculkan jendela baru yang memungkinkan Anda untuk membuat dan mengedit FA. Editor terbagi menjadi dua daerah dasar: kanvas, yang Anda dapat membangun robot Anda pada, dan toolbar, yang memegang alat yang Anda butuhkan untuk membangun robot Anda.

Jendela editor

Mari kita lihat lebih dekat di toolbar.

FA toolbar

Seperti yang Anda lihat, toolbar memegang empat alat:

• Editor atribut alat : set awal dan akhir
• Negara alat pencipta : menciptakan Serikat
• Alat pencipta transisi : menciptakan transisi
• Alat deletor : menghapus Serikat dan transisi

Untuk memilih alat, klik pada ikon yang sesuai dengan mouse Anda. Ketika alat yang dipilih, itu teduh, sebagai alat Editor atribut di atas. Memilih alat menempatkan Anda dalam modus yang sesuai. Misalnya, dengan toolbar di atas, kita sekarang berada pada mode Editor atribut.
Mode yang berbeda menentukan cara klik mouse mempengaruhi mesin. Sebagai contoh, jika kita berada dalam modus negara pencipta, mengklik pada kanvas akan membuat negara baru. Mode ini akan dijelaskan lebih detail segera.

Sekarang mari kita mulai menciptakan FA kami.

Membuat Serikat

Pertama, mari kita membuat beberapa negara. Untuk itu kita perlu mengaktifkan bahwa alat pencipta negara dengan mengklik tombol pada toolbar. Selanjutnya, klik pada kanvas di lokasi yang berbeda untuk membuat Serikat. Kami tidak sangat yakin berapa banyak negara kita akan membutuhkan, jadi kami menciptakan empat negara. Jendela editor Anda akan terlihat seperti ini:

Negara-negara yang dibuat

Sekarang bahwa kita telah menciptakan keadaan kita, mari kita menentukan keadaan awal dan akhir.

Menentukan awal dan akhir Serikat

Sewenang-wenang, kami memutuskan bahwa q₀ akan keadaan awal kami. Untuk menentukan untuk menjadi keadaan awal kami, pertama Pilih alat Editor atribut di toolbar. Sekarang bahwa kita berada dalam mode Editor atribut, klik kanan pada q₀. Ini harus memberi kita menu pop-up yang terlihat seperti ini:

Menu negara

Dari pop-up menu, pilih kotak centang yang awal. Arrowhead putih appreas di sebelah kiri q₀ untuk menunjukkan bahwa itu adalah keadaan awal.

q₀ didefinisikan sebagai keadaan awal

Selanjutnya, mari kita membuat keadaan akhir. Sewenang-wenang, kami memilih q₁ sebagai keadaan akhir kami. Untuk menetapkan sebagai keadaan akhir, klik kanan pada keadaan dan klik kotak centang yang Final. Itu akan memiliki garis ganda, menunjukkan bahwa itu adalah keadaan akhir.

q₁ didefinisikan sebagai keadaan akhir

Sekarang bahwa kita telah didefinisikan Serikat awal dan akhir, mari kita beralih ke menciptakan transtitions.

Menciptakan transisi (fileex.blogspot.com)

Kita tahu string dalam bahasa kita dapat memulai dengan 's, jadi, keadaan awal harus transisi keluar pada . Kita juga tahu bahwa itu dapat memulai dengan sejumlah 's, yang berarti bahwa FA harus dalam keadaan yang sama setelah pengolahan masukan dari sejumlah ' s. Dengan demikian, transisi keluar pada dari q₀ loop kembali kepada dirinya sendiri.
Untuk membuat sebuah transisi, pertama Pilih alat pencipta transisi dari toolbar. Selanjutnya, klik pada q₀ di kanvas. Kotak teks akan muncul di negara:

Menciptakan transisi

Perhatikan bahwa λ, reprsenting string kosong, awalnya diisi untuk Anda. Jika Anda lebih suka ε mewakili string kosong, pilih preferensi: preferensi dalam menu utama untuk mengubah simbol yang mewakili string kosong.
Jenis "a" dalam teks kotak dan tekan Enter. Jika kotak teks tidak dipilih, tekan Tab untuk memilihnya, lalu masukkan "". Ketika Anda selesai, itu akan terlihat seperti ini:

Transisi yang dibuat

Selanjutnya, kita tahu bahwa string dalam bahasa kita harus diakhiri dengan sejumlah aneh b' s. Dengan demikian, kita tahu bahwa transtion keluar pada b dari q₀ harus ke keadaan akhir, sebagai sebuah string yang berakhir dengan satu b harus diterima. Untuk membuat transisi dari keadaan awal kami q₀ untuk kami keadaan akhir q₁, pertama memastikan bahwa alat pencipta transisi dipilih di toolbar. Selanjutnya, klik dan tahan pada q₀, dan tarik mouse untuk q₁ dan lepaskan tombol mouse. Masukkan "b" dalam textbox dengan cara yang sama Anda memasukkan "" untuk transisi sebelumnya. Transisi antara kedua negara akan terlihat seperti ini:

Kedua transisi yang dibuat

Terakhir, kita tahu bahwa hanya string yang berakhir dengan angka ganjil bharus diterima. Dengan demikian, kita tahu bahwa q₁ memiliki transisi keluar pada b, yang tidak bisa loop kembali ke q₁. Ada dua pilihan untuk transtion: itu dapat pergi ke keadaan awal q₀, atau ke negara baru, misalnya, q₂.
Jika transisi pada b ke keadaan awal q₀, string tidak akan menjadi bentuk b^mn; string seperti ababab juga akan diterima. Justru, transisi tidak bisa untuk q₀dan itu harus untuk q₂.
Membuat transisi b dari q₁ q₂. FA harus menerima string yang berakhir dengan angka ganjil b, membuat transisi lain pada b dari q₂ q₁. FA Anda adalah sekarang penuh bekerja FA! Seharusnya terlihat seperti ini:

Kerja FA

Anda mungkin melihat bahwa q₃ tidak digunakan dan dapat dihapus. Selanjutnya, kami akan menjelaskan bagaimana menghapus Serikat dan transisi.

Menghapus Serikat dan transisi

Untuk menghapus q₃, pertama Pilih alat Deletor di toolbar. Selanjutnya, klik pada negara q₃. Jendela editor Anda sekarang harus terlihat seperti ini:

q₃ dihapus

Demikian pula, untuk menghapus transisi, cukup klik pada simbol masukan transisi ketika dalam Deletor mode.

Anda FA, faex.jff, kini lengkap.

Menjalankan FA beberapa string

Sekarang bahwa Anda telah menyelesaikan FA Anda, Anda mungkin ingin menguji untuk melihat jika itu benar-benar menerima string dari bahasa. Untuk melakukannya, pilih masukan: menjalankan beberapa dari menu bar.

Mulai menjalankan beberapa tab

Tab baru akan muncul menampilkan otomaton pada panel kiri, dan input tabel di sebelah kanan:

Beberapa baru menjalankan tab

Untuk memasukkan string input, klik pada baris pertama di kolom Input dan ketik string. Tekan Enter untuk melanjutkan ke berikutnya input string. Ketika Anda selesai, klik Menjalankan input untuk menguji Anda FA pada semua senar masukan. Hasilnya, menerima atau menolak ditampilkan di kolom hasil . Anda juga dapat memuat input dari file yang dibatasi oleh ruang putih. Klik beban input dan memuat file untuk menambahkan tambahan masukan string ke panel multi-run.

Menjalankan beberapa masukan

Mengklik Clear menghapus semua senar input, sementara Memasukkan Lambda memasuki string kosong di kursor. Lihat jejak memunculkan jendela terpisah yang menunjukkan jejak slected masukan. Untuk kembali ke jendela Editor, pilih File: mengabaikan Tab dari menu bar.

Membangun robot terbatas Nondeterministic

Membangun robot terbatas nondeterministic (NFA) sangat banyak seperti membangun DFA. Namun, NFA berbeda dari DFA yang memenuhi salah satu dari dua kondisi. Pertama, jika FA memiliki dua transisi dari negara bagian yang sama yang membaca lambang, FA dianggap NFA. Kedua, jika FA memiliki transisi yang membaca string kosong untuk input, hal ini juga dianggap NFA.  Mari kita lihat pada NFA ini, yang dapat diakses melalui ex1.3a.jff: (Catatan: contoh ini diambil dari JFLAP: bahasa Formal yang interaktif dan Automata paket oleh Susan Rodger dan Thomas Finley.)

NFA

Kita dapat langsung mengetahui bahwa ini adalah NFA karena λ empat-transisi yang berasal dari q₃ dan q₉, tetapi kita mungkin tidak yakin apakah kita telah melihat semua negara nondeterministic. JFLAP dapat membantu dengan itu.

Menyoroti Nondeterministic Serikat

Untuk melihat semua negara nondeterministic di NFA, pilih Test: Sorot Nondeterminism dari menu bar:

Menyoroti nondeterministic Serikat

Tab baru akan muncul dengan nondeterministic Serikat teduh warna gelap:

Nondeterministic Serikat disorot

Seperti yang kita lihat, q₃ dan q₉ yang memang nondeterministic karena λ mereka keluar-transisi. Catatan bahwa mereka akan keduanya menjadi nondeterministic bahkan jika mereka masing-masing memiliki satu λ-transisi bukan dua: hanya satu λ-transisi diperlukan untuk membuat keadaan nondeterministic. Kita juga melihat bahwa q₁ nondeterministic karena dua transisi yang keluar pada simbol sama, . Selanjutnya, kita akan pergi melalui JFLAP's alat untuk menjalankan masukan pada NFA.

Menjalankan masukan pada NFA

Untuk melangkah melalui masukan pada NFA, pilih masukan: langkah dengan penutupan... dari menu bar. Sebuah kotak dialog yang meminta Anda untuk masukan akan muncul. Biasanya, Anda akan memasukkan masukan Anda ingin langkah di sini. Untuk saat ini, ketik "aaaabb" di kotak dialog dan tekan Enter. Anda juga dapat memuat file input mengetik string.
Catatan: Ketika loading masukan dari file, JFLAP menentukan akhir input string dengan ruang putih. Jadi jika ada string "ab cd" dalam file, hanya "ab" akan dianggap sebagai masukan ("cd" akan diabaikan karena ada spasi sebelum mereka).

Memasuki input

Tab baru akan muncul menampilkan robot di bagian atas jendela, dan konfigurasi di bagian bawah. Keadaan saat ini teduh.

Masukan tab baru

Pertama, mari kita lihat lebih dekat di konfigurasi:

Sebuah ikon konfigurasi

Ikon konfigurasi menunjukkan keadaan saat ini konfigurasi di pojok kiri atas, dan masukan pada pita putih di bawah ini. Input olahan ditampilkan dalam abu-abu, dan input diproses hitam.
Klik langkah ke proses berikutnya simbol masukan. Anda akan melihat q₁ menjadi negara teduh di NFA, dan bahwa ikon konfigurasi perubahan, mencerminkan fakta bahwa pertama telah diproses. Klik langkah lagi untuk proses berikutnya . Anda akan menemukan bahwa empat negara teduh bukan satu, dan ada empat konfigurasi bukan satu.

aa diproses

Hal ini karena mesin ini nondeterministic. Dari q₁, NFA mengambil kedua transisi ke q₂ dan q₉. Sebagai q₉ memiliki dua λ-transisi (yang tidak memerlukan input), NFA lebih lanjut diproduksi dua konfigurasi yang lain dengan mengambil transisi mereka. Dengan demikian, simulator sekarang memiliki empat konfigurasi. Klik langkah lagi untuk proses masukan simbol berikutnya.

aaa diproses

Perhatikan bahwa dua konfigurasi merah disorot, menunjukkan mereka ditolak. Melihat masukan mereka, kita juga tahu bahwa hanya aa diproses. Apa yang terjadi?

Memproduksi jejak

Untuk memilih konfigurasi, klik di atasnya. Ini akan menjadi warna solid ketika dipilih, daripada warna sedikit dinilai. Klik pada ikon untuk konfigurasi ditolak dengan negara q₁₁, lalu klik jejak. Seorang janda yang baru akan muncul menampilkan traceback bahwa konfigurasi:

Traceback konfigurasi

Traceback menunjukkan konfigurasi setelah memproses masing-masing simbol masukan. Dari traceback, kita dapat mengatakan bahwa bahwa konfigurasi dimulai pada q₀ dan membawa transisi ke q₁ setelah pengolahan pertama . Setelah memproses kedua , itu di q₁₁. Meskipun q₁₁ tidak berdekatan q₁, bisa dicapai dengan mengambil λ-transisi dari q₉. Seperti simulator mencoba untuk memproses berikutnya pada konfigurasi ini, menyadari bahwa ada yang tidak keluar transisi dari q₁₁ dan karena itu menolak konfigurasi.

Meskipun ditolak konfigurasi akan menghapus diri pada langkah berikutnya, kita juga dapat menghapus konfigurasi yang tidak telah ditolak.

Menghapus konfigurasi

Melihat tracebacks konfigurasi ditolak, kita bisa mengatakan bahwa konfigurasi apapun yang di q₁₁ atau q₆ dan simbol masukan yang berikutnya adalah akan ditolak.

Sebagai simbol masukan berikutnya , kita dapat mengatakan bahwa konfigurasi yang sedang dalam t₆ dan q₁₁ akan ditolak. Klik sekali pada setiap dari empat konfigurasi untuk memilihnya, lalu klik Hapus. Simulator tidak lagi akan langkah konfigurasi ini. (Meskipun kami hanya menghapus konfigurasi yang akan ditolak, kita dapat menghapus konfigurasi apapun untuk tujuan apapun, dan simulator akan berhenti melangkah melalui masukan pada konfigurasi tersebut.)  Simulator Anda sekarang harus terlihat seperti ini:

Ditolak konfigurasi dihapus

Sekarang ketika kita melangkah simulator, dua konfigurasi akan melangkah melalui.

Melihat dua konfigurasi yang di atas, kita mungkin menyadari bahwa konfigurasi pada q₃ tidak akan mengarah ke konfigurasi menerima. Kita dapat menguji ide kami keluar dengan membekukan konfigurasi lainnya.

Pembekuan dan pencairan konfigurasi

Untuk membekukan konfigurasi pada q₁₀, klik pada q₁₀ sekali, kemudian klik tombol membeku . Ketika konfigurasi beku, itu akan menjadi berwarna gelap warna ungu:

Konfigurasi pada q₁₀ beku

Dengan konfigurasi yang beku, ketika Anda mengklik langkah untuk langkah melalui konfigurasi pada q₃, konfigurasi beku tetap sama. Mengklik langkah dua kali akan mengungkapkan bahwa konfigurasi pada q₃ adalah tidak diterima baik. Simulator Anda sekarang akan terlihat seperti ini:

Konfigurasi lain ditolak

Untuk melanjutkan dengan konfigurasi beku, pilih dan klik mencair. Simulator sekarang akan melangkah melalui input seperti biasa. Klik langkah lain tiga kali untuk menemukan konfigurasi menerima. Konfigurasi menerima adalah berwarna hijau:

Menerima konfigurasi yang ditemukan

Jika kita klik langkah lagi, kita akan melihat bahwa konfigurasi terakhir ditolak. Dengan demikian, ada hanya satu menerima konfigurasi. Namun, kita mungkin tidak yakin bahwa hal ini benar-benar terjadi, karena kami telah menghapus beberapa konfigurasi. Kita dapat Periksa oleh ulang simulator.

Reset simulator

Pada setiap titik dalam simulasi, kita dapat mulai seluruh simulasi proses dengan mengklik Reset. Ini akan menghapus semua konfigurasi saat ini dan restart simulasi. Jika kita klik Reset dan langkah semua konfigurasi, kita akan menemukan bahwa ada, memang, hanya satu menerima konfigurasi. Ini menyimpulkan walkthrough, meskipun ada lampiran mencatat beberapa fitur lain yang mendukung JFLAP.

Lampiran
Catatan

Untuk menambahkan catatan ke JFLAP file, memilih Editor atribut, klik kanan dan pilih "Tambahkan catatan". Catatan akan mulai dengan pesan "insert_text". Untuk mengubah teks cukup klik dalam catatan, pilih mana Anda ingin mulai mengetik, dan mengetik catatan Anda. Klik di luar catatan untuk menyingkirkan kursor. Klik dan seret catatan untuk memindahkannya.

<

Pilihan

Untuk memilih lebih dari satu negara bagian atau memblokir sekaligus, memilih editor atribut, klik pada ruang kosong, dan tarik mouse. Muncul kotak melompat-lompat dan semua negara dan blok dalam kotak dipilih, warna mereka sekarang biru. Untuk memindahkan Serikat dipilih sebagai sebuah kelompok, klik dan seret mereka. Untuk Hapus mereka, klik di tempat lain.

Tata letak perintah (per JFLAP versi 6.2)

JFLAP sekarang akan membiarkan Anda menerapkan standar grafik layout perintah untuk grafik Anda, yang dapat membantu dengan lebih estetis menyenangkan grafik. Ada menu baru di jendela editor robot, "Lihat" menu, yang akan memungkinkan seseorang untuk menyimpan tata letak grafik saat ini dan untuk menerapkan grafik yang berbeda tata letak perintah dan algoritma. Untuk tutorial lengkap tentang cara menggunakan fitur ini, dan untuk melihat Deskripsi perintah built-in layout, merasa bebas untuk membaca layout perintah tutorial.
Berikut ini adalah gambar dari robot terbatas digunakan sebelumnya, ex1.3a.jff, dengan grafik layout baru. Gambar pertama menunjukkan robot di bawah "GEM" tata letak algoritma, yang kedua di bawah "Pohon (derajat, vertikal)" tata letak algoritma, dan yang terakhir di bawah "Dua lingkaran" tata letak algoritma.

Ini mengakhiri tutorial singkat kami membangun automata terbatas. Terima kasih untuk membaca