Is it possible to express all prime numbers using a regular grammar?

We will use the Pumping Lemma, in order to understand whether it is possible to describe the prime numbers using a Regular Grammar.

Problem Statement

For simplicity let's consider the unary numeral system (number N is represented by word X_N, which consists of N consecutive symbols '1').
Also, let's use the following notation: |X_i| in order to express the amount of '1' symbols inside the word X_i.

So, having the infinite set of words, which corresponds to prime numbers:

X₁ = 11
X₂ = 111
X₃ = 11111
X₄ = 1111111
X₅ = 11111111111
...

where |X_i| is a prime number, for every i,

we would like to understand, whether it is possible to express all words from this language using a regular grammar?

In other words, is it possible construct the finite state machine, which will be able to recognize all prime numbers (and only the prime numbers), expressed in unary numeral system?

Pumping Lemma

The Pumping Lemma states, that every sufficiently long word of a regular language can be infinitely many times expanded in a special way, such that every new word (obtained after expansion of the original word) will belong to this language as well.

Formally saying, for every infinite regular language L: every word X_i (such, that length of the word is greater than some threshold) can be splitted into 3 consecutive parts: X, Y and Z, and every new word (e.g. XYYZ, XYYYZ, ..., XYⁿZ) will belong to the language L as well.

The lemma can be understood in such way, that the reguar expression for recognizing of any infinite regular language must contain a Kleene operator.

For example, lets's consider a regular language L, which corresponds to the following regular expression: ( 1 | 11 | 111 | 111(1)*1 )

Let's select some sufficiently long word of this language:
W_i = 111111

One of the possible ways to split W_i is:
W_i = XYZ = 111 _ 11 _ 1
(underscore characters are not a part of the alphabet of the language L, but I am using these characters just to display the separation between X, Y and Z)

So, the parts of the word W_i are:
X = 111
Y = 11
Z = 1

We can infinitely many times replicate the part Y ("pump" the word W_i), and all generated words: XY²Z, XY³Z, ..., XYⁿZ will belong to the langauge L as well:

XYZ = 111111
XY²Z = 11111111
XY³Z = 1111111111

The Pumping Lemma is only a necessary condition (and not a sufficient condition) for the language being a regular.

However, this lemma is a very convenient tool for proving, that the language is not regular: proving that every sufficiently long word of the language can't be "pumped" - implies that the language is not regular.

Regular grammar for prime numbers?

The unary representation W_p of every prime number p (such that |W_p| = p) can be splited into 3 parts: X, Y and Z.

Which, in general case, implies that:
|W_p| = |XYZ| = |X| + |Y| + |Z|

XYⁿZ means, that we just should replicate n times the Y part of the word W_p.

So, the amount of symbols '1' inside the generated word can be represented as:
|XYⁿZ| = |X| + n×|Y| + |Z| = (|X| + |Y| + |Z|) + (n - 1)×|Y| = |W_p| + (n - 1)×|Y|

We can choose the n = |W_p| + 1
Which implies, that:
|XYⁿZ| = |W_p| + (n - 1)×|Y| = |W_p| + |W_p|×|Y| = (|Y| + 1)×|W_p|
Hence, XYⁿZ is a composite number.

Hence, for any arbitrary splitting of W_p (any arbitrary prime number), we can choose such n, that XYⁿZ will be a composite number.

Our implication contradicts to the Pumping Lemma, which leads to the conclusion, that the language, which consists of the prime numbers can’t be expressed using a Regular Grammar.