Kapan regexp bukan Ekspresi Reguler?

Karena saya sedang belajar untuk kursus bahasa formal di perguruan tinggi, saya menemukan tulisan-tulisan menarik ini ( Satu Dua ) yang menggambarkan bagaimana menemukan bilangan prima menggunakan regexp . Seperti yang saya katakan, regexp , bukan ekspresi reguler . Karena ekspresi reguler dapat mencocokkan string yang dihitung oleh Finite State Automata dan menemukan bilangan prima tidak dapat dilakukan oleh FSA, regexp yang diperlihatkan dalam posting blog tidak sepenuhnya merupakan ekspresi reguler karena ia mundur untuk mencocokkan string.

Karena saya tidak pernah menggunakan ekspresi reguler, sekarang, pertanyaan saya:

Bagaimana saya bisa langsung mengenali regexp dari ekspresi reguler "benar" hanya dengan melihatnya?

Definisi: Dengan ekspresi reguler, saya merujuk pada gagasan sebagaimana didefinisikan dalam bahasa formal. Dengan regexp, maksud saya gagasan yang didukung oleh bahasa pemrograman modern; sintaksis regexp sering berisi fitur tambahan, seperti referensi-kembali. Regexps seperti yang terlihat dalam bahasa pemrograman lebih kuat daripada ekspresi formal gaya bahasa formal.

tl; dr backrefs.

Segera setelah ada \1(atau nomor apa pun yang tidak digunakan untuk keluar dari unicode) di regexp itu bukan ekspresi reguler.

Backrefs memungkinkan Anda untuk mencocokkan pertandingan (a+)b\1mana yang n kali adiikuti oleh b diikuti oleh n kali auntuk n> 1. Ini bukan bahasa biasa (ini adalah anak poster dari bahasa yang tidak biasa).

Diperlukan dan hampir mencukupi bahwa backref mereferensikan grup yang berisi regexp yang cocok dengan string panjang sewenang-wenang atau bahwa itu berisi a *atau +. Satu-satunya pengecualian (yang saya temukan) dari regexp dari bentuk di (A)B\1mana A adalah bahasa yang terbatas (dapat digantikan dengan penghitungan semua kata yang menerimanya). Anda dapat mengonversinya ke word1+Bword1|word2+Bword2dll. Karena A terbatas.

Grup look-around tidak menghilangkan keteraturan regexp. A(?=B)Cadalah penampang regex AB.*dan ACdan penampang 2 bahasa reguler adalah reguler. Lookahead negatif serupa kecuali menggunakan pelengkap B.*(pelengkap bahasa reguler menjadi reguler). Lookbehind persis sama juga A(?<=B)Cadalah penampang ACdan .*BC.