Push Down Automata (PDA) merupakan mesin otomata dari bahasa bebas konteks. PDA di gambarkan sebagai tempat penyipanan yang tidak terbatas berupa stack/tumpukan.
Stack ialah kumpulan dari elemen-elemen sejenis dengan sifat penambahan elemen dan pengambilan elemen melalui suatu tempat yang disebut top of stack (puncak stack). Prinsip pada stack adalah LIFO. Pengambilan elemen dari stack dinyatakan dengan operasi pop, sedang memasukkan elemen ke dalam stack dengan operasi push.:)
Push Down Automata (PDA) merupakan mesin otomata dari bahasa bebas konteks. PDA di gambarkan sebagai tempat penyipanan yang tidak terbatas berupa stack/tumpukan.
Stack ialah kumpulan dari elemen-elemen sejenis dengan sifat penambahan elemen dan pengambilan elemen melalui suatu tempat yang disebut top of stack (puncak stack). Prinsip pada stack adalah LIFO. Pengambilan elemen dari stack dinyatakan dengan operasi pop, sedang memasukkan elemen ke dalam stack dengan operasi push.
automata Pushdown berbeda dari mesin negara yang terbatas dalam dua cara:
Mereka dapat menggunakan atas tumpukan untuk menentukan transisi untuk mengambil.
Mereka dapat memanipulasi stack sebagai bagian dari melakukan transisi.
Pushdown transisi otomata memilih dengan mengindeks meja dengan sinyal input, negara saat ini, dan simbol di bagian atas dari stack. Ini berarti bahwa ketiga parameter sepenuhnya menentukan jalur transisi yang dipilih. Hingga mesin negara hanya melihat sinyal masukan dan negara saat ini: mereka tidak memiliki stack untuk bekerja dengan. Pushdown automata menambahkan stack sebagai parameter untuk pilihan.
automata Pushdown juga dapat memanipulasi stack, sebagai bagian dari melakukan transisi. Hingga mesin negara memilih negara baru, hasil berikut transisi. manipulasi ini dapat mendorong simbol tertentu ke puncak stack, atau untuk pop dari atas tumpukan. robot ini alternatif dapat mengabaikan tumpukan, dan biarkan sebagaimana adanya. Pemilihan manipulasi (atau manipulasi tidak) ditentukan oleh tabel transisi.
Masukkan bersama-sama: Mengingat sinyal input, negara saat ini, dan stack simbol, robot dapat mengikuti transisi ke negara lain, dan secara opsional memanipulasi (push atau pop) stack.
Dalam automata pushdown umum mungkin memiliki beberapa perhitungan string masukan yang diberikan, beberapa yang mungkin tersendat-sendat dalam menerima konfigurasi sementara yang lain tidak. Jadi kami memiliki model yang secara teknis dikenal sebagai "otomat pushdown nondeterministic" (NPDA). Nondeterminism berarti bahwa mungkin ada lebih dari satu transisi yang tersedia untuk mengikuti, diberi sinyal input, negara, dan simbol stack. Jika dalam setiap situasi hanya satu transisi tersedia sebagai kelanjutan dari perhitungan, maka hasilnya adalah otomat pushdown deterministik (DPDA), yang lebih lemah perangkat ketat.
Jika kita mengizinkan akses otomat hingga ke dua tumpukan bukan hanya satu, kita mendapatkan perangkat yang lebih kuat, setara dalam daya ke mesin Turing . Sebuah robot dibatasi linier adalah perangkat yang lebih kuat daripada robot pushdown tetapi kurang daripada mesin Turing.
automata Pushdown yang setara dengan tata bahasa bebas konteks : untuk setiap tata bahasa bebas konteks, ada robot pushdown seperti bahwa bahasa dihasilkan oleh tata bahasa identik dengan bahasa yang dihasilkan oleh robot, yang mudah untuk membuktikan. sebaliknya adalah benar, meskipun sulit untuk membuktikan: untuk setiap otomat pushdown terdapat tata bahasa bebas konteks seperti bahwa bahasa yang dihasilkan oleh robot identik dengan bahasa dihasilkan oleh tata bahasa.
0 komentar:
Posting Komentar