Everybody knows the Chomsky-hierarchy for describing formal languages and big-O notation for describing time and space complexity of a function.
We know, that each class in the Chomsky-hierarchy corresponds to an atomata, that can recognize any language in the corresponding class.
The question is: What is the worst-case time and space complexity of these automatas given any language of the above class?
What I found out already:
Chomksy-3 class, the regular languages can be recognized by an FSM of n-states where n is a finite number. IMO this makes it require O(n) space and O(l) time, where l is the length of the input.
Chomsky-2 class, the context free languages can be recognised by a Non-deterministic pushdown automaton. CYK algorithm run $n^3 * G$ where n is the length of the input and G is the number of rules in the grammar in Chomsky Normal form.
But how much space needed? Do we have better bounds?
Chomsky-1 class, the context sensitive languages can be recognised by a Linear-bounded non-deterministic Turing machine.
This class seem to depend on the length of the context to be recognised. Maybe in exponential time.
Chomksy-0 class, the recursively enumerable languages can be recognised by Turing machine.
Can anything stated for this class? If not, why? Maybe the $P \stackrel{?}{=} NP$ problem is related.
Are the above statements true?
Please give citations to your answer!