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

Question

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

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

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

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

In fact, if you have ever used your fingers to make an account or report a quantity, you have already used anointing. 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 to use the character 1. So if I want to represent the 6 decimal in unary, I must 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 numbers that are not prime. It is divided into two parts:

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

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

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, okay? Then, it consists of a rearview mirror (the \1), who does the exact match of the previous grouping. But, 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 until infinitely many times.

So, if the grouped string has length 3, the regular expression will give match in strings of length 6, 9, 12 and so on. This is because the Kleene cross will ensure that the string as a whole will have the following length (for l being the size of the grouping string):

l + k*l, k >= 1

So, in order for the number not to be prime, you need to ensure that l != 1. Returning to the grouping, this is defined in 11+?. Here the wedding occurs with any string of size 2 or more (the interrogation after Kleene’s cross is only to be less greedy possible and to run faster, it is not strictly necessary). So with that, we have to l >= 2. So if that second part of the regular expression gives a match in the string, we have that the number passed is a composite number.

Thus, through an expression that transcends the regular languages, this expression was assembled that recognizes the primality (or, rather, the non-prinality) of a number. Note that mirrors and other forms of explicit memory do not consist of expressions mathematically regular. Behold plus about the subject.

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

Answer 1

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 produce it. Always. No exceptions. In the case of an DFA, there is always a regular grammar underneath that is computationally equivalent to the automaton.

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

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

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

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

For this demonstration, we need to remember the pumping lemma for context-free languages:

• there is a word u v w x y belonging to the L
• such that |v x| >= 1
• such that |v w x| <= p
• then u v^n w x^n t also belongs to L, whole n >= 0

If that word cannot be found, then L is not context-free.

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

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

Here, we have two options:

• the length of u w y is null, therefore any pumping of n != 1 produces a non-prime number, i.e. 0 or a multiple composite number of v+x
• the length of u w y is non-zero

Here, the only possible output for a language that generates primes is the second. So, this should generate primes for any n, check? Let’s take n = u + w + y. So the length of the word would be (u+w+y)*(v+x) + u+w+y. Putting u+w+y in evidence: (u+w+y)*(1+v+x). This number is composed, so it was possible to generate a non-prime number through the pumping lemma. So the conclusion that can be drawn 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.