Ekspresi reguler “Padat” menghasilkan

Berikut dugaan untuk ekspresi reguler:

Untuk ekspresi reguler , biarkan panjang | R | menjadi jumlah simbol di dalamnya, mengabaikan tanda kurung dan operator. Misalnya | 0 ∪ 1 | = | ( 0 ∪ 1 ) ∗ | = $R$$|R|$$|0 \cup 1| = |(0 \cup 1)^*| = 2$

Dugaan: Jika dan L ( R ) berisi setiap string dengan panjang | R | atau kurang, maka L ( R ) = Σ ∗ .$|R| > 1$$L(R)$$|R|$$L(R) = \Sigma^*$

Artinya, jika adalah 'padat' hingga R panjang 's, maka R benar-benar menghasilkan segalanya.$L(R)$$R$$R$

Beberapa hal yang mungkin relevan:

1. Hanya sebagian kecil dari yang diperlukan untuk menghasilkan semua string. Misalnya dalam biner, R = ( 0 ∪ 1 ) * ∪ S akan bekerja untuk setiap S .$R$$R = (0 \cup 1)^* \cup S$$S$
2. Perlu ada bintang Kleene di di beberapa titik. Jika tidak ada, itu akan kehilangan beberapa string ukuran kurang dari | R | .$R$$|R|$

Akan menyenangkan untuk melihat bukti atau contoh tandingan. Apakah ada beberapa kasus di mana itu jelas salah aku rindu? Adakah yang pernah melihat ini (atau yang serupa) sebelumnya?

Dugaan Anda dibantah oleh Keith Ellul, Bryan Krawetz, Jeffrey Shallit dan Ming-wei Wang dalam makalah mereka "Ekspresi Reguler: Hasil Baru dan Masalah Terbuka". Meskipun makalah tidak tersedia secara online, pembicaraan tetap dilakukan.

Di koran, mereka mendefinisikan ukuran , yang merupakan jumlah simbol dalam R , tidak termasuk ϵ atau ∅ . Namun, ∅ dapat dihilangkan dari setiap ekspresi yang tidak menghasilkan bahasa kosong, dan ekspresi tersebut dapat "dibersihkan" sehingga jumlah ϵ yang dikandungnya paling banyak | a l p h ( R ) | (Lemma di halaman 10 dari pembicaraan).$|\mathrm{alph}(R)|$$R$$\epsilon$$\emptyset$$\emptyset$$\epsilon$$|\mathrm{alph}(R)|$

Pada halaman 51, untuk setiap mereka membangun ekspresi reguler ukuran O ( n ) di atas { 0 , 1 } yang menghasilkan semua string ukuran paling banyak Ω ( 2 n n ) , tetapi tidak menghasilkan semua string. Perhatikan bahwa "ukuran" di sini sesuai dengan pengertian Anda dan milik mereka, karena kami menggunakan notasi O-besar. Mereka juga mengajukan pertanyaan terbuka untuk menemukan ketergantungan terbaik antara dua parameter.$n \geq 3$$O(n)$$\{0,1\}$$\Omega(2^n n)$