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)$?
Unicode symbols with XeLaTeX and Lato font
Can stored/leased 737s be used to substitute for grounded MAXs?
Can I take recommendation from someone I met at a conference?
Does GDPR cover the collection of data by websites that crawl the web and resell user data
My mentor says to set image to Fine instead of RAW — how is this different from JPG?
Who's this lady in the war room?
Changing order of draw operation in PGFPlots
Can two people see the same photon?
How to create a button that adds InputFields when clicked?
How to name indistinguishable henchmen in a screenplay?
Should man-made satellites feature an intelligent inverted "cow catcher"?
Magento 2 - Add additional attributes in register
Found this skink in my tomato plant bucket. Is he trapped? Or could he leave if he wanted?
3D Masyu - A Die
Why is there so little support for joining EFTA in the British parliament?
Where did Ptolemy compare the Earth to the distance of fixed stars?
Does the main washing effect of soap come from foam?
How to achieve cat-like agility?
The Nth Gryphon Number
Fit odd number of triplets in a measure?
Flight departed from the gate 5 min before scheduled departure time. Refund options
calculator's angle answer for trig ratios that can work in more than 1 quadrant on the unit circle
What helicopter has the most rotor blades?
Is it possible to intall libXft.so.2 on WSL?
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 17 mins ago
Yuval Filmus
197k15186350
asked 54 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 17 mins ago
Yuval Filmus
197k15186350
asked 54 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 17 mins ago
Yuval Filmus
197k15186350
asked 54 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 17 mins ago
Yuval Filmus
197k15186350
asked 54 mins ago
hps13hps13
276
edited 17 mins ago
Yuval Filmus
197k15186350
asked 54 mins ago
hps13hps13
276
edited 17 mins ago
Yuval Filmus
197k15186350
edited 17 mins ago
Yuval Filmus
197k15186350
edited 17 mins ago
Yuval Filmus
197k15186350
197k15186350
asked 54 mins ago
hps13hps13
276
asked 54 mins ago
hps13hps13
276
asked 54 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 19 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
6 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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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 19 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
6 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 19 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
6 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 19 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 19 mins ago
orlporlp
6,0451826
answered 19 mins ago
orlporlp
6,0451826
answered 19 mins ago
orlporlp
6,0451826
answered 19 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
6 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
6 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
6 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
6 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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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
