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.

|cite|improve this question
$\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$ – maverick98 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
7
$\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

Not the answer you're looking for? Browse other questions tagged or ask your own question.