3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think this might be related to your query. $\endgroup$ – Gokul Aug 25 '18 at 11:24
  • $\begingroup$ @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?? $\endgroup$ – user102382 Aug 25 '18 at 11:29
  • $\begingroup$ Where do you see any room for exceptions? The parsing algorithms that decide membership are completely general. $\endgroup$ – reinierpost Aug 25 '18 at 14:41
8
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy