Minimal class of grammar required to run program
Determining whether a context-free grammar generates a regular language is undecidable (this is exercise 9.107 in Singh's Elements of computation theory; the reduction is from the Post correspondence problem). So if you are OK with a language being given to you as a context-free grammar, then even determining whether a language is regular or context-free but not regular is undecidable.