Ekspresi reguler tanpa pergantian

9

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.)ΣC

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.

Charles
sumber
apa arti pergantian? juga, itu "Kleene".
Suresh Venkat
1
@Suresh Venkat: Union, logical OR, |, /, ∪.
Charles
Perhatikan bahwa dalam konteks asli, kelas tidak memiliki komplemen tetapi memiliki referensi kembali.
Peter Taylor
@ Peter Taylor: Benar. Saya bermaksud untuk mengajukan pertanyaan tindak lanjut tentang referensi, tetapi saya pikir itu terlalu banyak untuk dimasukkan ke dalam pertanyaan ini.
Charles

Jawaban:

12

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.

Hermann Gruber
sumber
1
Bagus. Adakah yang diketahui tentang kekuatan tambahan dari komplementasi?
Charles
1
Koreksi singkat nitpicky: Makalah oleh Afonin dan Golomazov muncul di LATA 2009, bukan DLT 2009.
Dominik D. Freydenberger