Apakah mungkin untuk meminimalkan automata pushdown?

8

Apakah mungkin untuk meminimalkan automata pushdown? Jika tidak, mengapa? Apakah karena untuk minimalisasi, kelas ekivalensi perlu memiliki indeks yang terbatas dan kami tidak dapat menjaminnya untuk CFG?

computability automata pushdown-automata Tom J.
sumber

Jawaban:

8

Sayangnya masalahnya tidak dapat dihitung. Bahkan tidak dapat dipastikan apakah dua PDA sewenang-wenang setara; meminimalkan PDA bahkan lebih sulit.

DW
sumber
6

Saya pada dasarnya menjawab pertanyaan yang sama (lebih umum) di sini .

Argumen singkatnya: jika Anda bisa melakukan ini, Anda dapat memutuskan universalitas, dan beberapa properti PDA / CFG yang tidak dapat ditentukan. Karenanya, dengan reduksi, tidak mungkin ada minimizer seperti itu.

Raphael
sumber
4

Maaf, kecilkan dalam hal apa?

Setiap PDA memiliki yang setara memiliki satu negara.

Hendrik Jan
sumber
Hah, benar. :) Saya kira "ukuran penyandian yang masuk akal", misalnya tabel transisi. Jawaban lain akan berhasil dengan itu, bukan?
Raphael
2

Saya tidak tahu tentang meminimalkan cara Anda melakukannya dengan automata non-pushdown, tapi ...

Anda dapat mengonversi CFG ke PDA kan? Dan konversi itu menurut Hopcroft hanya memiliki satu keadaan, yang sangat diminimalkan bukan begitu? Jadi, yang harus Anda lakukan adalah, mengonversi PDA Anda menjadi CFG, dan kemudian CFG Anda kembali ke PDA, Anda akan memiliki 1-state PDA.

H_DANILO
sumber
Perhatikan bahwa ini adalah negara-minimal, tetapi bukan transisi minimal. Seperti kata DW, menjadikannya transisi dan status minimal tidak dapat dihitung.
jmite
0

"kecilkan" biasanya berarti "minimum global" tetapi kadang-kadang dapat merujuk pada "minimum lokal" dalam hal ini terdapat heuristik yaitu strategi yang dapat menghasilkan beberapa pengurangan tetapi tidak secara konsisten menemukan minimum global. dan juga beberapa kelas khusus PDA dapat diminimalkan atau "dipangkas". Algoritma optimisasi pembelajaran mesin "tidak dijamin dihentikan", misalnya algoritma genetika dapat digunakan di sini juga. di sini ada dua makalah tentang "tampak menekan automata" sebuah subclass. 2 contoh makalah di sepanjang baris ini:

vzn
sumber