Pertanyaan yang diberi tag ?regular-expressions?

Pertanyaan tentang ekspresi reguler, formalisme untuk menggambarkan bahasa reguler.

4
Bagaimana cara mengubah automata terbatas ke ekspresi reguler?
Mengubah ekspresi reguler menjadi (minimal) NFA yang menerima bahasa yang sama adalah mudah dengan algoritma standar, misalnya algoritma Thompson . Namun, arah yang lain tampaknya lebih membosankan, dan terkadang ekspresi yang dihasilkannya berantakan. Algoritma apa yang ada untuk mengubah NFA menjadi ekspresi reguler yang setara? Apakah ada keuntungan terkait kompleksitas …

1
Apakah Regex golf NP-Complete?
Seperti yang terlihat di strip XKCD terbaru ini dan posting blog terbaru inidari Peter Norvig (dan sebuah kisah Slashdot yang menampilkan yang terakhir), "golf regex" (yang mungkin lebih baik disebut masalah pemisahan ekspresi reguler) adalah teka-teki untuk menentukan ekspresi reguler sesingkat mungkin yang menerima setiap kata pada set A dan …

4
Bagaimana cara mensimulasikan backreferences, lookaheads, dan lookbehinds di automata state yang terbatas?
Pertanyaan ini dimigrasikan dari Stack Overflow karena dapat dijawab di Computer Science Stack Exchange. Bermigrasi 7 tahun yang lalu . Saya membuat ekspresi reguler sederhana lexer dan parser untuk mengambil ekspresi reguler dan menghasilkan pohon parsenya. Membuat otomat keadaan terbatas non-deterministik dari pohon parse ini relatif sederhana untuk ekspresi reguler …

6
Apa Hubungan Antara Bahasa Pemrograman, Ekspresi Reguler, dan Bahasa Formal
Saya telah mencari-cari jawaban untuk pertanyaan ini dan kelihatannya semua orang secara implisit tahu jawabannya kecuali saya. Agaknya ini karena satu-satunya orang yang peduli adalah mereka yang pernah memiliki pendidikan tinggi tentang hal itu. Saya, di sisi lain, telah dilemparkan ke dalam untuk tugas sekolah menengah. Pertanyaan saya adalah, bagaimana …



1
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 …

2
Untuk setiap regex 'jahat', apakah ada alternatif yang tidak jahat, atau apakah iblis ada dalam tata bahasa?
Rupanya, serangan ReDos mengeksploitasi karakteristik dari beberapa ekspresi reguler (yang berguna) ... pada dasarnya menyebabkan ledakan jalur yang mungkin melalui grafik yang ditentukan oleh NFA. Apakah mungkin untuk menghindari masalah seperti itu dengan menulis regex 'non-evil' yang setara? Jika tidak (dengan demikian, tata bahasa tidak dapat ditangani di ruang / …


2
Apakah teka-teki silang regex NP-keras?
Saya bermain-main beberapa hari lalu di situs web ini: http://regexcrossword.com/ dan itu membuat saya bertanya-tanya apa cara terbaik untuk menyelesaikannya. Bisakah Anda memecahkan masalah berikut dalam waktu polinomial atau NP-keras? Diberi kisi NxM dengan N ekspresi reguler untuk kolom dan M untuk baris, temukan solusi apa pun untuk kisi sehingga …


1
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 …

4
Mengapa tidak ada permutasi di Regex? (Bahkan jika bahasa reguler tampaknya dapat melakukan ini)
Masalah Tidak ada cara mudah untuk mendapatkan permutasi dengan regex. Permutasi: Mendapatkan kata ("aabc") ke urutan lain, tanpa mengubah jumlah atau jenis huruf.w=x1…xnw=x1…xnw=x_1…x_n Regex: Ekspresi reguler. Untuk verifikasi: "Regex permutasi tanpa pengulangan" Jawabannya menciptakan kode JavaScript, bukan regex, dengan asumsi ini akan lebih sederhana. "Bagaimana menemukan semua permutasi dari kata …

3
Bahasa reguler yang tidak dapat diekspresikan dengan hanya 2 operasi regex
Saya pikir semua bahasa reguler dapat diekspresikan dengan ekspresi reguler (jika suatu bahasa biasa, dapat diekspresikan dengan regex), tetapi saya telah diberitahu bahwa Anda memerlukan ketiga operasi reguler (penggabungan, penyatuan, dan bintang) untuk itu untuk menahan. Sebagai contoh, saya telah diberitahu bahwa jika saya hanya dapat menggunakan operasi regex gabungan …


Dengan menggunakan situs kami, Anda mengakui telah membaca dan memahami Kebijakan Cookie dan Kebijakan Privasi kami.
Licensed under cc by-sa 3.0 with attribution required.
Judi bola