Bahasa reguler yang tidak dapat diekspresikan dengan hanya 2 operasi regex

12

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?

pengguna3295674
sumber

Jawaban:

19

Dengan hanya penyatuan dan penggabungan, Anda tidak dapat menjelaskan bahasa tanpa batas. Penyatuan dan penggabungan hanya dapat menghasilkan banyak string. Dengan hanya serikat dan tanda star, Anda tidak bisa menggambarkan bahasa seperti , karena tidak ada cara untuk menggabungkan sebuah pembangkit ekspresi hanya dengan pembangkit ekspresi hanya . Dengan hanya penggabungan dan bintang Kleene, Anda tidak dapat mendeskripsikan bahasa seperti .a b L = { a , b }L={ab}abL={a,b}

DylanSp
sumber
3
.... dan tidak dimungkinkan tanpa penyatuan. {a,b}
Raphael
Jadi mengapa saya tidak bisa menggambarkan L = {a, b} tanpa penyatuan? Apakah karena mereka tidak dapat direpresentasikan sebagai elemen terpisah dengan bintang dan rangkaian? Itu hanya bisa dilakukan ab, bb, aba dll?
user3295674
@ user3295674 Persis.
DylanSp
dan sesuatu seperti L = {a *} tidak akan mungkin hanya dengan penyatuan dan penggabungan, kan? Terima kasih banyak!
user3295674
Saya bahkan tidak mengerti bagaimana bintang akan didefinisikan tanpa tersedia concatenation.
G. Bach
11

(abc)dddd1

Yuval Filmus
sumber
4

A(ab)(a(ab)b)(aa)

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.

J.-E. Pin
sumber