Bisakah POSIX BRE mengekspresikan semua bahasa reguler?

Tampaknya "Ekspresi Reguler Dasar" seperti yang didefinisikan oleh POSIX.1-2008 tidak mendukung pergantian, a|b(meskipun beberapa implementasi grep mengenali versi yang lolos, \|).

Karena bahasa reguler ditutup di bawah penyatuan menurut definisi, apakah ini berarti bahwa POSIX BRE memiliki daya ekspresif yang kurang dari otomat terbatas? Atau ada beberapa cara untuk mensimulasikan pergantian menggunakan konstruksi lain?

Memang bahasa POSIX BRE tidak dapat mengekspresikan semua ekspresi reguler karena tidak memiliki pergantian. Ia bahkan tidak bisa mengenali semua bahasa hingga, apalagi semua bahasa biasa.

Misalnya, tidak dikenali sebagai BRE. Untuk membuktikan ini, pertimbangkan bentuk sintaksis tingkat atas yang mana:$\{ab, ba\}$

• Itu tidak dapat menjadi salah satu bentuk karakter tunggal karena bahasa tersebut memiliki kata-kata panjang .$\gt 1$
• Tidak boleh karena itu akan cocok dengan string kosong.$R^*$
• Tidak boleh kecuali dengan (dalam hal ini kita kembali ke masalah semula) karena itu akan cocok dengan string dengan panjang berbeda atau string kosong.$R^{\{m,n\}}$$m=n=1$
• Jadi itu harus Rangkaian: . Sekarang pertimbangkan bagaimana diakui: $R_1 R_2$$ab$
  • Jika mengenali maka tidak boleh mengenali apa pun selain string kosong. Jadi harus mengenali dan kami kembali ke masalah semula.$R_1$$ab$$R_2$$R_1$$\{ab,ba\}$
  • Jika mengakui tapi tidak maka harus mengakui . Tapi kemudian mengakui semua kata dari bentuk mana mengakui , sehingga tidak harus mengakui apa pun selain . Tidak ada cara untuk mengenali .$R_1$$a$$ab$$R_2$$b$$R_1R_2$$u b$$R_1$$u$$R_1$$a$$ba$
  • Jika tidak mengenali atau maka satu-satunya cara bagi untuk mengenali adalah jika mengenali string kosong, dalam hal ini kita kembali ke masalah semula seperti di atas, tetapi untuk kali ini. a b a R a b R 1 R $R_1$$ab$$a$$R$$ab$$R_1$$R_2$

Ketika "kita kembali ke masalah awal", itu berarti bahwa satu-satunya solusi untuk menemukan BRE mengenali bahasa adalah dengan menemukan BRE yang lebih kecil yang memiliki properti yang sama. Ini adalah keturunan tanpa batas , jadi tidak ada BRE yang memiliki properti yang diinginkan.

Saya tidak berpikir ada karakterisasi "baik" dari bahasa yang dapat dikenali BRE, misalnya sebagai bahasa yang dikenali oleh kelas automata "baik".

Perhatikan bahwa bahasa yang dikenali BRE sebenarnya bukan subkelas dari bahasa biasa, karena referensi balik menambah kekuatan ekspresif. Misalnya dikenali oleh BRE tetapi terkenal tidak teratur. BRE tanpa backreferensi hanyalah gula sintaksis di atas ekspresi reguler sehingga bahasa yang dapat mereka kenali adalah subkelas dari bahasa biasa.$\{w w \mid w \in \{a,b\}^*\}$\(.*\)\1