What is the Chomsky class of a language containing strings of a prime length?

Question

I recently saw a Perl golf program that used a perl regex in a loop in order to test primality. Perl's regex's are strictly more powerful the regular expressions and applying them in a loop can be used to basically create a turning machine.

However it made me wonder. If you have a language $P = \{ a^n : n \text{ is prime} \} $ what class is it in?

Now, since we can create a computer program to test primality, it is clear that $P$ is recursively enumerable.

Also, the pumping lemma can show that the language is not regular. However I'm unsure if it could be context free or context sensitive.

Answer 1

Concerning the context-sensitiveness:

If the length is not prime, it has some divisor $k$. This means that you can write the string as $$a^k\cdot a^k \cdots a^k.$$ Checking this can be done in a tedious but straight-forward way (for $k$ from 2 to (half) the string's length) without exceeding the space that the original string occupies. Thus the language is context-sensitive.

Answer 2

Parikh's theorem states that every context-free language is commutatively equivalent to some regular language. As a corollary, every context-free language on a one-letter alphabet is regular. Thus your language is not context-free.

Answer 3

In order for something to be a context sensitiveness language the it should be able to be matched by a turning machine whos size is limited to a linear function of the size. Here is an algorithm to test primality in a Turing machine. Assuming that the tape is populated with the string at be beginning and blanks(#) for the rest.

You then create copy last two chars of the string back by one so the tape looks like

[aaaa...aaaa#aa####....###]

Where [ and ] are the end markers.

Then you write in the cell after this 10#0# so the string will look like this.

[aaaa...aaaa#aa#10#00#....###]

Then do the following.

    Set the a to the left of the leftmost # to # and set the cell that was 
    previously # to a (advancing the blank one set left through string).

    To each of the number pairs do the following.  Increment the second number 
    of the pair mod the base of the first (the numbers are represented in 
    binary).

    If you reach the end of the number pairs without any of the numbers being 
    set to 0 then write down the length of the string between the blanks in 
    binary and write down 0's of that has the same string length as the binary
    number number you just wrote.

Repeat the above until you reach the start of the string.

The accept state is if on the last operation you added a number pair.

This is a variation of the Sieve of Eratosthenes and at worst its space requirements is $O(\sqrt{n}\log{n})$ since this is sublinear it can be implemented on a linear bounded Turing machine hence it is context sensitive.