Mixing
Chomsky Hierarchy and P vs NP
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
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.
complexity-theory p-vs-np chomsky-hierarchy
asked Aug 25 at 11:14
Maverick98
82
add a comment |Â
up vote
1
down vote
favorite
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.
complexity-theory p-vs-np chomsky-hierarchy
asked Aug 25 at 11:14
Maverick98
82
I think this might be related to your query.
– Gokul
Aug 25 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 at 11:29
Where do you see any room for exceptions? The parsing algorithms that decide membership are completely general.
– reinierpost
Aug 25 at 14:41
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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.
complexity-theory p-vs-np chomsky-hierarchy
asked Aug 25 at 11:14
Maverick98
82
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.
complexity-theory p-vs-np chomsky-hierarchy
asked Aug 25 at 11:14
Maverick98
82
asked Aug 25 at 11:14
Maverick98
82
asked Aug 25 at 11:14
Maverick98
82
asked Aug 25 at 11:14
Maverick98
82
82
I think this might be related to your query.
– Gokul
Aug 25 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 at 11:29
Where do you see any room for exceptions? The parsing algorithms that decide membership are completely general.
– reinierpost
Aug 25 at 14:41
add a comment |Â
I think this might be related to your query.
– Gokul
Aug 25 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 at 11:29
Where do you see any room for exceptions? The parsing algorithms that decide membership are completely general.
– reinierpost
Aug 25 at 14:41
I think this might be related to your query.
– Gokul
Aug 25 at 11:24
I think this might be related to your query.
– Gokul
Aug 25 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 at 11:29
@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 at 11:29
Where do you see any room for exceptions? The parsing algorithms that decide membership are completely general.
– reinierpost
Aug 25 at 14:41
Where do you see any room for exceptions? The parsing algorithms that decide membership are completely general.
– reinierpost
Aug 25 at 14:41
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
5
down vote
accepted
Regular languages
Regular languages are in $mathbfP$ 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 $mathbfP$: Valiant showed in the 1970s that context-free grammars in Chomsky normal form can be parsed in time $O(n^3)$ [1]. $mathbfP$ strictly includes the set of context-free languages, since $a^nb^nc^nd^nmid ngeq 0$ is not context-free but is clearly in $mathbfP$.
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 $mathbfNP$ but, since a linear space Turing machine can use exponential time, probably there are context-sensitive languages that aren't in $mathbfNP$. However, showing this would be a major advance in complexity theory as it would imply that $mathbfNPneqmathbfPSPACE$.
The problem of "Here's a context-sensitive grammar $G$ and a string $w$: is $win L(G)$" is $mathbfPSPACE$-complete [2], so certainly every problem in $mathbfNP$ can be reduced to the parsing problem for context-sensitive gramars. However, that's not the same thing as saying that every language in $mathbfNP$ is defined by a context-sensitive grammar, since the $mathbfPSPACE$-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 $mathbfNP$ and includes undecidable languages such as the halting problem, which definitely aren't in $mathbfNP$.
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.
answered Aug 25 at 12:22
David Richerby
61.4k1594179
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
Regular languages
Regular languages are in $mathbfP$ 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 $mathbfP$: Valiant showed in the 1970s that context-free grammars in Chomsky normal form can be parsed in time $O(n^3)$ [1]. $mathbfP$ strictly includes the set of context-free languages, since $a^nb^nc^nd^nmid ngeq 0$ is not context-free but is clearly in $mathbfP$.
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 $mathbfNP$ but, since a linear space Turing machine can use exponential time, probably there are context-sensitive languages that aren't in $mathbfNP$. However, showing this would be a major advance in complexity theory as it would imply that $mathbfNPneqmathbfPSPACE$.
The problem of "Here's a context-sensitive grammar $G$ and a string $w$: is $win L(G)$" is $mathbfPSPACE$-complete [2], so certainly every problem in $mathbfNP$ can be reduced to the parsing problem for context-sensitive gramars. However, that's not the same thing as saying that every language in $mathbfNP$ is defined by a context-sensitive grammar, since the $mathbfPSPACE$-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 $mathbfNP$ and includes undecidable languages such as the halting problem, which definitely aren't in $mathbfNP$.
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.
answered Aug 25 at 12:22
David Richerby
61.4k1594179
add a comment |Â
up vote
5
down vote
accepted
Regular languages
Regular languages are in $mathbfP$ 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 $mathbfP$: Valiant showed in the 1970s that context-free grammars in Chomsky normal form can be parsed in time $O(n^3)$ [1]. $mathbfP$ strictly includes the set of context-free languages, since $a^nb^nc^nd^nmid ngeq 0$ is not context-free but is clearly in $mathbfP$.
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 $mathbfNP$ but, since a linear space Turing machine can use exponential time, probably there are context-sensitive languages that aren't in $mathbfNP$. However, showing this would be a major advance in complexity theory as it would imply that $mathbfNPneqmathbfPSPACE$.
The problem of "Here's a context-sensitive grammar $G$ and a string $w$: is $win L(G)$" is $mathbfPSPACE$-complete [2], so certainly every problem in $mathbfNP$ can be reduced to the parsing problem for context-sensitive gramars. However, that's not the same thing as saying that every language in $mathbfNP$ is defined by a context-sensitive grammar, since the $mathbfPSPACE$-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 $mathbfNP$ and includes undecidable languages such as the halting problem, which definitely aren't in $mathbfNP$.
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.
answered Aug 25 at 12:22
David Richerby
61.4k1594179
add a comment |Â
up vote
5
down vote
accepted
up vote
5
down vote
accepted
Regular languages
Regular languages are in $mathbfP$ 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 $mathbfP$: Valiant showed in the 1970s that context-free grammars in Chomsky normal form can be parsed in time $O(n^3)$ [1]. $mathbfP$ strictly includes the set of context-free languages, since $a^nb^nc^nd^nmid ngeq 0$ is not context-free but is clearly in $mathbfP$.
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 $mathbfNP$ but, since a linear space Turing machine can use exponential time, probably there are context-sensitive languages that aren't in $mathbfNP$. However, showing this would be a major advance in complexity theory as it would imply that $mathbfNPneqmathbfPSPACE$.
The problem of "Here's a context-sensitive grammar $G$ and a string $w$: is $win L(G)$" is $mathbfPSPACE$-complete [2], so certainly every problem in $mathbfNP$ can be reduced to the parsing problem for context-sensitive gramars. However, that's not the same thing as saying that every language in $mathbfNP$ is defined by a context-sensitive grammar, since the $mathbfPSPACE$-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 $mathbfNP$ and includes undecidable languages such as the halting problem, which definitely aren't in $mathbfNP$.
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.
answered Aug 25 at 12:22
David Richerby
61.4k1594179
Regular languages
Regular languages are in $mathbfP$ 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 $mathbfP$: Valiant showed in the 1970s that context-free grammars in Chomsky normal form can be parsed in time $O(n^3)$ [1]. $mathbfP$ strictly includes the set of context-free languages, since $a^nb^nc^nd^nmid ngeq 0$ is not context-free but is clearly in $mathbfP$.
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 $mathbfNP$ but, since a linear space Turing machine can use exponential time, probably there are context-sensitive languages that aren't in $mathbfNP$. However, showing this would be a major advance in complexity theory as it would imply that $mathbfNPneqmathbfPSPACE$.
The problem of "Here's a context-sensitive grammar $G$ and a string $w$: is $win L(G)$" is $mathbfPSPACE$-complete [2], so certainly every problem in $mathbfNP$ can be reduced to the parsing problem for context-sensitive gramars. However, that's not the same thing as saying that every language in $mathbfNP$ is defined by a context-sensitive grammar, since the $mathbfPSPACE$-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 $mathbfNP$ and includes undecidable languages such as the halting problem, which definitely aren't in $mathbfNP$.
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.
answered Aug 25 at 12:22
David Richerby
61.4k1594179
answered Aug 25 at 12:22
David Richerby
61.4k1594179
answered Aug 25 at 12:22
David Richerby
61.4k1594179
answered Aug 25 at 12:22
David Richerby
61.4k1594179
61.4k1594179
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f96606%2fchomsky-hierarchy-and-p-vs-np%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
I think this might be related to your query.
– Gokul
Aug 25 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 at 11:29
Where do you see any room for exceptions? The parsing algorithms that decide membership are completely general.
– reinierpost
Aug 25 at 14:41