Dapatkah regex yang mengandung quantifier nongreedy (enggan) ditulis ulang untuk tidak menggunakannya?

Pertimbangkan bahasa regex dengan quantifier greedy , quantifier nongreedy, pergantian kelas, dan kelas karakter. (Ini pada dasarnya adalah sebuah subbahasa dari PCRE tanpa referensi balik, pernyataan sekilas, atau beberapa bit lain yang lebih menarik.)$*$${*}?$

Sebuah pertandingan untuk untuk regex pada tali adalah interval setengah terbuka lebih sehingga diterima oleh .$[a_0,a_1)$$R$$s = s_0\dots s_n$$\mathbb{N}$$s_{a_0}\dots s_{a_1-1}$$R$

Kami memberikan definisi rekursif dari apa yang membuat satu pertandingan lebih baik daripada yang lain. Sebuah pertandingan untuk regex R pada string adalah lebih baik daripada pertandingan lain b = [ b 0 , b 1 ) jika suatu 0 < b 0 atau, jika sebuah 0 = b 0 dan:$a = [a_0,a_1)$$R$$b = [b_0,b_1)$$a_0 < b_0$$a_0 = b_0$

• Jika adalah kelas karakter: Kelas karakter memiliki kecocokan unik, sehingga semua kecocokan pada posisi yang sama untuk R adalah sama. Karenanya kasus ini tidak mungkin.$R$$R$

• Jika :$R = ST$

  • Bagian utama dari adalah kecocokan yang lebih baik untuk S daripada bagian terkemuka dari b , atau$a$$S$$b$
  • Bagian terdepan dari dan b adalah kecocokan yang sama baiknya untuk S , dan bagian tambahan dari a adalah kecocokan yang lebih baik untuk T daripada bagian akhir dari b .$a$$b$$S$$a$$T$$b$

• Jika :$R = S|T$

  • adalah kecocokan untuk S dan b tidak, atau$a$$S$$b$
  • dan b adalah pertandingan sama baik untuk S dan sebuah merupakan pertandingan yang lebih baik untuk S dari b , atau$a$$b$$S$$a$$S$$b$
  • dan b tidak cocok untuk S tetapi pertandingan untuk T , dan sebuah merupakan pertandingan yang lebih baik untuk T dari b adalah.$a$$b$$S$$T$$a$$T$$b$

Semua bentuk sintaksis lainnya mengurangi ke tiga di atas untuk tujuan prioritas pertandingan:

• : R ≡ S 0 | S 1 | $R = S{*}$$R \equiv S^0|S^1|\dots$
• : R ≡ … | S 1 | S $R = S{*}?$$R \equiv \dots|S^1|S^0$

Pola tak terhingga ini digunakan hanya untuk tujuan prioritas pertandingan --- mereka bukan bagian dari bahasa pertandingan yang sedang dipertimbangkan.

Relasi "yang lebih baik" adalah urutan linier yang lemah pada semua kecocokan yang memungkinkan untuk suatu pola tertentu.

Sebut dua regexes pertandingan-setara jika, untuk setiap string input yang terbatas, set berpasangan menguraikan pertandingan terbaik untuk S sama dengan set berpasangan menguraikan pertandingan terbaik untuk T .$S,T$ $S$$T$

T: Apakah ini kasus bahwa untuk setiap regex mengandung quantifier nongreedy ∗ ? ada regex T yang setara dengan pertandingan yang tidak mengandung penjumlahan nongreedy?$S$${*}?$$T$

Sunting: Ini adalah penulisan ulang lengkap pertanyaan untuk memperjelas apa yang ditanyakan.

Jawaban ini didasarkan pada asumsi bahwa kesetaraan dua regex didefinisikan karena mereka mengenali bahasa yang sama. Itu tidak menjawab pertanyaan saat ini.

Anda memiliki kesalahpahaman umum bahwa quantifier yang enggan mengubah rangkaian string yang cocok dengan ekspresi reguler. Tidak, dan hanya mengubah opsi mana yang dicoba terlebih dahulu.

Misalnya, jika Anda melakukan kecocokan regex 'aaaa' =~ /a+/di Perl, ia menemukan kecocokan pertama dalam string aaaa, dan mengingat substring yang cocok dengan variabel khusus. Bahkan jika ada lebih dari satu substring aaaayang cocok dengan regex yang diberikan, pertandingan selain dari pertandingan pertama diabaikan.

Apakah bilangan bulat serakah atau enggan mempengaruhi pertandingan pertama di antara banyak pertandingan, tetapi rangkaian pertandingan tidak berubah. Dalam hal ini, rangkaian string yang cocok dengan regex tidak berubah, tidak peduli apakah Anda menggunakan quantifier serakah biasa atau quantifier enggan.