Ekspresi reguler dengan referensi kembali di atas alfabet unary

Pengaturan:

ekspresi reguler dengan referensi kembali
bahasa unary (alfabet 1 simbol)

Apakah masalah berikut ini dapat ditentukan dalam pengaturan ini:

Diberi ekspresi reguler dengan referensi, apakah itu mendefinisikan bahasa biasa?

Misalnya, (aa+)\1mendefinisikan bahasa reguler, sementara (aa+)\1+tidak. Bisakah kita memutuskan yang mana masalahnya?

Untuk konkret, "ekspresi reguler dengan referensi-kembali" di sini merujuk ke misalnya subset berikut dari ekspresi reguler Perl-kompatibel yang biasa :

acocok dengan karakter a(satu-satunya karakter dalam alfabet)
X* cocok dengan 0 atau lebih kejadian dari X
X|Ycocok XatauY
tanda kurung dapat digunakan untuk pengelompokan dan pengambilan
\1. \2, dll. cocok dengan string yang sama dengan pasangan kurung 1, 2, dll

Kita juga dapat menggunakan steno normal mis X+= XX*.

formal-languages computability regular-languages undecidability regular-expressions Jukka Suomela
sumber

Sudahkah Anda menjelajahi pendekatan penghitungan, yaitu memeriksa urutan

? Saya kira Anda sudah familiar dengan karya Freydenberger?

| L_{n} |

$|L_n|$

Raphael

Jawaban:

Bukti terhadap decidability yang efektif dari masalah disediakan oleh konstruksi dalam bukti Teorema 9 dalam makalah saya Pada Ekspresi Praktis Biasa : Anda dapat menentukan apakah ada banyak bilangan prima Fermat yang halus.

Holger Petersen
sumber

Selamat datang di situs ini! Saya telah menambahkan kutipan yang lebih lengkap ke kertas Anda.

David Richerby