Hello first of all let us discuss about the Context Sensitive Language(CSL), In Chomsky Hierarchy CSL is belongs to Type-1 grammar. Basically the difference between Regular Language and Context Free Language is that Regular Languages won't remember anything i.e. what it has (I mean here either NFA or DFA) processed until the current input character, where as Context Free Languages(Pushdown Automata) will remember the last state, just one last state! this is what pumping lemma for both RL and CFL says!
Now when ever want to remember more than one last state, Pushdown Automata won't suitable because we are simulating Pushdown Automata with only one stack with infinite depth(i.e. stack can remember the last state, precisely last input character) and please note that the last input character has to be a pattern not just some arbitary string! If it is not the pattern, if it is some random string then we won't need Pushdown Automata to process it! We need Pushdown Automata because we need to have some pattern and pumping lemma work only with the patterns of some sense not just some arbitary strings!
Now to overcome this difficult the Automata community proposed some thing called Context Sensitive Languages(CSL) which we can imagine same as CFL and a Pushdown Automata with difference that there are more than one stack!(because we need to remember more than one state i.e. more than one pattern). These CSL will be simulated by some machines called Linear Bound Automata(LBA) which is verymuch similar (almost as same as) Non Deterministic Turing Machine(NDTM)!
So what is the difference between Deterministic Turing Machine(DTM) and Linear Bound Automata, if we can build a DTM for some language then we can write a program in the computer or conversly if we can write a program for some problem then there should exist a DTM for that problem!
In Chomsky Hierarchy Type-0 grammars called as Recursive Enumerable Language(REL) and they are recognized by Turing Machine(either DTM or NDTM). Please note that REL may or maynot halt on all input for the strings, where as CSL will halt on all input strings(always hatls).
So coming to question a^p | p is prime consider following cases
1. Since there is no pattern for prime numbers they can't be identified by both FSA (Finite State Automation) or Pushdown Automation.
2. Since we were given just p as prime number and there is no bound on the length so we need infinite amount of space which can be provided by Turing Machine so we can recoginze it by a Turing Macine.
Now whether it is decidable or not decidable?
We can see it in this way
We can write a program to check the prime numbers, and that too we can do it in finite time so there exist a Turing Machine which halt on every string, and by the definition of NDTM halts on every input and language accepted by NDTM will be CSL so therefore a^p | p is prime is a CSL.
And it can be Recursive Language also, Recursive Languages are not a part of Chomsky Hierarchy they reside between Type-0 and Type-1 grammars in hierarchy! and a language is Recursive if and only if every string on some Turing Machine halt after some transitions.
Please refer https://en.wikipedia.org/wiki/Linear_bounded_automaton
and please let me know any mistake is there in concept!
