Masalah

Tidak ada cara mudah untuk mendapatkan permutasi dengan regex.

Permutasi: Mendapatkan kata ("aabc") ke urutan lain, tanpa mengubah jumlah atau jenis huruf. $w = x_{1} \dots x_{n}$ $w=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 yang diberikan dalam teks yang diberikan" - Jawabannya tidak menggunakan regex juga.
"Regex untuk mencocokkan semua {1, 2, 3, 4} tanpa pengulangan" - Jawabannya menggunakan regex, tetapi itu tidak mudah beradaptasi atau sederhana.
Jawaban ini bahkan mengklaim: "Ekspresi reguler tidak dapat melakukan apa yang Anda minta. Itu tidak dapat menghasilkan permutasi dari string" .

Jenis solusi yang saya cari

Seharusnya berupa:

»Aabc« (atau apa pun yang Anda bisa menggunakan kurung buka dan tutup)
(aabc)! (mirip dengan (abc)? tetapi dengan simbol lain pada akhirnya)
[aabc]! (mirip dengan [abc] + tetapi dengan simbol lain pada akhirnya)

Keuntungan dari solusi ini

Mereka:

mudah
mudah beradaptasi
dapat digunakan kembali

Kenapa ini harus ada

Regex adalah cara untuk menggambarkan tata bahasa dari bahasa reguler. Mereka memiliki kekuatan penuh untuk menjadi jenis bahasa biasa.
Katakanlah, bahasa reguler cukup kuat untuk permutasi (bukti di bawah) - mengapa tidak ada cara mudah untuk mengekspresikan ini?

Jadi pertanyaan saya adalah:

(Kenapa) Apakah buktiku salah?
Jika benar: Mengapa tidak ada cara mudah untuk mengekspresikan permutasi?

Bukti

Ekspresi reguler adalah salah satu cara untuk memperhatikan tata bahasa bahasa reguler. Mereka dapat menjelaskan tata bahasa bahasa biasa.
Cara lain untuk menggambarkan bahasa biasa (yang memiliki jumlah huruf hingga dalam alfabet) terbatas adalah tata bahasa yang bukan deterministik (dengan jumlah negara terbatas).

Memiliki jumlah huruf yang terbatas saya dapat membuat otomat ini: (Contoh. Formal: lihat di bawah)

Tata bahasa yang menerima permutasi "abbc":

(coba nomor di atas, mungkin seseorang tahu cara membuat bagian ini terlihat lebih baik)

s -> ah¹

s -> bh²

s -> ch³

h¹ -> bh¹¹

h¹ -> ch¹²

h² -> ah¹¹ (tidak ada kesalahan ketik!)

h² -> bh²²

h² -> ch²³

h³ -> ah¹²

h³ -> bh²³

h¹¹ -> bc

h¹¹ -> cb

h¹² -> bb

h²² -> ac

h²² -> ca

h²³ -> ab

h²³ -> ba

Lebih formal: (menggunakan finite-state-automaton tetapi ini bisa dibuat dengan tata bahasa juga)

Sebuah kata q (dengan panjang terbatas) yang permutasi apa pun harus mencapai kondisi penerimaan.
X adalah alfabet terbatas.
Set of state S berisi urutan huruf apa saja hingga panjang q. (Jadi ukuran S adalah terbatas.) Ditambah satu status "any any word".
status transisi fungsi d yang mengambil huruf dan bergerak pada status yang sesuai dengan bagian kata yang sekarang dibaca.
F adalah himpunan yang menyatakan permutasi yang tepat dari q.

Jadi dimungkinkan untuk membuat otomat kondisi-terbatas untuk menerima permutasi dari kata yang diberikan.

Pindah dengan buktinya

Jadi saya telah membuktikan bahwa bahasa reguler memiliki kekuatan untuk memeriksa permutasi, bukan?

Jadi mengapa tidak ada pendekatan untuk mencapai ini dengan Regex? Ini fungsionalitas yang berguna.

formal-languages regular-languages regular-expressions Asqiir
sumber

10

Anda dapat membuat daftar semua permutasi kata Anda dengan ekspresi reguler. Ekspresi yang dihasilkan akan cukup besar, tetapi pasti akan menjadi ekspresi reguler.

Yuval Filmus

7

Saya sarankan mengabaikan semua jawaban tentang Teori Komputasi pada stackoverflow. Ini bukan spesialisasi situs itu.

Yuval Filmus

Jawaban pada halaman tertaut Anda di sini - stackoverflow.com/a/3102205/6936386 - tampaknya mudah diadaptasi dan tidak terlalu rumit: ^(a()|a()|b()|c()){4}\2\3\4\5$tampaknya berfungsi (lihat regex101.com/r/9URPpg/4/tests ).

boboquack

7

@ Boboquack Itu bukan ekspresi reguler dalam arti istilah yang digunakan dalam ilmu komputer. (Hal semacam inilah yang tepatnya Yuval sarankan untuk tidak mempercayai jawaban Stack Overflow tentang CS teoretis.)

David Richerby

37

Teorema dasar teori bahasa formal adalah bahwa ekspresi reguler, tata bahasa reguler, deterministic finite automata (DFAs) dan finite automata (NFA) deterministik semuanya menggambarkan jenis bahasa yang sama: yaitu bahasa reguler. Fakta bahwa kita dapat mendeskripsikan bahasa-bahasa ini dalam banyak cara yang sangat berbeda menunjukkan bahwa ada sesuatu yang alami dan penting tentang bahasa-bahasa ini, dengan cara yang sama seperti kesetaraan mesin Turing, kalkulus lambda dan segala macam hal lainnya menunjukkan bahwa bahasa yang dapat dihitung alami dan penting. Itu bukan hanya artefak dari keputusan acak apa pun yang dibuat oleh penemu asli.

Misalkan kita menambahkan aturan baru untuk menciptakan ekspresi reguler: jika $R$ adalah ekspresi reguler, maka $\pi(R)$ adalah ekspresi reguler, dan itu cocok dengan setiap permutasi dari setiap string yang cocok dengan $R$ . Jadi, misalnya, $L(\pi(abc)) = \{abc, acb, bac, bca, cab, cba\}$ . Masalahnya adalah ini melanggar kesetaraan mendasar yang dijelaskan di atas. $L\big(\pi((ab)^*))\big)$ adalah bahasa string yang berisi jumlah yang sama $a$ s dan $b$ dan ini bukan bahasa biasa. Bandingkan ini dengan, misalnya, menambahkan operator negasi atau pembalikan ke ekspresi reguler, yang tidak mengubah kelas bahasa yang diterima.

Jadi, untuk menjawab pertanyaan judul, ekspresi reguler tidak dapat melakukan permutasi dan kami tidak menambahkan kemampuan itu karena kemudian ekspresi reguler tidak akan cocok dengan bahasa biasa. Karena itu, ada kemungkinan bahwa "ekspresi reguler dengan permutasi" juga akan menjadi kelas bahasa yang menarik dengan banyak penokohan yang berbeda.

David Richerby
sumber

Tetapi L ((ab) *) juga bukan bahasa biasa - jadi L (perm ((ab) *)) tidak dapat menjadi satu. ((ab) * bukan bahasa biasa karena tidak ada jenis memori untuk mengingat berapa banyak pembukaan "a", jadi dengan jumlah negara terbatas Anda tidak dapat memasukkan jumlah yang sama "b".)

Asqiir

9

L ((a b)^{*})

$L((ab)^*)$

{ε, a b, a b a b, a b a b a b, a b a b a b a b, \dots}

$\{\varepsilon, ab, abab, ababab, abababab, \dots\}$

{ε, a b, a a b b, a a a b b b, a a a a b b b b, \dots}

$\{\varepsilon,ab,aabb,aaabbb,aaaabbbb,\dots\}$

4

a

$a$

b

$b$

2

Anda sepenuhnya benar. Saya melewatkan titik "menempatkan ekspresi reguler ke satu sama lain", saya hanya berpikir tentang "permutasi kata tetap" tidak "permutasi regex lain" yang tentu saja tidak mungkin.

Asqiir

1

Mungkin ekspresi reguler dengan permutasi menggambarkan kelas bahasa dengan properti yang menarik, tetapi saya tidak pernah mengalami kebutuhan untuk !operator dalam praktik, dan saya kira beberapa orang memiliki, karena mudah diimplementasikan, dan tidak ada implementasi dari ekspresi reguler yang diperluas. telah terlihat mendukungnya.

reinierpost

16

Jadi pertanyaan saya adalah:

(Kenapa) Apakah buktiku salah?

Jika benar: Mengapa tidak ada cara mudah untuk mengekspresikan permutasi?

"Bukti" Anda hanya melihat permutasi kata tunggal, yang merupakan bahasa terbatas.

Setiap bahasa berhingga adalah reguler (mis. Hanya dengan mendaftar semua anggota dengan |inbetween), tetapi ada bahasa reguler yang tak terbatas (dan itu pada umumnya yang lebih menarik).

Segera setelah Anda mendapatkan ekspresi reguler (atau tata bahasa / otomat) yang menerima bahasa tak terbatas (yaitu ekspresi dengan *operator, atau automaton dengan loop), konstruksi Anda tidak berfungsi lagi (Anda mendapatkan tata bahasa / otomat tak terbatas) ).

Jawaban oleh David Richerby memberikan contoh bahasa biasa yang bahasa permutasinya tidak teratur lagi - semua contoh tersebut adalah bahasa tanpa batas.

Paŭlo Ebermann
sumber

8

$\Sigma$ $n$ $\Sigma$ $m$ $O(m)$

Jadi dalam beberapa hal, tidak ada cara ringkas untuk menentukan semua permutasi kata.

$\tilde\Omega(2^n)$ $\Sigma$ $n$ $m$ $O(m)$

$L$ $(x_i,y_i)_{1 \leq i \leq N}$

$x_iy_i \in L$
$i \neq j$ $x_i y_j \notin L$ $x_j y_i \notin L$

$L$ $N$ $L$ $i$ $x_iy_i$ $q_i$ $x_i$ $q_i \neq q_j$ $i \neq j$ $q_i = q_j$ $x_iy_j$ $x_jy_i$ $L$

$L_n$ $\sigma_1,\ldots,\sigma_n$ $n$ $S$ $\sigma_1,\ldots,\sigma_n$ $n/2$ $x_S$ $S$ $y_S$ $S$ $x_Sy_S \in L_n$ $S \neq T$ $x_S y_T \notin L_n$ $L_n$ $\binom{n}{n/2} = \Omega(2^n/\sqrt{n})$

Yuval Filmus
sumber

Apakah ini berarti 1) dalam teori akan memungkinkan untuk membiarkan »abc« cocok dengan semua {abc, acb, bac, bca, cab, cba} tetapi itu tidak efisien dan akan membuat mereka terlalu lambat karena »abc« akan meluas secara eksponensial ke (abc | acb | bac | bca | cab | cba)? atau 2) Jenis otomat yang saya butuhkan tidak dapat menentukan semua permutasi untuk kata yang diberikan?

Asqiir

1

Berikut adalah ekspresi reguler yang cocok dengan semua permutasi dari

a b c

$abc$

a b c + a c d + b a c + b c a + c a b + c b a

$abc+acd+bac+bca+cab+cba$

1 + 3 + 6 + 6 + 1 = 17

$1+3+6+6+1 = 17$

a b c d e f g h i j

$abcdefghij$ .

Yuval Filmus

1

Apa yang saya pahami: Secara teori, bahasa reguler dapat menerima permutasi (demikian juga ekspresi reguler). Tidak ada "cara sederhana" untuk menulis "permutasi abc" seperti »abc«. (Untuk alasan apa pun.)

Asqiir

1

Ya, itu ringkasan yang bagus. Saya akan melihat apakah saya dapat mengajukan argumen sederhana untuk ekspresi reguler.

Yuval Filmus

2

Untuk pembaca masa depan: ini bukan jawaban yang benar! (Koreksi saya jika saya salah.) Cari yang diterima.

Asqiir

0

Mengapa tidak ada cara untuk menulis "permutasi" di Regex

Permutasi bahasa reguler dan tak terbatas (jumlah kata tak terbatas) belum tentu teratur. Dengan demikian, tidak dapat ditulis sebagai regex.

Bukti

Pikirkan bahasanya (ab)*. (Contoh terinspirasi oleh David Richerby .) Salah satu permutasi adalah a*b*. Ini bukan bahasa biasa. qed.

Asqiir
sumber

Mengapa tidak ada permutasi di Regex? (Bahkan jika bahasa reguler tampaknya dapat melakukan ini)

Masalah

Untuk verifikasi:

Jenis solusi yang saya cari

Keuntungan dari solusi ini

Kenapa ini harus ada

Jadi pertanyaan saya adalah:

Bukti

Pindah dengan buktinya

Jawaban:

Mengapa tidak ada cara untuk menulis "permutasi" di Regex

Bukti