Problem

Nie ma łatwego sposobu na uzyskanie permutacji za pomocą wyrażenia regularnego.

Permutacja: Uzyskanie słowa („aabc”) w innym porządku, bez zmiany liczby lub rodzaju liter. $w = x_{1} \dots x_{n}$ $w=x_1…x_n$
Regex: wyrażenie regularne.

Dla weryfikacji:

„Permutacje regexów bez powtórzeń” Odpowiedź tworzy kod JavaScript zamiast wyrażenia regularnego, zakładając, że byłoby to prostsze.
„Jak znaleźć wszystkie permutacje danego słowa w danym tekście” - Odpowiedź również nie używa wyrażeń regularnych.
„Ponownie dopasuj, aby dopasować wszystkie {1, 2, 3, 4} bez powtórzeń” - w odpowiedzi użyto wyrażeń regularnych, ale nie jest to ani adaptowalne, ani proste.
Ta odpowiedź twierdzi nawet: „Wyrażenie regularne nie może robić tego, o co prosisz. Nie może generować permutacji z łańcucha” .

Rodzaj rozwiązania, którego szukam

Powinien mieć postać:

»Aabc« (lub cokolwiek innego, czego można użyć nawiasów otwierających i zamykających)
(aabc)! (podobny do (abc)? ale z innym symbolem na końcu)
[aabc]! (podobny do [abc] +, ale z innym symbolem na końcu)

Zalety tych rozwiązań

Oni są:

łatwy
dający się przystosować
wielokrotnego użytku

Dlaczego to powinno istnieć

Regeksy są sposobem na opisanie gramatyki zwykłego języka. Mają pełną moc, aby być dowolnym językiem.
Powiedzmy, że zwykłe języki są wystarczająco mocne, aby uzyskać permutacje (dowód poniżej) - dlaczego nie ma łatwego sposobu na wyrażenie tego?

Więc moje pytanie brzmi:

(Dlaczego) Czy mój dowód jest błędny?
Jeśli to prawda: dlaczego nie ma łatwego sposobu wyrażenia permutacji?

Dowód

Wyrażenia regularne są jednym ze sposobów odnotowania gramatyki języka regularnego. Potrafią opisać dowolną gramatykę języków regularnych.
Innym sposobem na opisanie języków regularnych (które mają skończoną liczbę liter w swoim alfabecie) gramatyka są niedeterministyczne Automaty (o skończonej liczbie stanów).

Mając skończoną liczbę liter, mogę utworzyć ten automat: (Przykład. Formalny: patrz poniżej)

Gramatyka, która akceptuje permutacje „abbc”:

(wypowiedz cyfry na górze, może ktoś wie, jak sprawić, by ta część wyglądała lepiej)

s -> ah¹

s -> bh²

s -> ch³

h¹ -> bh¹¹

h¹ -> ch¹²

h² -> ah¹¹ (brak równoważności literówek!)

h² -> bh²²

h² -> ch²³

h³ -> ah¹²

h³ -> bh²³

h¹¹ -> bc

h¹¹ -> cb

h¹² -> bb

h²² -> ac

h²² -> ca

h²³ -> ab

h²³ -> ba

Bardziej formalne: (przy użyciu automatu stanu skończonego, ale można to również zrobić za pomocą gramatyki)

Słowo q (o skończonej długości), do którego każda permutacja powinna osiągnąć stan akceptacji.
X jest skończonym alfabetem.
Zbiór stanów S zawiera dowolną kolejność liter do długości q. (Więc rozmiar S jest skończony.) Plus jeden stan „dowolnego dłuższego słowa”.
funkcja przejścia stanu d, która przyjmuje literę i przesuwa się do stanu, który odpowiada teraz czytanej części słowa.
F jest zbiorem tych stanów, które są dokładnymi permutacjami q.

Możliwe jest więc utworzenie automatu skończonego do akceptowania permutacji danego słowa.

Idąc dalej z dowodem

Udowodniłem, że zwykłe języki mają uprawnienia do sprawdzania permutacji, prawda?

Dlaczego więc nie ma podejścia do osiągnięcia tego za pomocą Regexes? To przydatna funkcjonalność.

formal-languages regular-languages regular-expressions Asqiir
źródło

10

Możesz wymienić wszystkie kombinacje swojego słowa za pomocą wyrażenia regularnego. Wynikowe wyrażenie będzie dość duże, ale na pewno będzie wyrażeniem regularnym.

Yuval Filmus

7

Sugeruję zignorowanie wszystkich odpowiedzi dotyczących teorii obliczeń przy przepełnieniu stosu. To nie jest specjalność tej witryny.

Yuval Filmus

Odpowiedź na podanej tutaj stronie - stackoverflow.com/a/3102205/6936386 - wydaje się łatwa do dostosowania i niezbyt skomplikowana: ^(a()|a()|b()|c()){4}\2\3\4\5$wydaje się działać (patrz regex101.com/r/9URPpg/4/tests ).

Boboback

7

@ Boboquack To nie jest wyrażenie regularne w tym sensie, w jakim termin jest używany w informatyce. (Właśnie dlatego Yuval sugeruje, aby nie ufać odpowiedziom przepełnienia stosu na temat teoretycznego CS.)

David Richerby,

37

Podstawowe twierdzenia formalnej teorii języka są takie, że wyrażenia regularne, gramatyka regularna, deterministyczne automaty skończone (DFA) i niedeterministyczne automaty skończone (NFA) opisują te same rodzaje języków: mianowicie języki regularne. Fakt, że możemy opisać te języki na tak wiele różnych sposobów, sugeruje, że istnieje coś naturalnego i ważnego w tych językach, w taki sam sposób, w jaki równoważność maszyn Turinga, rachunku lambda i wszelkiego rodzaju innych rzeczy sugeruje, że języki obliczalne są naturalne i ważne. Nie są jedynie artefaktem przypadkowych decyzji podjętych przez pierwotnego odkrywcę.

Załóżmy, że dodać nową regułę tworzenia wyrażeń regularnych: jeśli $R$ jest wyrażenie regularne, wtedy $\pi(R)$ jest wyrażeniem regularnym, a to pasuje do każdego permutacji każdego łańcucha dopasowane $R$ . Na przykład $L(\pi(abc)) = \{abc, acb, bac, bca, cab, cba\}$ . Problem polega na tym, że łamie to podstawowe równoważniki opisane powyżej. $L\big(\pi((ab)^*))\big)$ jest językiem ciągów, które zawierają taką samą liczbę $a$ s i $b$ s, a to nie jest język regularny. Porównaj to, na przykład, dodając operator negacji lub odwrócenia do wyrażeń regularnych, co nie zmienia klasy akceptowanych języków.

Tak więc, aby odpowiedzieć na pytanie tytułowe, wyrażenia regularne nie mogą dokonywać permutacji i nie dodajemy tej możliwości, ponieważ wtedy wyrażenia regularne nie pasują do języków regularnych. Powiedziawszy to, możliwe jest, że „wyrażenia regularne z permutacjami” byłyby również interesującą klasą języków o wielu różnych charakterystykach.

David Richerby
źródło

Ale L ((ab) *) też nie jest zwykłym językiem - więc L (perm ((ab) *)) nie może być jednym. ((ab) * nie jest zwykłym językiem, ponieważ nie ma pamięci, aby zapamiętać, ile jest początkowych „a”, więc przy skończonej liczbie stanów nie można umieścić tej samej liczby „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

Masz całkowitą rację. Brakowało mi punktu „wstawiania do siebie wyrażeń regularnych”, myślałem tylko o „permutacji ustalonego słowa”, a nie „permutacji innego wyrażenia regularnego”, co oczywiście nie jest możliwe.

Asqiir,

1

Być może wyrażenia regularne z permutacjami opisują klasę języków o interesujących właściwościach, ale nigdy nie spotkałem się z potrzebą !operatora w praktyce i przypuszczam, że niewiele osób ma, ponieważ jest łatwe do wdrożenia i nie ma rozszerzenia rozszerzonych wyrażeń regularnych. widzieliśmy, że to popiera.

reinierpost

16

Więc moje pytanie brzmi:

(Dlaczego) Czy mój dowód jest błędny?

Jeśli to prawda: dlaczego nie ma łatwego sposobu wyrażenia permutacji?

Twój „dowód” dotyczył tylko permutacji pojedynczych słów, które są skończonymi językami.

Każdy skończony język jest regularny (np. Po prostu wymieniając wszystkich członków |pomiędzy), ale istnieją nieskończone regularne języki (i te są na ogół bardziej interesujące).

Gdy tylko otrzymasz wyrażenie regularne (lub gramatykę / automat), które akceptuje nieskończony język (tj. Wyrażenie z *operatorem lub automat z pętlą), twoja konstrukcja już nie działa (otrzymujesz nieskończoną gramatykę / automat) ).

Odpowiedź Davida Richerby podała przykład zwykłego języka, którego język permutacji nie jest już regularny - wszystkie takie przykłady są nieskończonymi językami.

Paŭlo Ebermann
źródło

8

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

W pewnym sensie nie ma zwięzłego sposobu na określenie wszystkich permutacji słowa.

$\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
źródło

Czy to oznacza 1) teoretycznie byłoby możliwe, aby »abc« pasowało do wszystkich {abc, acb, bac, bca, cab, cba}, ale to po prostu nie jest wydajne i spowolniłoby je, ponieważ »abc« rozwijałby się wykładniczo do (abc | acb | bac | bca | cab | cba)? lub 2) Rodzaj automatu, którego potrzebuję, nie jest w stanie określić wszystkich permutacji dla danego słowa?

Asqiir,

1

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

Co zrozumiałem: Teoretycznie języki regularne są w stanie zaakceptować permutacje (podobnie jak wyrażenia regularne). Po prostu nie ma „prostego sposobu” na napisanie „permutacji abc” jak »abc«. (Z jakichkolwiek powodów.)

Asqiir,

1

Tak, to dobre podsumowanie. Zobaczę, czy mogę wymyślić prostszy argument dla wyrażeń regularnych.

Yuval Filmus

2

Dla przyszłych czytelników: to nie jest poprawna odpowiedź! (Popraw mnie, jeśli się mylę.) Poszukaj zaakceptowanego.

Asqiir,

0

Dlaczego nie ma sposobu na napisanie „permutacji” w Regexes

Permutacja zwykłego, nieskończonego języka (nieskończona ilość słów) niekoniecznie jest regularna. Dlatego nie można go zapisać jako wyrażenia regularnego.

Dowód

Pomyśl o języku (ab)*. (Przykład zainspirowany przez Davida Richerby'ego .) Jedną z jego permutacji jest a*b*. To nie jest zwykły język. co było do okazania.

Asqiir
źródło

Dlaczego w Regexach nie ma permutacji? (Nawet jeśli wydaje się, że zwykłe języki to potrafią)

Problem

Dla weryfikacji:

Rodzaj rozwiązania, którego szukam

Zalety tych rozwiązań

Dlaczego to powinno istnieć

Więc moje pytanie brzmi:

Dowód

Idąc dalej z dowodem

Odpowiedzi:

Dlaczego nie ma sposobu na napisanie „permutacji” w Regexes

Dowód