Minimal class of grammar required to run program

In computability we have the hierarchy of grammars "https://en.wikipedia.org/wiki/Chomsky_hierarchy". In this hierarchy we have many classes of grammar. This hierarchy has Turing machines at the top, and weaker machines lower. Machines are able to "recognize" languages within their class, and they are able to "decide" the halt-ability of weaker languages. "http://www.radford.edu/~nokie/classes/420/Chap3-Langs.html". Doing such tasks has different complexity classes based on the class of what is being acted on.

Here is my question: What is the process of determining the minimal class of machine required to recognize, and then decide, on a language. Also what is the cost of this function in relation to the class of machine?

I know that one way is to construct a grammar for a weak machine, see if it accepts, and then if you cant find one work your way up the hierarchy.

I certainly hope there is a solution to this problem besides just brute forcing potentially forever? Thanks!

• Do you ask for an (existence of) algorithm that can take your grammar and compress it to a lower type grammar? – Valentin Tihomirov Jan 10 '16 at 12:05
• @ValentinTihomirov That is not the question I am asking. I assume that is impossible. I am asking for an (or the existence of) algorithm to determine the class of a machine required to run a program (besides brute force potentially forever). – 44701 Jan 10 '16 at 12:13
• So, you have just finished reading the table, which maps Unrestricted grammar => Turing Machine, Context-sensitive grammar => Linear-bounded automaton => Context-free grammar => Pushdown automaton and Regular grammar => Finite state automaton and ask for an algorithm to implement this simple 4-row tabe? It looks like a research-level question. – Valentin Tihomirov Jan 10 '16 at 13:06