Saya pikir semua bahasa reguler dapat diekspresikan dengan ekspresi reguler (jika suatu bahasa biasa, dapat diekspresikan dengan regex), tetapi saya telah diberitahu bahwa Anda memerlukan ketiga operasi reguler (penggabungan, penyatuan, dan bintang) untuk itu untuk menahan.
Sebagai contoh, saya telah diberitahu bahwa jika saya hanya dapat menggunakan operasi regex gabungan dan gabungan (2 dari 3), akan ada bahasa reguler yang tidak dapat saya gambarkan hanya dengan keduanya.
Sama dengan bintang dan persatuan Kleene saja. Apa saja contohnya?
sumber
sumber
Jika seseorang sekarang memungkinkan untuk menggunakan bintang, tetapi bukan bintang bersarang , maka itu merupakan masalah terbuka (setidaknya selama 45 tahun) untuk mengetahui apakah seseorang dapat memperoleh semua bahasa reguler. Pertanyaan ini dikenal sebagai masalah ketinggian bintang umum . Ini mirip dengan masalah ketinggian bintang yang disebutkan oleh Yuval Filmus, dengan perbedaan bahwa komplementasi sekarang diperbolehkan.
sumber