Chomsky Hierarchy and P vs NP
$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.
complexity-theory p-vs-np chomsky-hierarchy
asked Aug 25 '18 at 11:14
Maverick98Maverick98
82
$endgroup$
add a comment |
$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.
complexity-theory p-vs-np chomsky-hierarchy
asked Aug 25 '18 at 11:14
Maverick98Maverick98
82
$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
add a comment |
$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.
complexity-theory p-vs-np chomsky-hierarchy
asked Aug 25 '18 at 11:14
Maverick98Maverick98
82
$endgroup$
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
complexity-theory p-vs-np chomsky-hierarchy
asked Aug 25 '18 at 11:14
Maverick98Maverick98
82
asked Aug 25 '18 at 11:14
Maverick98Maverick98
82
asked Aug 25 '18 at 11:14
Maverick98Maverick98
82
asked Aug 25 '18 at 11:14
Maverick98Maverick98
82
asked Aug 25 '18 at 11:14
Maverick98Maverick98
82
82
$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
add a comment |
$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
$begingroup$
I think this might be related to your query.
$endgroup$
– Gokul
Aug 25 '18 at 11:24
$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$
@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
$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
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
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 '18 at 12:22
David RicherbyDavid Richerby
66.3k15101190
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
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
Required, but never shown
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
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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 '18 at 12:22
David RicherbyDavid Richerby
66.3k15101190
$endgroup$
add a comment |
$begingroup$
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 '18 at 12:22
David RicherbyDavid Richerby
66.3k15101190
$endgroup$
add a comment |
$begingroup$
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 '18 at 12:22
David RicherbyDavid Richerby
66.3k15101190
$endgroup$
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 '18 at 12:22
David RicherbyDavid Richerby
66.3k15101190
answered Aug 25 '18 at 12:22
David RicherbyDavid Richerby
66.3k15101190
answered Aug 25 '18 at 12:22
David RicherbyDavid Richerby
66.3k15101190
answered Aug 25 '18 at 12:22
David RicherbyDavid Richerby
66.3k15101190
66.3k15101190
add a comment |
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$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