Recentemente vi uma publicação de como ensinaram ao Perl a reconhecer um número primo usando expressões regulares. A expressão regular em questão é:
/^1?$|^(11+?)\1+$/
O único requisito a essa expressão regular é que o número seja fornecido em formato unário (a publicação mostra como fazer a transformação de um número em decimal para unário em Perl).
Sabe o que é esse "formato unário"? Bem, diferente do nosso costumeiro decimal (ou do hexadecimal ou do binário), o unário não é posicional.
Na verdade, se você já usou os dedos para fazer uma conta ou informar uma quantidade, você já usou unário. Nesse formato, a quantidade de símbolos de uma expressão (ou dedos levantados da mão) corresponde ao número em questão. Por exemplo,
X
em unário é equivalente ao decimal1
, eXXXXX
é equivalente ao decimal5
.Qualquer símbolo pode ser usado na representação unária, e o mais comum é usarem o caracter
1
. Então, se eu quiser representar o6
decimal em unário, devo repetir o símbolo um total de seis vezes; usando o símbolo1
, a representação do seis seria111111
Como essa expressão funciona? Bem, na verdade ela detecta os números que não são primos. Ela é dividida em duas partes:
^1?$
^(11+?)\1+$
A primeira parte é responsável por pegar números trivialmente não primos: o 0 e o 1. A segunda parte é mais interessante, entretanto.
Na segunda parte, temos um termo que está contido em um agrupamento (o 11+?
). Vamos deixar ele no cantinho por enquanto, tá? Depois, consiste de um retrovisor (o \1
), que faz o exato match do agrupamento anterior. Só que, não satisfeito com isso, esse mesmo match vem seguido da cruz de Kleene, que indica que a expressão deve aparecer pelo menos 1 vez e pode se repetir até infinitas vezes.
Logo, se a string agrupada tiver comprimento 3, a expressão regular dará match em strings de comprimento 6, 9, 12 e por aí vai. Isso porque a cruz de Kleene vai garantir que a string ao todo terá o seguinte comprimento (para l
sendo o tamanho da string do agrupamento):
l + k*l, k >= 1
Então, para que o número não seja primo, precisa-se garantir que l != 1
. Voltando ao agrupamento, isso é definido em 11+?
. Aqui o casamento ocorre com qualquer string de tamanho 2 ou mais (a interrogação depois da cruz de Kleene é só para ser menos guloso possível e rodar mais rapidamente, não é estritamente necessário). Logo, com isso, temos que l >= 2
. Então, se essa segunda parte da expressão regular der um match na string, temos que o número passado é um número composto.
Assim, através de uma expressão que transcende as linguagens regulares, foi montada essa expressão que reconhece a primalidade (ou, melhor, a não primalidade) de um número. Vale lembrar que retrovisores e outras formas de memória explícita não consistem em expressões matematicamente regulares. Veja mais sobre o assunto.
Sendo assim, é possível desenhar algum Autômato Finito Determinístico que consiga reconhecer se um número é primo? Se sim, como ele é? Se não, qual a prova de que esse problema não pode ser resolvido através de uma linguagem regular?