Saya telah membaca beberapa makalah teori bahasa formal, dan saya menemukan istilah yang tidak saya mengerti.
Makalah ini akan sering merujuk pada satu set yang "ditutup secara efektif di bawah persimpangan" atau operasi lainnya. Apa arti "efektif" di sini? Apa bedanya dengan penutupan normal?
Sebagai referensi, makalah yang saya lihat ini adalah:
M. Daley dan I. McQuillan. Pemodelan formal kompresi gen virus. International Journal of Foundations of Computer Science, 16 (3): 453–469, 2005.
"Tutup secara efektif" berarti bahwa keluarga ditutup di bawah operasi, dan bahwa penutupan dapat dihitung dengan memberikan otomat / tata bahasa untuk itu (jika bahasa asli juga diberikan dalam representasi yang efektif). Misalnya, diberi otomat keadaan terbatas, kita dapat benar-benar menemukan otomat untuk pelengkap.
Maka itu adalah pertanyaan wajar, apakah ada contoh properti penutupan yang tidak efektif. Saya tahu satu sekarang. Untuk bahasa reguler dan bahasa apa pun , hasil bagi lagi teratur. Tidak ada cara yang efektif untuk membangun FSA untuk hasil bagi itu jika eg misalnya rekursif.