Do regular languages belong to Space(1)?
$begingroup$
I was wondering, if we take some regular language, will it be in Space(1)?
For a regular language X, for instance, we can construct an equivalent NFA that matches strings in the regular language.
But I cannot see why is X in Space(1).
If it is true, why is X or any other regular language in Space(1)?
complexity-theory turing-machines space-complexity
edited 16 mins ago
Yuval Filmus
197k15186350
asked 53 mins ago
hps13hps13
276
$endgroup$
add a comment |
$begingroup$
I was wondering, if we take some regular language, will it be in Space(1)?
For a regular language X, for instance, we can construct an equivalent NFA that matches strings in the regular language.
But I cannot see why is X in Space(1).
If it is true, why is X or any other regular language in Space(1)?
complexity-theory turing-machines space-complexity
edited 16 mins ago
Yuval Filmus
197k15186350
asked 53 mins ago
hps13hps13
276
$endgroup$
add a comment |
$begingroup$
I was wondering, if we take some regular language, will it be in Space(1)?
For a regular language X, for instance, we can construct an equivalent NFA that matches strings in the regular language.
But I cannot see why is X in Space(1).
If it is true, why is X or any other regular language in Space(1)?
complexity-theory turing-machines space-complexity
edited 16 mins ago
Yuval Filmus
197k15186350
asked 53 mins ago
hps13hps13
276
$endgroup$
I was wondering, if we take some regular language, will it be in Space(1)?
For a regular language X, for instance, we can construct an equivalent NFA that matches strings in the regular language.
But I cannot see why is X in Space(1).
If it is true, why is X or any other regular language in Space(1)?
complexity-theory turing-machines space-complexity
complexity-theory turing-machines space-complexity
edited 16 mins ago
Yuval Filmus
197k15186350
asked 53 mins ago
hps13hps13
276
edited 16 mins ago
Yuval Filmus
197k15186350
asked 53 mins ago
hps13hps13
276
edited 16 mins ago
Yuval Filmus
197k15186350
edited 16 mins ago
Yuval Filmus
197k15186350
edited 16 mins ago
Yuval Filmus
197k15186350
197k15186350
asked 53 mins ago
hps13hps13
276
asked 53 mins ago
hps13hps13
276
asked 53 mins ago
hps13hps13
276
276
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
A regular expression can be transformed into an NFA as you say. And an NFA can be transformed into a DFA. This latter transformation is exponential in the worst case (in terms of the size of the original NFA), but that is irrelevant. The amount of time this transformation takes is independent from the size of the input, and is thus $O(1)$.
Similarly, the size of this DFA is also independent from the size of the input, so storing it takes $O(1)$ space. No further space is needed other than the DFA, and thus a recognizer for a regular expression can run in $O(1)$ space.
answered 18 mins ago
orlporlp
6,0451826
$endgroup$
$begingroup$
Is there a formal proof to that? it is easier for me to understand it as a process of "convincing". why is the amount of time the transformation takes is independent from the input? and why is the size of the obtained DFA is independent from the size of the input?
$endgroup$
– hps13
5 mins ago
add a comment |
Your Answer
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%2f107355%2fdo-regular-languages-belong-to-space1%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$
A regular expression can be transformed into an NFA as you say. And an NFA can be transformed into a DFA. This latter transformation is exponential in the worst case (in terms of the size of the original NFA), but that is irrelevant. The amount of time this transformation takes is independent from the size of the input, and is thus $O(1)$.
Similarly, the size of this DFA is also independent from the size of the input, so storing it takes $O(1)$ space. No further space is needed other than the DFA, and thus a recognizer for a regular expression can run in $O(1)$ space.
answered 18 mins ago
orlporlp
6,0451826
$endgroup$
$begingroup$
Is there a formal proof to that? it is easier for me to understand it as a process of "convincing". why is the amount of time the transformation takes is independent from the input? and why is the size of the obtained DFA is independent from the size of the input?
$endgroup$
– hps13
5 mins ago
add a comment |
$begingroup$
A regular expression can be transformed into an NFA as you say. And an NFA can be transformed into a DFA. This latter transformation is exponential in the worst case (in terms of the size of the original NFA), but that is irrelevant. The amount of time this transformation takes is independent from the size of the input, and is thus $O(1)$.
Similarly, the size of this DFA is also independent from the size of the input, so storing it takes $O(1)$ space. No further space is needed other than the DFA, and thus a recognizer for a regular expression can run in $O(1)$ space.
answered 18 mins ago
orlporlp
6,0451826
$endgroup$
$begingroup$
Is there a formal proof to that? it is easier for me to understand it as a process of "convincing". why is the amount of time the transformation takes is independent from the input? and why is the size of the obtained DFA is independent from the size of the input?
$endgroup$
– hps13
5 mins ago
add a comment |
$begingroup$
A regular expression can be transformed into an NFA as you say. And an NFA can be transformed into a DFA. This latter transformation is exponential in the worst case (in terms of the size of the original NFA), but that is irrelevant. The amount of time this transformation takes is independent from the size of the input, and is thus $O(1)$.
Similarly, the size of this DFA is also independent from the size of the input, so storing it takes $O(1)$ space. No further space is needed other than the DFA, and thus a recognizer for a regular expression can run in $O(1)$ space.
answered 18 mins ago
orlporlp
6,0451826
$endgroup$
A regular expression can be transformed into an NFA as you say. And an NFA can be transformed into a DFA. This latter transformation is exponential in the worst case (in terms of the size of the original NFA), but that is irrelevant. The amount of time this transformation takes is independent from the size of the input, and is thus $O(1)$.
Similarly, the size of this DFA is also independent from the size of the input, so storing it takes $O(1)$ space. No further space is needed other than the DFA, and thus a recognizer for a regular expression can run in $O(1)$ space.
answered 18 mins ago
orlporlp
6,0451826
answered 18 mins ago
orlporlp
6,0451826
answered 18 mins ago
orlporlp
6,0451826
answered 18 mins ago
orlporlp
6,0451826
6,0451826
$begingroup$
Is there a formal proof to that? it is easier for me to understand it as a process of "convincing". why is the amount of time the transformation takes is independent from the input? and why is the size of the obtained DFA is independent from the size of the input?
$endgroup$
– hps13
5 mins ago
add a comment |
$begingroup$
Is there a formal proof to that? it is easier for me to understand it as a process of "convincing". why is the amount of time the transformation takes is independent from the input? and why is the size of the obtained DFA is independent from the size of the input?
$endgroup$
– hps13
5 mins ago
$begingroup$
Is there a formal proof to that? it is easier for me to understand it as a process of "convincing". why is the amount of time the transformation takes is independent from the input? and why is the size of the obtained DFA is independent from the size of the input?
$endgroup$
– hps13
5 mins ago
$begingroup$
Is there a formal proof to that? it is easier for me to understand it as a process of "convincing". why is the amount of time the transformation takes is independent from the input? and why is the size of the obtained DFA is independent from the size of the input?
$endgroup$
– hps13
5 mins ago
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%2f107355%2fdo-regular-languages-belong-to-space1%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
