Chomsky Hierarchy and P vs NP I have read multiple questions here that involve this kind of subject but I haven't found any definite answer. In what class do regular languages belong? (P or NP or some regular are P and other NP), context-free languages? (same question) ,context-sensitive? and general languages? . I personally believe all regular languages belong in P class and the rest (more complex) languages of chomsky hierarchy are in the NP class. Can someone answer and provide some kind of proof for the answer? Thanks in advance.
Regular languages
Regular languages are in $\mathbf{P}$ because a deterministic finite automaton is a restricted deterministic Turing machine that runs in linear time.
Context-free languages
In fact, any context-free language is in $\mathbf{P}$: Valiant showed in the 1970s that context-free grammars in Chomsky normal form can be parsed in time $O(n^3)$ [1]. $\mathbf{P}$ strictly includes the set of context-free languages, since $\{a^nb^nc^nd^n\mid n\geq 0\}$ is not context-free but is clearly in $\mathbf{P}$.
Context-sensitive languages
Context-sensitive languages can be parsed in nondeterministic linear space [2]. We don't know the exact relationship between this class and $\mathbf{NP}$ but, since a linear space Turing machine can use exponential time, probably there are context-sensitive languages that aren't in $\mathbf{NP}$. However, showing this would be a major advance in complexity theory as it would imply that $\mathbf{NP}\neq\mathbf{PSPACE}$.
The problem of &quot;Here's a context-sensitive grammar $G$ and a string $w$: is $w\in L(G)$&quot; is $\mathbf{PSPACE}$-complete [2], so certainly every problem in $\mathbf{NP}$ can be reduced to the parsing problem for context-sensitive gramars. However, that's not the same thing as saying that every language in $\mathbf{NP}$ is defined by a context-sensitive grammar, since the $\mathbf{PSPACE}$-completeness result allows arbitrary polynomial-time computation in the reduction and also allows the grammar to depend on the instance. Hopefully, somebody can post a comment or answer clarifying this.
Unrestricted grammars
Unrestricted grammars define all recursively-enumerable languages. This includes all of $\mathbf{NP}$ and includes undecidable languages such as the halting problem, which definitely aren't in $\mathbf{NP}$.

References
[1] L. G. Valiant, General context-free recognition in less than cubic time, Journal of Computer and System Sciences 10(2):308–315, 1974.
[2] Context-sensitive language, Wikipedia.