Uma expressão regular de Perl / Java / etc pode ser escrita para coincidir com números decimais (não) primos?

9

Perguntas / materiais relacionados:

Como é sabido, as "expressões regulares" suportadas por várias linguagens de programação geram linguagens que não são regulares no sentido formal e, como demonstrado no material acima, capazes de reconhecer pelo menos algumas idiomas sensíveis ao contexto.

A linguagem L = {x | x é um número primo na base 10} é uma linguagem sensível ao contexto, uma vez que a primalidade pode ser testada por um autômato limitado linear (mas não é uma linguagem livre de contexto por um argumento do lema do bombeamento).

Então, é possível escrever uma expressão regular Perl ou Java que aceite precisamente todos os números primos na base 10? Sinta-se à vontade para substituir qualquer outra base ≥ 2 ou para reconhecer precisamente todos os números compostos se isso parecer mais fácil.

Usar fugas para, por exemplo, executar código arbitrário Perl é considerado trapaça. Fazer substituições repetidas (o que é facilmente Turing completo) também está fora do escopo; todo o trabalho deve ser feito dentro da expressão regular. Esta questão é mais sobre os limites de quão poderosas são as expressões regulares.

    
por Sami Liedes 23.09.2016 в 22:34
fonte

1 resposta

2

NOTA: Estes Regexes foram escritos para PHP e usam quantificadores possessivos que são usados ​​em muitas, mas não em todas as linguagens, por exemplo, java-script não os suporta. Também isso é muito ineficiente e rapidamente se tornará inviável.

EDIT: aqui é para base 10 \b(((\d)(?=[\d\s]*({0,10}(n(?=.*n)|nn(?=.*1)|n{3}(?=.*2)|n{4}(?=.*3)|n{5}(?=.*4)|n{6}(?=.*5)|n{7}(?=.*6)|n{8}(?=.*7)|n{9}(?=.*8))?)))+)(?![\d\s]*(n(?=))++(..?1|(...*)+1)) Eu usei base 2 depois disso para facilitar as coisas.

EDIT: este permitirá que você passe uma string contendo vários números binários e corresponda àqueles que são primos \b(((\d)(?=[\d\s]*({0,2}n(?=.*)|{0,2})))+)(?![\d\s]*(n(?=))++(..?1|(...*)+1)) Ele basicamente faz isso usando o limite \ b ao invés do início da string ^, ele permite qualquer número de decimais e espaços ao avançar para o ns e envolve toda a parte que testa as representações da base 1 em uma previsão negativa. Além disso, funciona da mesma maneira que o abaixo. Como exemplo 1111 1011 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn1 corresponderá a 1011 .

Eu consegui algo que acho que funciona (marcado para 25) e combina com os não-primos. Aqui está para a base 2 (mais fácil de explicar) ^((\d)(?= \d*\s({0,2}n(?=.*)|{0,2})))+\s(n(?=))*+\K(..?1|(..+?)+1) , isso pode ser expandido até a base n, mas isso expande o regex muito rapidamente. Para que este regex funcione eu preciso de alguns perquisites (A bit hacky), a string de entrada deve ser o número seguido por um espaço seguido por pelo menos tantos n caracteres quanto o valor do seu número (se você tivesse o número 10 você precisa no leat 10 ns depois dele) seguido pelos dígitos da sua base, a fim de excluir o seu dígito de 0 (por exemplo, para a base 10 123456789), não incluindo o seu 0. Por exemplo 11 nnnnnnnnnnnnnn1 . Isso se deve ao fato de que as regexes não têm armazenamento acessível, portanto, preciso usar grupos de captura para fazer isso. Finalmente, este regex usa / x para ignorar os espaços em branco na expressão, tira todo o espaço se você não quiser usar isso.

Agora explicarei como isso funciona em três etapas. Este regex funciona em 3 partes:

Parte 1 : esta parte altera uma base n & gt; 1 para basear 1 como um grupo de captura de ns

Esta é a parte ^((\d)(?= \d*\s({0,2}n(?=.*)|{0,2})))+ que funciona de forma muito semelhante ao exemplo a^nb^n na questão. O ^ na frente significa que a partida completa tem que começar no começo, isso é importante para mais tarde. A estrutura principal deste código é ^((\d)(?= \d*\s (suff)))+ . Isso leva cada decimal entre o início e o primeiro espaço e executa um look-ahead positivo usando (\ d) (? =) Onde \ d é um decimal e (? =) É um Olhar em frente o \ d está em um grupo de captura () para mais tarde. É o dígito que estamos vendo atualmente.

O lado de dentro do look-ahead não é realmente verificar uma condição à frente, mas sim construir um grupo de captura representando nosso número na base 1. O interior do grupo de captura se parece com isso

\d*\s({0,2}n(?=.*)|{0,2})) 

A parte \ d * \ s basicamente move os caracteres que estamos vendo depois do restante dos dígitos restantes \ d * (\ d é dígito e * é 0 a n quantas vezes for possível) isso agora nos deixa procurando no início do ns.

({0,2}n(?=.*)|{0,2}))

é um grupo de captura de auto-referência aqui é onde entra a necessidade dos dígitos que você colocou no final. Este grupo combina-se de 0 a 2 vezes, mas o maior número de vezes possível (usando \ 3 {0,2} com \ 3 significando caturing grupo 3 e {0,2} significando correspondência de 0 a 2 vezes) isto significa que se houver um número antes do dígito atual sua base 1 representação é multiplicada por 2. Isso seria 10 para base 10 ou 16 para a base 16. Se este for o primeiro dígito, o grupo será indefinido, portanto, corresponderá a 0 vezes. Em seguida, ele adiciona um único n ou n baseado na correspondência do dígito no qual estamos trabalhando atualmente (usando seu grupo de captura). Ele faz isso usando uma perspectiva positiva para olhar para o final da entrada em que colocamos os dígitos n (? =. * \ 2). Isso corresponde a n se puder encontrar algo seguido pelo dígito em que estamos trabalhando. Isso permite identificar em qual dígito estamos trabalhando neste momento. (Eu teria usado um olhar para trás, mas eles são de comprimento fixo) Se você tivesse base 3 e quisesse verificar se o dígito em que você está trabalhando atualmente é 2, você usaria nn (? =. * 1 \ 2). Isso corresponderia a nn apenas se o dígito fosse dois. Nós usamos um operador ou '|' para todos estes e se nenhum dígito for encontrado, assumimos que é 0 e não adicionar nenhum ns. Como isso está no grupo de captura, essa correspondência é salva no grupo.

Em resumo desta parte, o que fazemos é levar cada dígito para frente, pegar a representação de base 1 dos dígitos anteriores (salvos no grupo de captura) e multiplicá-la pela base, depois combiná-la e adicionar a base representação do dígito e salve-o no grupo. Se você fizer isso para cada dígito, você terá uma base de uma representação do número. Vamos olhar e exemplo. 101 nnnnnnnnnnnnnnnnn1

Primeiro, vai para o sábado por causa de ^. então: 101 nnnnnnnnnnnnnnnnn1

Em seguida, ele vai para o primeiro dígito e o salva em um grope de captura 1 01 nnnnnnnnnnnnnnnnn1

Grupo 2: 1

Ele usa um look-ahead usando \ d * \ s para passar todos os dígitos e o primeiro espaço. 1 01 n nnnnnnnnnnnnnnnn1

Agora está dentro do grupo de captura 3

Recebe o valor anterior deste grupo de captação e corresponde a 0 a 2 vezes

Como está indefinido, corresponde a 0 hora.

Agora, ele olha para frente novamente para tentar encontrar um dígito correspondente ao dígito na captura do grupo 2 1 01 n nnnnnnnnnnnnnnnn 1

como foi encontrado, ele corresponde a 1 n no grupo de captura 3 2 1 01 nn nnnnnnnnnnnnnnn1

Agora sai do grupo 3, atualizando seu valor e deixando o olhar para frente Grupo 3 = n

Agora, ele olha para o próximo dígito e salva isso em um grupo de captura 1 0 1 nnnnnnnnnnnnnnnnn1

grupo 2 = 0

grupo 3 = n

Em seguida, ele também usa um look-ahead e vai para o primeiro n 1 0 1 n nnnnnnnnnnnnnnnn1

Em seguida, ele corresponde ao grupo 3 0 a 2 vezes, mas o máximo possível, de modo que n 1 0 1 nn nnnnnnnnnnnnnnn1

Em seguida, ele usa um look-ahead para tentar igualar o dígito no grupo 2, o que ele pode fazer para adicionar ns, antes de retornar do grupo 3 e a antecipação

group3 = nn

Agora, o próximo dígito é exibido e salvo no grupo 2 10 1 nnnnnnnnnnnnnnnnn1 Usando uma olhada antecipada vai para o começo do ns e combina 2 vezes grupo 3 10 1 nnnn nnnnnnnnnnnnn1 Em seguida, ele usa um look-ahead para tentar igualar o dígito no grupo 2 que ele acha que corresponde a um n e retorna para fora do grupo 3 e o look-ahead. group3 = nnnnn O grupo 3 agora contém a representação da base 1 do nosso número.

Parte 2 Reduz o ns para o tamanho da representação de base 1 do seu número

\s(n(?=))*+\K

Isso corresponde ao espaço e, em seguida, corresponde a ns enquanto você pode combinar o grupo 3 (a representação básica do seu número) na frente. Ele faz isso combinando n tantas vezes quanto possível usando um * + que é possessivo (nunca deixa de corresponder isso é parar a correspondência de ser reduzido mais tarde para fazer um trabalho de correspondência) n tem uma antecipação posiva n (? = \ 3), o que significa que n será correspondido desde que haja um grupo 3 à frente (\ 3 dá o grupo de captura 3). Isso nos deixa com nossa representação de base 1 e dígitos sendo a única coisa que resta inigualável. Nós então nós \ K para dizer começar a correspondência novamente a partir daqui.

Parte3 Agora usamos o mesmo algoritmo mencionado na pergunta para separar os primos de forçá-lo a não corresponder entre o início da base na representação e o início dos dígitos. Você pode ler como isso funciona aqui Como determinar se um número é primo com regex?

Finalmente para fazer isso em uma base n regex você tem que fazer algumas coisas

 ^((\d)(?= \d*\s({0,2}n(?=.*)|{0,2})))+\s(n(?=))*+\K(..?1|(..+?)+1)

punho adicionar mais alguns dígitos no final da sua seqüência de entrada, em seguida, altere o n

?=.* to  n?=.*n |  n?=.*1   n?=.*3 ..,  n?=.***n**

Por fim, altere o \ 3 {0,2} para \ 3 {0, n }. onde n é a base. Lembre-se também que isso não funcionará sem a string de entrada correta.

    
por milo.farrell 07.11.2016 / 15:25
fonte