15

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 decimal 1, e XXXXX é equivalente ao decimal 5.

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 o 6 decimal em unário, devo repetir o símbolo um total de seis vezes; usando o símbolo 1, a representação do seis seria 111111

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?

2
  • 1
    DFA é O(n), isto equivaleria a um algoritmo de fatoração O(n)? onde n=número de dígitos unários.
    – epx
    Commented 25/02/2020 às 23:52
  • Devido ao fechamento de LR sob o complemento, seria pelo menos uma versão de decisão do número compostos. Commented 26/02/2020 às 12:15

1 Resposta 1

13
+100

Não é possível ter nenhum Autômato Finito Determinístico que reconheça números primos (ou reconheça números compostos, que é o subconjunto não trivial do complemento dos números primos).

Uma gramática que reconheça uma palavra também é capaz de produzi-la. Sempre. Sem exceções. No caso de um AFD, existe sempre uma gramática regular por baixo que é equivalente computacionalmente ao autômato.

Sendo assim, preciso encontrar uma prova de que não é possível escrever gramática alguma capaz de reconhecer números primos.

Como as linguagens regulares são fechadas no complemento (ie, se L é regular, então U\L também é regular, sendo U todas as palavras formadas pelas letras do alfabeto de L em todas as combinações possíveis), basta provar que não é possível encontrar primos que, por tabela, não será possível encontrar os compostos.

Aqui, vou demonstrar que não é possível nem mesmo escrever uma GLC que reconheça números primos! Como LLC é um superconjunto próprio de LR, isso significa que nenhuma LR é capaz de reconhecer um número como primo.

Ainda não consegui demonstrar que detectar se um número é composto é livre de contexto, mas vale ressaltar aqui que LLC não é fechada sob o complemento.

Para essa demonstração, precisamos recordar do lema do bombeamento para linguagens livres de contexto:

  • existe uma palavra u v w x y pertencente à L
  • tal que |v x| >= 1
  • tal que |v w x| <= p
  • então u v^n w x^n t também pertence a L, para todo inteiro n >= 0

Se não for possível encontrar essa palavra, então L não é livre de contexto.

Como estamos lidando com números em base unária, então o alfabeto é {1}. O comprimento de uma palavra é o número que ela representa.

Já que desejamos provar pelo lema do bombeamento que não é regular, tomemos o primo u + v + w + x + y como sendo a palavra u v w x y. Reordenemos o comprimento da palavra bombeada: n*v + n*x + u + w + y, e ainda podemos por n em evidência: n*(v+x) + u + w + y.

Aqui, temos duas opções:

  • o comprimento de u w y é nulo, portanto qualquer bombeamento de n != 1 produz um número não primo, seja 0 ou um número composto múltiplo de v+x
  • o comprimento de u w y é não nulo

Aqui, a única saída possível para uma linguagem que gere primos é a segunda. Então, isso deveria gerar primos para qualquer n, confere? Tomemos n = u + w + y. Assim, o comprimento da palavra ficaria (u+w+y)*(v+x) + u+w+y. Pondo u+w+y em evidência: (u+w+y)*(1+v+x). Esse número é composto, logo foi possível gerar um número não primo através do lema do bombeamento. Portanto, a conclusão que se pode chegar é que não existe LLC que gere apenas números primos.

Já que não há LLC que gere esse conjunto, também não há LR que seja capaz de reconhecer números primos. Por complemento, também não há LR que reconheça um número composto.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .