O problema

Não há uma maneira fácil de obter uma permutação com um regex.

Permutação: Obtendo uma palavra ("aabc") para outra ordem, sem alterar o número ou o tipo de letras. $w = x_{1} \dots x_{n}$ $w=x_1…x_n$
Regex: expressão regular.

Para verificação:

"Permutações de regex sem repetição" A resposta cria código JavaScript em vez de regex, assumindo que isso seria mais simples.
"Como encontrar todas as permutações de uma determinada palavra em um determinado texto" - A resposta também não usa expressões regulares.
"Regex para corresponder a todos os {1, 2, 3, 4} sem repetição" - A resposta usa regexes, mas não é adaptável nem simples.
Essa resposta ainda afirma: "Uma expressão regular não pode fazer o que você está pedindo. Não pode gerar permutações a partir de uma string" .

O tipo de solução que estou procurando

Deve ter a forma:

»Aabc« (ou qualquer outra coisa que você possa usar entre parênteses de abertura e fechamento)
(aabc)! (semelhante a (abc)? mas com outro símbolo no final)
[aabc]! (semelhante a [abc] + mas com outro símbolo no final)

Vantagens dessas soluções

Eles são:

fácil
adaptável
reutilizável

Por que isso deveria existir?

Regexes são uma maneira de descrever uma gramática de um idioma comum. Eles têm todo o poder de ser qualquer tipo de linguagem comum.
Digamos que linguagens regulares são poderosas o suficiente para permutações (prova abaixo) - por que não há uma maneira fácil de expressar isso?

Então, minha pergunta é:

(Por que) Minha prova está errada?
Se estiver certo: por que não há maneira fácil de expressar permutações?

A prova

Expressões regulares são uma maneira de observar a gramática de um idioma regular. Eles podem descrever qualquer gramática de idiomas comum.
Outra maneira de descrever qualquer gramática regular (com um número finito de letras no alfabeto) são os autômatos não determinísticos (com um número finito de estados).

Tendo um número finito de letras, posso criar este autômato: (Exemplo. Formal: veja abaixo)

Gramática que aceita permutações de "abbc":

(procure por números no topo, talvez alguém saiba como melhorar esta parte)

s -> ah¹

s -> bh²

s -> ch³

h¹ -> bh¹¹

h¹ -> ch¹²

h² -> ah¹¹ (sem erro de digitação!)

h² -> bh²²

h² -> ch²³

h³ -> ah¹²

h³ -> bh²³

h¹¹ -> bc

h¹¹ -> cb

h --² bb

h²² -> ac

h²² -> ca

h²³ -> ab

h²³ -> ba

Mais formal: (usando um autômato de estado finito, mas isso também pode ser feito com gramática)

Uma palavra q (com comprimento finito) para a qual qualquer permutação deve atingir um estado de aceitação.
X é o alfabeto finito.
O conjunto de estados S contém qualquer ordem de letras até o comprimento de q. (Portanto, o tamanho de S é finito.) Mais um estado de "qualquer palavra mais longa".
função de transição de estado d que pega uma letra e se move no estado que corresponde à parte da palavra agora lida.
F é um conjunto de estados que são permutações exatas de q.

Portanto, é possível criar um autômato de estado finito para aceitar permutações de uma determinada palavra.

Seguindo em frente com a prova

Então, eu provei que as línguas comuns têm o poder de verificar permutações, não tenho?

Então, por que não há uma abordagem para alcançar isso com os Regexes? É uma funcionalidade útil.

formal-languages regular-languages regular-expressions Asqiir
fonte

10

Você pode listar todas as permutações da sua palavra com uma expressão regular. A expressão resultante será bastante grande, mas definitivamente será uma expressão regular.

Yuval Filmus

7

Sugiro ignorar todas as respostas sobre Teoria da Computação no stackoverflow. Esta não é a especialidade do site.

Yuval Filmus

A resposta na sua página vinculada aqui - stackoverflow.com/a/3102205/6936386 - parece ser facilmente adaptável e não muito complicada: ^(a()|a()|b()|c()){4}\2\3\4\5$parece funcionar (consulte regex101.com/r/9URPpg/4/tests ).

boboquack

7

@boboquack Essa não é uma expressão regular no sentido em que o termo é usado em ciência da computação. (Esse tipo de coisa é exatamente por Yuval não sugere confiando respostas Stack Overflow sobre CS teórica.)

David Richerby

37

Os teoremas fundamentais da teoria da linguagem formal são que expressões regulares, gramáticas regulares, autômatos finitos determinísticos (DFAs) e autômatos finitos não determinísticos (NFAs) descrevem os mesmos tipos de linguagens: as linguagens regulares. O fato de podermos descrever essas linguagens de maneiras completamente diferentes sugere que há algo natural e importante nessas linguagens, da mesma forma que a equivalência das máquinas de Turing, o cálculo lambda e todo tipo de outras coisas sugere que as linguagens computáveis são naturais e importantes. Eles não são apenas um artefato de quaisquer decisões aleatórias que o descobridor original tomou.

Suponha que adicionar uma nova regra para a criação de expressões regulares: se $R$ é uma expressão regular, então $\pi(R)$ é uma expressão regular, e combina todas as permutações de cada corda acompanhado por $R$ . Assim, por exemplo, $L(\pi(abc)) = \{abc, acb, bac, bca, cab, cba\}$ . O problema é que isso quebra as equivalências fundamentais descritas acima. $L\big(\pi((ab)^*))\big)$ é o idioma de cadeias que contêm um número igual de $a$ s e $b$ s e esta não é uma linguagem regular. Compare isso com, por exemplo, adicionar um operador de negação ou reversão a expressões regulares, o que não altera a classe de idiomas aceitos.

Portanto, para responder à pergunta do título, expressões regulares não podem fazer permutações e não adicionamos essa capacidade porque expressões regulares não combinam com idiomas comuns. Dito isto, é possível que "expressões regulares com permutações" também sejam uma classe interessante de linguagens com muitas caracterizações diferentes.

David Richerby
fonte

Mas L ((ab) *) também não é uma linguagem comum - então L (perm ((ab) *)) não pode ser uma. ((ab) * não é uma linguagem comum, pois não há tipo de memória para lembrar quantas "a" s de abertura existem; portanto, com um número finito de estados, você não pode colocar o mesmo número de "b" s.)

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

Você está completamente certo. Perdi o objetivo de "colocar expressões regulares uma na outra", só pensei em "permutar uma palavra fixa" e não "permutar outra regex", o que obviamente não é possível.

Asqiir

11

Talvez expressões regulares com permutações descrevam uma classe de linguagens com propriedades interessantes, mas eu nunca precisei do !operador na prática e suponho que poucas pessoas tenham, como é fácil de implementar, e nenhuma implementação de expressões regulares estendidas. ' já vi suporta.

Reinierpost

16

Então, minha pergunta é:

(Por que) Minha prova está errada?

Se estiver certo: por que não há maneira fácil de expressar permutações?

Sua "prova" analisava apenas permutações de palavras únicas, que são idiomas finitos.

Cada idioma finito é regular (por exemplo, apenas listando todos os membros com um |entre), mas existem idiomas regulares infinitos (e esses geralmente são os mais interessantes).

Assim que você obtém uma expressão regular (ou gramática / autômato) que aceita uma linguagem infinita (ou seja, uma expressão com o *operador ou um autômato com um loop), sua construção não funciona mais (você obtém uma gramática / autômato infinito )

A resposta de David Richerby forneceu um exemplo de uma linguagem regular cuja linguagem de permutação não é mais regular - todos esses exemplos são linguagens infinitas.

Paŭlo Ebermann
fonte

8

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

Portanto, em certo sentido, não há maneira sucinta de especificar todas as permutações de uma palavra.

$\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
fonte

Isso significa 1) em teoria, seria possível deixar »abc« corresponder a todos {abc, acb, bac, bca, cab, cba}, mas isso não é eficiente e os torna muito lentos, pois o »abc« se expande exponencialmente para (abc | acb | bac | bca | cab | cba)? ou 2) O tipo de autômato de que preciso não é capaz de especificar todas as permutações para uma determinada palavra?

Asqiir

11

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

11

O que eu entendi: Em teoria, linguagens regulares são capazes de aceitar permutações (assim como expressões regulares). Simplesmente não existe uma "maneira simples" de escrever "permutação de abc" como »abc«. (Por qualquer motivo.)

Asqiir

11

Sim, esse é um bom resumo. Vou ver se consigo chegar a um argumento mais simples para expressões regulares.

Yuval Filmus

2

Para futuros leitores: esta não é a resposta correta! (Corrija-me se estiver errado.) Procure o aceito.

Asqiir

0

Por que não há como escrever "permutação de" nos Regexes

A permutação de uma linguagem regular e infinita (quantidade infinita de palavras) não é necessariamente regular. Assim, não pode ser escrito como regex.

Prova

Pense na linguagem (ab)*. (Exemplo inspirado em David Richerby .) Uma de suas permutações é a*b*. Este não é um idioma comum. qed.

Asqiir
fonte

Por que não há permutação nos Regexes? (Mesmo que os idiomas comuns pareçam fazer isso)

O problema

Para verificação:

O tipo de solução que estou procurando

Vantagens dessas soluções

Por que isso deveria existir?

Então, minha pergunta é:

A prova

Seguindo em frente com a prova

Respostas:

Por que não há como escrever "permutação de" nos Regexes

Prova