Do regular languages belong to Space(1)?Decidability of MachinesPower of Double - Logarithmic SpaceProve that $TQBF notin SPACE(n^frac13)$How to Study Space ComplexityWhy is the set of NFA that accept all words in co-NPSPACE?Difference between read-only Turing machine and non-erasing Turing machineShow Recognizing two Regular Expressions as equal is in PSPACEProve that the set of recursive languages is infiniteMore details on a language decided in $Theta(log log n)$ spaceDoes there exist a Turing-machine that runs in time $o(nlog n)$, but not $O(n)$?
How come there are so many candidates for the 2020 Democratic party presidential nomination?
a sore throat vs a strep throat vs strep throat
What does ゆーか mean?
How to fry ground beef so it is well-browned
555 timer FM transmitter
bldc motor, esc and battery draw, nominal vs peak
Which big number is bigger?
Is there any official lore on the Far Realm?
Why do games have consumables?
Two field separators (colon and space) in awk
Why did C use the -> operator instead of reusing the . operator?
How do I reattach a shelf to the wall when it ripped out of the wall?
Relationship between strut and baselineskip
Can someone publish a story that happened to you?
How to prevent z-fighting in OpenSCAD?
Can I criticise the more senior developers around me for not writing clean code?
Is Diceware more secure than a long passphrase?
Is the claim "Employers won't employ people with no 'social media presence'" realistic?
How exactly does Hawking radiation decrease the mass of black holes?
What happens to Mjolnir (Thor's hammer) at the end of Endgame?
How to write a column outside the braces in a matrix?
How do I deal with a coworker that keeps asking to make small superficial changes to a report, and it is seriously triggering my anxiety?
Checks user level and limit the data before saving it to mongoDB
Betweenness centrality formula
Do regular languages belong to Space(1)?
Decidability of MachinesPower of Double - Logarithmic SpaceProve that $TQBF notin SPACE(n^frac13)$How to Study Space ComplexityWhy is the set of NFA that accept all words in co-NPSPACE?Difference between read-only Turing machine and non-erasing Turing machineShow Recognizing two Regular Expressions as equal is in PSPACEProve that the set of recursive languages is infiniteMore details on a language decided in $Theta(log log n)$ spaceDoes there exist a Turing-machine that runs in time $o(nlog n)$, but not $O(n)$?
$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 Apr 22 at 12:48
Yuval Filmus
197k15187350
asked Apr 22 at 12:12
hps13hps13
346
$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 Apr 22 at 12:48
Yuval Filmus
197k15187350
asked Apr 22 at 12:12
hps13hps13
346
$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 Apr 22 at 12:48
Yuval Filmus
197k15187350
asked Apr 22 at 12:12
hps13hps13
346
$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 Apr 22 at 12:48
Yuval Filmus
197k15187350
asked Apr 22 at 12:12
hps13hps13
346
edited Apr 22 at 12:48
Yuval Filmus
197k15187350
asked Apr 22 at 12:12
hps13hps13
346
edited Apr 22 at 12:48
Yuval Filmus
197k15187350
edited Apr 22 at 12:48
Yuval Filmus
197k15187350
edited Apr 22 at 12:48
Yuval Filmus
197k15187350
197k15187350
asked Apr 22 at 12:12
hps13hps13
346
asked Apr 22 at 12:12
hps13hps13
346
asked Apr 22 at 12:12
hps13hps13
346
346
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 Apr 22 at 12:47
orlporlp
6,4851927
$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
Apr 22 at 12:59
4
$begingroup$
The NFA->DFA transformation doesn't even refer to the input (it's purely an operation on the language itself), so how could the input size matter?
$endgroup$
– jasonharper
Apr 22 at 13:16
1
$begingroup$
re: "storing it takes $O(1)$ space" this seems a little misleading. Since we're talking about Turing machines, the DFA doesn't have to get "stored" at all, but rather a DFA is a Turing machine that makes no use of the memory tape (since we're talking sublinear space we need separate input and memory tapes on the Turing Machine).
$endgroup$
– DreamConspiracy
Apr 22 at 15:04
$begingroup$
understood, thank you. @DreamConspiracy, would appreciate reading any additions you might have. @ jasonharper, thank you for explaining, it helped me a lot
$endgroup$
– hps13
Apr 22 at 15:37
$begingroup$
@DreamConspiracy Conceptually the DFA does needs to be stored. Remember that the inputs to our algorithm are a regular expression and an input - I'm not assuming that we get to do any pre-computation. The DFA would have to be generated during the runtime and stored in memory as well. But this generation time and memory requirement are both independent of the input (size), and thus $O(1)$. After we've reached that conclusion we could conclude we can pre-compute the DFA and don't have to store it explicitly, but the conclusion comes first, the optimization later.
$endgroup$
– orlp
Apr 22 at 18:48
|
show 1 more 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 Apr 22 at 12:47
orlporlp
6,4851927
$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
Apr 22 at 12:59
4
$begingroup$
The NFA->DFA transformation doesn't even refer to the input (it's purely an operation on the language itself), so how could the input size matter?
$endgroup$
– jasonharper
Apr 22 at 13:16
1
$begingroup$
re: "storing it takes $O(1)$ space" this seems a little misleading. Since we're talking about Turing machines, the DFA doesn't have to get "stored" at all, but rather a DFA is a Turing machine that makes no use of the memory tape (since we're talking sublinear space we need separate input and memory tapes on the Turing Machine).
$endgroup$
– DreamConspiracy
Apr 22 at 15:04
$begingroup$
understood, thank you. @DreamConspiracy, would appreciate reading any additions you might have. @ jasonharper, thank you for explaining, it helped me a lot
$endgroup$
– hps13
Apr 22 at 15:37
$begingroup$
@DreamConspiracy Conceptually the DFA does needs to be stored. Remember that the inputs to our algorithm are a regular expression and an input - I'm not assuming that we get to do any pre-computation. The DFA would have to be generated during the runtime and stored in memory as well. But this generation time and memory requirement are both independent of the input (size), and thus $O(1)$. After we've reached that conclusion we could conclude we can pre-compute the DFA and don't have to store it explicitly, but the conclusion comes first, the optimization later.
$endgroup$
– orlp
Apr 22 at 18:48
|
show 1 more 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 Apr 22 at 12:47
orlporlp
6,4851927
$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
Apr 22 at 12:59
4
$begingroup$
The NFA->DFA transformation doesn't even refer to the input (it's purely an operation on the language itself), so how could the input size matter?
$endgroup$
– jasonharper
Apr 22 at 13:16
1
$begingroup$
re: "storing it takes $O(1)$ space" this seems a little misleading. Since we're talking about Turing machines, the DFA doesn't have to get "stored" at all, but rather a DFA is a Turing machine that makes no use of the memory tape (since we're talking sublinear space we need separate input and memory tapes on the Turing Machine).
$endgroup$
– DreamConspiracy
Apr 22 at 15:04
$begingroup$
understood, thank you. @DreamConspiracy, would appreciate reading any additions you might have. @ jasonharper, thank you for explaining, it helped me a lot
$endgroup$
– hps13
Apr 22 at 15:37
$begingroup$
@DreamConspiracy Conceptually the DFA does needs to be stored. Remember that the inputs to our algorithm are a regular expression and an input - I'm not assuming that we get to do any pre-computation. The DFA would have to be generated during the runtime and stored in memory as well. But this generation time and memory requirement are both independent of the input (size), and thus $O(1)$. After we've reached that conclusion we could conclude we can pre-compute the DFA and don't have to store it explicitly, but the conclusion comes first, the optimization later.
$endgroup$
– orlp
Apr 22 at 18:48
|
show 1 more 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 Apr 22 at 12:47
orlporlp
6,4851927
$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 Apr 22 at 12:47
orlporlp
6,4851927
answered Apr 22 at 12:47
orlporlp
6,4851927
answered Apr 22 at 12:47
orlporlp
6,4851927
answered Apr 22 at 12:47
orlporlp
6,4851927
6,4851927
$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
Apr 22 at 12:59
4
$begingroup$
The NFA->DFA transformation doesn't even refer to the input (it's purely an operation on the language itself), so how could the input size matter?
$endgroup$
– jasonharper
Apr 22 at 13:16
1
$begingroup$
re: "storing it takes $O(1)$ space" this seems a little misleading. Since we're talking about Turing machines, the DFA doesn't have to get "stored" at all, but rather a DFA is a Turing machine that makes no use of the memory tape (since we're talking sublinear space we need separate input and memory tapes on the Turing Machine).
$endgroup$
– DreamConspiracy
Apr 22 at 15:04
$begingroup$
understood, thank you. @DreamConspiracy, would appreciate reading any additions you might have. @ jasonharper, thank you for explaining, it helped me a lot
$endgroup$
– hps13
Apr 22 at 15:37
$begingroup$
@DreamConspiracy Conceptually the DFA does needs to be stored. Remember that the inputs to our algorithm are a regular expression and an input - I'm not assuming that we get to do any pre-computation. The DFA would have to be generated during the runtime and stored in memory as well. But this generation time and memory requirement are both independent of the input (size), and thus $O(1)$. After we've reached that conclusion we could conclude we can pre-compute the DFA and don't have to store it explicitly, but the conclusion comes first, the optimization later.
$endgroup$
– orlp
Apr 22 at 18:48
|
show 1 more 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
Apr 22 at 12:59
4
$begingroup$
The NFA->DFA transformation doesn't even refer to the input (it's purely an operation on the language itself), so how could the input size matter?
$endgroup$
– jasonharper
Apr 22 at 13:16
1
$begingroup$
re: "storing it takes $O(1)$ space" this seems a little misleading. Since we're talking about Turing machines, the DFA doesn't have to get "stored" at all, but rather a DFA is a Turing machine that makes no use of the memory tape (since we're talking sublinear space we need separate input and memory tapes on the Turing Machine).
$endgroup$
– DreamConspiracy
Apr 22 at 15:04
$begingroup$
understood, thank you. @DreamConspiracy, would appreciate reading any additions you might have. @ jasonharper, thank you for explaining, it helped me a lot
$endgroup$
– hps13
Apr 22 at 15:37
$begingroup$
@DreamConspiracy Conceptually the DFA does needs to be stored. Remember that the inputs to our algorithm are a regular expression and an input - I'm not assuming that we get to do any pre-computation. The DFA would have to be generated during the runtime and stored in memory as well. But this generation time and memory requirement are both independent of the input (size), and thus $O(1)$. After we've reached that conclusion we could conclude we can pre-compute the DFA and don't have to store it explicitly, but the conclusion comes first, the optimization later.
$endgroup$
– orlp
Apr 22 at 18:48
$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
Apr 22 at 12:59
$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
Apr 22 at 12:59
4
4
$begingroup$
The NFA->DFA transformation doesn't even refer to the input (it's purely an operation on the language itself), so how could the input size matter?
$endgroup$
– jasonharper
Apr 22 at 13:16
$begingroup$
The NFA->DFA transformation doesn't even refer to the input (it's purely an operation on the language itself), so how could the input size matter?
$endgroup$
– jasonharper
Apr 22 at 13:16
1
1
$begingroup$
re: "storing it takes $O(1)$ space" this seems a little misleading. Since we're talking about Turing machines, the DFA doesn't have to get "stored" at all, but rather a DFA is a Turing machine that makes no use of the memory tape (since we're talking sublinear space we need separate input and memory tapes on the Turing Machine).
$endgroup$
– DreamConspiracy
Apr 22 at 15:04
$begingroup$
re: "storing it takes $O(1)$ space" this seems a little misleading. Since we're talking about Turing machines, the DFA doesn't have to get "stored" at all, but rather a DFA is a Turing machine that makes no use of the memory tape (since we're talking sublinear space we need separate input and memory tapes on the Turing Machine).
$endgroup$
– DreamConspiracy
Apr 22 at 15:04
$begingroup$
understood, thank you. @DreamConspiracy, would appreciate reading any additions you might have. @ jasonharper, thank you for explaining, it helped me a lot
$endgroup$
– hps13
Apr 22 at 15:37
$begingroup$
understood, thank you. @DreamConspiracy, would appreciate reading any additions you might have. @ jasonharper, thank you for explaining, it helped me a lot
$endgroup$
– hps13
Apr 22 at 15:37
$begingroup$
@DreamConspiracy Conceptually the DFA does needs to be stored. Remember that the inputs to our algorithm are a regular expression and an input - I'm not assuming that we get to do any pre-computation. The DFA would have to be generated during the runtime and stored in memory as well. But this generation time and memory requirement are both independent of the input (size), and thus $O(1)$. After we've reached that conclusion we could conclude we can pre-compute the DFA and don't have to store it explicitly, but the conclusion comes first, the optimization later.
$endgroup$
– orlp
Apr 22 at 18:48
$begingroup$
@DreamConspiracy Conceptually the DFA does needs to be stored. Remember that the inputs to our algorithm are a regular expression and an input - I'm not assuming that we get to do any pre-computation. The DFA would have to be generated during the runtime and stored in memory as well. But this generation time and memory requirement are both independent of the input (size), and thus $O(1)$. After we've reached that conclusion we could conclude we can pre-compute the DFA and don't have to store it explicitly, but the conclusion comes first, the optimization later.
$endgroup$
– orlp
Apr 22 at 18:48
|
show 1 more 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
