Le problème

Il n'y a pas de moyen facile d'obtenir une permutation avec une expression régulière.

Permutation: obtenir un mot ("aabc") dans un autre ordre, sans changer le nombre ou le type de lettres. $w = x_{1} \dots x_{n}$ $w=x_1…x_n$
Regex: expression régulière.

Pour vérification:

"Permutations d'expression régulière sans répétition" La réponse crée du code JavaScript au lieu d'une expression régulière, en supposant que ce serait plus simple.
"Comment trouver toutes les permutations d'un mot donné dans un texte donné" - La réponse n'utilise pas non plus de regex.
"Regex pour correspondre à tous les {1, 2, 3, 4} sans répétition" - La réponse utilise des regex, mais ce n'est ni adaptable ni simple.
Cette réponse affirme même: "Une expression régulière ne peut pas faire ce que vous demandez. Elle ne peut pas générer de permutations à partir d'une chaîne" .

Le type de solution que je recherche

Il devrait avoir la forme:

»Aabc« (ou toute autre chose que vous pourriez utiliser entre parenthèses ouvrantes et fermantes)
(aabc)! (similaire à (abc)? mais avec un autre symbole à la fin)
[aabc]! (similaire à [abc] + mais avec un autre symbole à la fin)

Avantages de ces solutions

Elles sont:

facile
adaptable
réutilisable

Pourquoi cela devrait exister

Les expressions régulières sont un moyen de décrire la grammaire d'une langue régulière. Ils ont le plein pouvoir d'être n'importe quel langage ordinaire.
Disons que les langages réguliers sont assez puissants pour les permutations (preuve ci-dessous) - pourquoi n'y a-t-il pas de moyen facile d'exprimer cela?

Ma question est donc:

(Pourquoi) Ma preuve est-elle fausse?
Si c'est le cas: pourquoi n'y a-t-il pas de moyen facile d'exprimer des permutations?

La preuve

Les expressions régulières sont un moyen de noter la grammaire d'une langue régulière. Ils peuvent décrire n'importe quelle grammaire de langues régulières.
Les automates non déterministes (avec un nombre fini d'états) sont une autre façon de décrire les langages réguliers (qui ont un nombre fini de lettres dans leur alphabet).

Ayant un nombre fini de lettres je peux créer cet automate: (Exemple. Formel: voir ci-dessous)

Grammaire qui accepte les permutations de "abbc":

(essayez les chiffres en haut, peut-être que quelqu'un sait comment rendre cette partie plus belle)

s -> ah¹

s -> bh²

s -> ch³

h¹ -> bh¹¹

h¹ -> ch¹²

h² -> ah¹¹ (pas d'équivalence typo!)

h² -> bh²²

h² -> ch²³

h³ -> ah¹²

h³ -> bh²³

h¹¹ -> bc

h¹¹ -> cb

h¹² -> bb

h²² -> ac

h²² -> ca

h²³ -> ab

h²³ -> ba

Plus formel: (en utilisant un automate à états finis mais cela pourrait aussi être fait avec la grammaire)

Un mot q (de longueur finie) auquel toute permutation devrait atteindre un état acceptant.
X est l'alphabet fini.
L'ensemble d'états S contient n'importe quel ordre de lettres jusqu'à la longueur de q. (La taille de S est donc finie.) Plus un état de "tout mot plus long".
fonction de transition d'état d qui prend une lettre et se déplace sur l'état qui correspond à la partie maintenant lue du mot.
F est un ensemble de ces états qui sont des permutations exactes de q.

Il est donc possible de créer un automate à états finis pour accepter les permutations d'un mot donné.

Passer à la preuve

J'ai donc prouvé que les langues régulières ont le pouvoir de vérifier les permutations, n'est-ce pas?

Alors, pourquoi n'y a-t-il pas d'approche pour y parvenir avec Regexes? C'est une fonctionnalité utile.

formal-languages regular-languages regular-expressions Asqiir
la source

10

Vous pouvez lister toutes les permutations de votre mot avec une expression régulière. L'expression résultante sera assez grande, mais sera certainement une expression régulière.

Yuval Filmus

7

Je suggère d'ignorer toutes les réponses sur la théorie du calcul sur stackoverflow. Ce n'est pas la spécialité de ce site.

Yuval Filmus

La réponse sur votre page liée ici - stackoverflow.com/a/3102205/6936386 - semble être facilement adaptable et pas trop compliquée: ^(a()|a()|b()|c()){4}\2\3\4\5$semble fonctionner (voir regex101.com/r/9URPpg/4/tests ).

boboquack

7

@boboquack Ce n'est pas une expression régulière dans le sens où le terme est utilisé en informatique. (Ce genre de chose est exactement la raison pour laquelle Yuval suggère de ne pas faire confiance aux réponses de Stack Overflow sur le CS théorique.)

David Richerby

37

Les théorèmes fondamentaux de la théorie du langage formel sont que les expressions régulières, les grammaires régulières, les automates finis déterministes (DFA) et les automates finis non déterministes (NFA) décrivent tous les mêmes types de langues: à savoir les langues régulières. Le fait que nous puissions décrire ces langages de tant de manières complètement différentes suggère qu'il y a quelque chose de naturel et important dans ces langages, de la même manière que l'équivalence des machines de Turing, le calcul lambda et toutes sortes d'autres choses suggèrent que les langages calculables sont naturels et importants. Ils ne sont pas seulement un artefact de toutes les décisions aléatoires prises par le découvreur d'origine.

Supposons que nous ajoutons une nouvelle règle pour la création d' expressions régulières: si $R$ est une expression régulière, $\pi(R)$ est une expression régulière, et il correspond à toutes les permutations de chaque chaîne par correspondance $R$ . Ainsi, par exemple, $L(\pi(abc)) = \{abc, acb, bac, bca, cab, cba\}$ . Le problème est que cela rompt les équivalences fondamentales décrites ci-dessus. $L\big(\pi((ab)^*))\big)$ est le langage des chaînes qui contiennent un nombre égal de $a$ s et $b$ s et ce n'est pas un langage normal. Comparez cela avec, par exemple, l'ajout d'un opérateur de négation ou d'inversion aux expressions régulières, ce qui ne change pas la classe des langues acceptées.

Donc, pour répondre à la question du titre, les expressions régulières ne peuvent pas faire de permutations et nous n'ajoutons pas cette capacité car les expressions régulières ne correspondraient pas aux langues régulières. Cela dit, il est possible que les "expressions régulières avec permutations" soient également une classe de langues intéressante avec beaucoup de caractérisations différentes.

David Richerby
la source

Mais L ((ab) *) n'est pas non plus un langage régulier - donc L (perm ((ab) *)) ne peut pas en être un. ((ab) * n'est pas un langage régulier car il n'y a aucune sorte de mémoire pour se souvenir du nombre d'ouvertures "a", donc avec un nombre fini d'états vous ne pouvez pas mettre le même nombre de "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

Vous avez parfaitement raison. J'ai raté le point de «mettre des expressions régulières les unes dans les autres», je n'ai pensé qu'à «permuter un mot fixe» et non «permuter une autre expression régulière», ce qui bien sûr n'est pas possible.

Asqiir

1

Peut-être que les expressions régulières avec permutations décrivent une classe de langages avec des propriétés intéressantes, mais je n'ai jamais eu besoin de l' !opérateur en pratique, et je suppose que peu de gens l'ont, car c'est facile à implémenter, et aucune implémentation d'expressions régulières étendues I ' ve vu le soutient.

reinierpost

16

Ma question est donc:

(Pourquoi) Ma preuve est-elle fausse?

Si c'est le cas: pourquoi n'y a-t-il pas de moyen facile d'exprimer des permutations?

Votre "preuve" n'a regardé que les permutations de mots simples, qui sont des langues finies.

Chaque langue finie est régulière (par exemple juste en listant tous les membres avec un |entre-deux), mais il existe une infinité de langues régulières (et ce sont généralement les plus intéressantes).

Dès que vous obtenez une expression régulière (ou grammaire / automate) qui accepte un langage infini (ie une expression avec l' *opérateur, ou un automate avec une boucle), votre construction ne fonctionne plus (vous obtenez une grammaire / automate infinie ).

La réponse de David Richerby a fourni un exemple de langage régulier dont le langage de permutation n'est plus régulier - tous ces exemples sont des langages infinis.

Paŭlo Ebermann
la source

8

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

Donc, dans un certain sens, il n'existe aucun moyen succinct de spécifier toutes les permutations d'un mot.

$\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
la source

Est-ce à dire 1) en théorie, il serait possible de laisser »abc« correspondre à tous {abc, acb, bac, bca, cab, cba} mais ce n'est tout simplement pas efficace et les rendrait trop lents car »abc« se développerait exponentiellement jusqu'à (abc | acb | bac | bca | cab | cba)? ou 2) Le type d'automate dont j'ai besoin n'est pas en mesure de spécifier toutes les permutations pour un mot donné?

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

Ce que j'ai compris: en théorie, les langages réguliers sont capables d'accepter les permutations (tout comme les expressions régulières). Il n'y a tout simplement pas de "méthode simple" pour écrire "permutation d'abc" comme »abc«. (Pour quelque raison que ce soit.)

Asqiir

1

Oui, c'est un bon résumé. Je vais voir si je peux trouver un argument plus simple pour les expressions régulières.

Yuval Filmus

2

Pour les futurs lecteurs: ce n'est pas la bonne réponse! (Corrigez-moi si je me trompe.) Recherchez l'accepté.

Asqiir

0

Pourquoi il n'y a aucun moyen d'écrire "permutation de" dans Regexes

Une permutation d'une langue régulière et infinie (quantité infinie de mots) n'est pas nécessairement régulière. Ainsi, il ne peut pas être écrit en regex.

Preuve

Pensez à la langue (ab)*. (Exemple inspiré par David Richerby .) L'une de ses permutations est a*b*. Ce n'est pas une langue régulière. qed.

Asqiir
la source

Pourquoi n'y a-t-il pas de permutation dans les regexes? (Même si les langues régulières semblent pouvoir le faire)

Le problème

Pour vérification:

Le type de solution que je recherche

Avantages de ces solutions

Pourquoi cela devrait exister

Ma question est donc:

La preuve

Passer à la preuve

Réponses:

Pourquoi il n'y a aucun moyen d'écrire "permutation de" dans Regexes

Preuve