Do regular languages belong to Space(1)? Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?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)$?
Dinosaur Word Search, Letter Solve, and Unscramble
Do British people often use the word lightning conductor?
Can two people see the same photon?
Magento 2 Editing phtml files in Production Mode
How do you cope with tons of web fonts when copying and pasting from web pages?
No invitation for tourist visa but I want to visit
Why is there so little support for joining EFTA in the British parliament?
How to achieve cat-like agility?
Why do C and C++ allow the expression (int) + 4*5?
Should man-made satellites feature an intelligent inverted "cow catcher"?
Who's the Giant Batman in the back of this dark knights metal Batman picture?
Why are two-digit numbers in Jonathan Swift's "Gulliver's Travels" (1726) written in "German style"?
How do I say "this must not happen"?
Why did Bronn offer to be Tyrion Lannister's champion in trial by combat?
Why does BitLocker not use RSA?
Found this skink in my tomato plant bucket. Is he trapped? Or could he leave if he wanted?
Is it possible to intall libXft.so.2 on WSL?
What's the connection between Mr. Nancy and fried chicken?
Alternative of "Rest In Peace" (RIP)
Combining list in a Cartesian product format with addition operation?
Can I take recommendation from someone I met at a conference?
Proving that any solution to the differential equation of an oscillator can be written as a sum of sinusoids.
What could prevent concentrated local exploration?
How can I prevent/balance waiting and turtling as a response to cooldown mechanics
Do regular languages belong to Space(1)?
Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)
Announcing the arrival of Valued Associate #679: Cesar Manara
Unicorn Meta Zoo #1: Why another podcast?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 40 mins ago
Yuval Filmus
197k15186350
asked 1 hour 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 40 mins ago
Yuval Filmus
197k15186350
asked 1 hour 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 40 mins ago
Yuval Filmus
197k15186350
asked 1 hour 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 40 mins ago
Yuval Filmus
197k15186350
asked 1 hour ago
hps13hps13
276
edited 40 mins ago
Yuval Filmus
197k15186350
asked 1 hour ago
hps13hps13
276
edited 40 mins ago
Yuval Filmus
197k15186350
edited 40 mins ago
Yuval Filmus
197k15186350
edited 40 mins ago
Yuval Filmus
197k15186350
197k15186350
asked 1 hour ago
hps13hps13
276
asked 1 hour ago
hps13hps13
276
asked 1 hour 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 42 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
29 mins ago
$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
13 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 42 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
29 mins ago
$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
13 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 42 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
29 mins ago
$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
13 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 42 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 42 mins ago
orlporlp
6,0451826
answered 42 mins ago
orlporlp
6,0451826
answered 42 mins ago
orlporlp
6,0451826
answered 42 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
29 mins ago
$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
13 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
29 mins ago
$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
13 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
29 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
29 mins ago
$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
13 mins ago
$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
13 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
