Sabtu, 18 Mei 2013

Aplikasi Automata JFLAP

Aplikasi Automata JFLAP




JFLAP mendefinisikan otomaton terbatas (FA) M Quadraple M = (Q, Σ, Δ, qs, F) mana
Q adalah seperangkat terbatas Serikat {qsaya | saya adalah bulat nonnegative}
Σ adalah alfabet input terbatas
Δ adalah fungsi transisi, δ: D → 2Q dimana D adalah subset terbatas dari Q × Σ *
qs (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 = {bmn : 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.)
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.
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.
Sewenang-wenang, kami memutuskan bahwa q0 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 q0. 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 q0 untuk menunjukkan bahwa itu adalah keadaan awal.
q0 didefinisikan sebagai keadaan awal
Selanjutnya, mari kita membuat keadaan akhir. Sewenang-wenang, kami memilih q1 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.
q1 didefinisikan sebagai keadaan akhir
Sekarang bahwa kita telah didefinisikan Serikat awal dan akhir, mari kita beralih ke menciptakan transtitions.
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 q0 loop kembali kepada dirinya sendiri.
Untuk membuat sebuah transisi, pertama Pilih alat pencipta transisi dari toolbar. Selanjutnya, klik pada q0 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 q0 harus ke keadaan akhir, sebagai sebuah string yang berakhir dengan satu b harus diterima. Untuk membuat transisi dari keadaan awal kami q0 untuk kami keadaan akhir q1, pertama memastikan bahwa alat pencipta transisi dipilih di toolbar. Selanjutnya, klik dan tahan pada q0, dan tarik mouse untuk q1 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 q1 memiliki transisi keluar pada b, yang tidak bisa loop kembali ke q1. Ada dua pilihan untuk transtion: itu dapat pergi ke keadaan awal q0, atau ke negara baru, misalnya, q2.
Jika transisi pada b ke keadaan awal q0, string tidak akan menjadi bentuk bmn; string seperti ababab juga akan diterima. Justru, transisi tidak bisa untuk q0dan itu harus untuk q2.
Membuat transisi b dari q1 q2. FA harus menerima string yang berakhir dengan angka ganjil b, membuat transisi lain pada b dari q2 q1. FA Anda adalah sekarang penuh bekerja FA! Seharusnya terlihat seperti ini:
Kerja FA
Anda mungkin melihat bahwa q3 tidak digunakan dan dapat dihapus. Selanjutnya, kami akan menjelaskan bagaimana menghapus Serikat dan transisi.
Menghapus Serikat dan transisi
Untuk menghapus q3, pertama Pilih alat Deletor di toolbar. Selanjutnya, klik pada negara q3. Jendela editor Anda sekarang harus terlihat seperti ini:
q3 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 q3 dan q9, 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, q3 dan q9 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 q1 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 q1 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 q1, NFA mengambil kedua transisi ke q2 dan q9. Sebagai q9 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 q11, 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 q0 dan membawa transisi ke q1 setelah pengolahan pertama . Setelah memproses kedua , itu di q11. Meskipun q11 tidak berdekatan q1, bisa dicapai dengan mengambil λ-transisi dari q9. Seperti simulator mencoba untuk memproses berikutnya pada konfigurasi ini, menyadari bahwa ada yang tidak keluar transisi dari q11 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 q11 atau q6 dan simbol masukan yang berikutnya adalah akan ditolak.
Sebagai simbol masukan berikutnya , kita dapat mengatakan bahwa konfigurasi yang sedang dalam t6 dan q11 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 q3 tidak akan mengarah ke konfigurasi menerima. Kita dapat menguji ide kami keluar dengan membekukan konfigurasi lainnya.
Pembekuan dan pencairan konfigurasi
Untuk membekukan konfigurasi pada q10, klik pada q10 sekali, kemudian klik tombol membeku . Ketika konfigurasi beku, itu akan menjadi berwarna gelap warna ungu:

Konfigurasi pada q10 beku
Dengan konfigurasi yang beku, ketika Anda mengklik langkah untuk langkah melalui konfigurasi pada q3, konfigurasi beku tetap sama. Mengklik langkah dua kali akan mengungkapkan bahwa konfigurasi pada q3 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

Tidak ada komentar:

Posting Komentar