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

13

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=x1xn
  • Regex: expressão regular.

Para verificação:

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.

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

Respostas:

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 π(R) é uma expressão regular, e combina todas as permutações de cada corda acompanhado por  R . Assim, por exemplo, L(π(abc))={abc,acb,bac,bca,cab,cba}. O problema é que isso quebra as equivalências fundamentais descritas acima. L(π((ab)))) é 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((ab)){ε,ab,abab,ababab,abababab,}{ε,ab,aabb,aaabbb,aaaabbbb,}
4
ab
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

ΣnΣmO(m)

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


Ω~(2n)ΣnmO(m)

L(xi,yi)1iN

  • xiyiL
  • ijxiyjLxjyiL

LNLixiyiqixiqiqjijqi=qjxiyjxjyiL

Lnσ1,,σnnSσ1,,σnn/2xSSySSxSySLnSTxSyTLnLn(nn/2)=Ω(2n/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
abcabc+acd+bac+bca+cab+cba1+3+6+6+1=17abcdefghij.
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