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!
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. $\endgroup$