Is a finite state machine capable of detecting primality of a number?

I recently saw a publication of how Perl was taught to recognize a prime number using regular expressions. The regular expression in question is: 

/^1?$|^(11+?)\1+$/

The only requirement to this regular expression is that the number be provided in unary format (the post shows how to make the transformation from a decimal number to Unary in Perl).

Do you know what this "unary format"is? Well, different from our usual decimal (or hexadecimal or binary), the unary is not positional.

In fact, if you've ever used your fingers to make an account or report an amount, you've already used unary. In this format, the number of symbols of an expression (or fingers raised from the hand) corresponds to the number in question. For example, X in unary is equivalent to decimal 1, and XXXXX is equivalent to decimal 5.

Any symbol can be used in the unary representation, and the most common is use the character 1. So if I want to represent the decimal 6 in unary, I should repeat the symbol a total of six times; using the symbol 1, the representation of the six would be 111111

How does this expression work? Well, it actually detects the numbers that are not Cousins. It is divided into two parts:

  • ^1?$
  • ^(11+?)\1+$

The first part is responsible for taking trivially non-prime numbers: the 0 and the 1. The second part is more interesting, though.

In the second part, we have a term that is contained in a grouping (the 11+?). Let's leave him in the corner for now, shall we? It then consists of a rear-view mirror (the \1), which makes the exact match of the previous grouping. Only, not satisfied with this, this same match comes followed by the Kleene cross, which indicates that the expression must appear at least 1 time and can repeat itself even infinitely.

Logo, if the string grouped with length 3, the regular expression will give match in strings of length 6, 9, 12 and so on. This is because Kleene's Cross will ensure that the entire string will have the following length (for l being the size of the grouping string): 

l + k*l, k >= 1

So that the number is not prime, one must ensure that l != 1. Going back to grouping, this is set to 11+?. Here the marriage occurs with any string of size 2 or more (the question after Kleene's Cross is only to be as greedy as possible and rotate faster, it is not strictly necessary). So, with that, we have to l >= 2. So, if this second part of the regular expression gives a match in the string, we have that the number passed is a compound number.

Thus, through an expression that transcends regular languages, this expression has been assembled that recognizes the primality (or, rather, the non-primality) of a number. It is worth remembering that mirrors and other forms of explicit memory do not consist of mathematically regular expressions. see more about the subject .

So, is it possible to draw some deterministic finite automaton that can recognize if a number is prime? If so, how is he? If not, what is the proof that this problem cannot be solved through regular language?

Author: Jefferson Quesado, 2020-02-19
Source

1 answers

It is not possible to have any deterministic finite automaton that recognizes prime numbers (or recognizes compound numbers, which is the nontrivial subset of the complement of prime numbers).

A grammar that recognizes a word is also capable of producing it . Always. No exceptions. In the case of an AFD, there is always a regular grammar underneath that is computationally equivalent to the automaton.

So, I need to find proof that it is not possible to write some grammar capable of recognizing prime numbers.

Since regular languages are closed in the complement (ie, if L is regular, then U\L is also regular, being U all words formed by the letters of the alphabet of L in all possible combinations), it is enough to prove that it is not possible to find primes that, by table, it will not be possible to find

Here, I will demonstrate that it is not even possible write a GLC that recognizes prime numbers! Since LLC is a proper superset of LR, this means that no LR is able to recognize a number as a prime.

I have not yet been able to demonstrate that detecting whether a number is composed is context-free, but it is worth noting here that LLC is not closed under the complement.

For this demonstration, we need to recall the pumping motto for context-free languages:

  • There is a u v w x y word belonging to L
  • such that |v x| >= 1
  • such that |v w x| <= p
  • so u v^n w x^n t also belongs to L, for every integer n >= 0

If it is not possible to find this word, then L is not context-free.

Since we are dealing with numbers on a unary basis, then the alphabet is {1}. The length of a word is the number it represents.

Since we wish to prove by the pumping motto that it is not regular, let's take the prime u + v + w + x + y as the word u v w x y. Let's reorder the length of the pumped word: n*v + n*x + u + w + y, and we can still by n in evidence: n*(v+x) + u + w + y.

Here, we have two options:

  • the length of u w y is null, so any pumping of n != 1 produces a non-prime number, either 0 or a multiple compound number of v+x
  • the length of u w y is non-null

Here, the only possible output for a language that generates Cousins is second. So this should generate primes for any n, check? Let's take n = u + w + y. Thus, the length of the word would be (u+w+y)*(v+x) + u+w+y. Putting u+w+y into evidence: (u+w+y)*(1+v+x). This number is composed, so it was possible to generate a non-prime number through the pumping motto. Therefore, the conclusion that can be reached is that there is no LLC that generates only prime numbers.

Since there is no LLC that manages this set, there is also no LR that is able to recognize prime numbers. By complement, there is also no LR that recognizes a compound number.

 12
Author: Jefferson Quesado, 2020-02-26 04:20:40