# 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.

• I think this might be related to your query. – Gokul Aug 25 '18 at 11:24
• @Gokul I was recommended that question when I posted mine , but I can't actually understand what the answer is when they speak of decidable languages. What I get is that to form regular languages and context-free languages are P class problems , but there are some exceptions?? – maverick98 Aug 25 '18 at 11:29
• Where do you see any room for exceptions? The parsing algorithms that decide membership are completely general. – reinierpost Aug 25 '18 at 14:41

### 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 "Here's a context-sensitive grammar $$G$$ and a string $$w$$: is $$w\in L(G)$$" 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.