Saya bertanya-tanya tentang kumpulan bahasa apa yang dihasilkan oleh pembatasan ekspresi reguler. Andaikan semua batasan memiliki simbol konstan untuk setiap elemen dan gabungan. Kemudian delapan kelas dapat dibentuk dengan ada atau tidak adanya komplemen / negasi, alterasi / persatuan, dan bintang Kleene. (Ya, ekspresi reguler 'normal' tidak memiliki operator C , tetapi lebih nyaman di sini.)
Ekspresi yang memungkinkan pergantian dan bintang Kleene, dengan atau tanpa komplemen (apa yang merupakan ledakan ganda eksponensial ganda di antara teman?), Menghasilkan bahasa biasa. Ekspresi yang memungkinkan pergantian dan pelengkap tetapi bukan bintang Kleene yang menghasilkan bahasa bebas bintang. Ekspresi yang memungkinkan pergantian tetapi tidak melengkapi atau bintang Kleene menghasilkan bahasa yang terbatas.
Tetapi bisakah kelas bahasa yang menarik dihasilkan tanpa bergantian? Tanpa salah satu dari tiga operator semua yang dapat dihasilkan adalah satu kata. Operator pelengkap tidak banyak membantu di sini.
Hanya dengan bintang Kleene kelasnya agak menarik ... tidak jelas apakah mereka dapat dikenali lebih cepat daripada bahasa biasa. (Apakah ada yang tidak diketahui tentang hal ini?)
Dengan bintang Kleene dan pelengkap ... apakah Anda mendapatkan sesuatu yang menarik? Apakah kelas ini memiliki nama?
Pertanyaan ini terinspirasi oleh pertanyaan Ekspresi Reguler pada math.se.
Jawaban:
Kelas bahasa reguler yang dapat dijelaskan dengan ekspresi reguler tanpa penyatuan (dan tanpa pelengkap) dikenal sebagai bahasa biasa yang bebas serikat (juga: bintang-reguler ). Kelas bahasa ini tampaknya telah mendapat perhatian baru-baru ini:
Benedek Nagy: "Bahasa reguler bebas-serikat dan 1-jalur-bebas-automata", Publicationes Mathematicae 68 (1-2), 2006.
Sergey Afonin dan Denis Golomazov: "Minimal Dekomposisi Bebas Bahasa Reguler", Teori dan Aplikasi dan Teori Automata, Springer 2009.
Galina Jirásková dan Tomás Masopust: "Kompleksitas dalam Bahasa Reguler Bebas Union", Perkembangan dalam Teori Bahasa, Springer 2010.
sumber