Mrthdrb

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)$?

2

$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

share|cite|improve this question

edited Apr 22 at 12:48

Yuval Filmus

197k15187350

asked Apr 22 at 12:12

hps13hps13

346

$endgroup$

add a comment | 

2

$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

share|cite|improve this question

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

share|cite|improve this question

edited Apr 22 at 12:48

Yuval Filmus

197k15187350

asked Apr 22 at 12:12

hps13hps13

346

$endgroup$

share|cite|improve this question

edited Apr 22 at 12:48

Yuval Filmus

197k15187350

asked Apr 22 at 12:12

hps13hps13

346

share|cite|improve this question

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

asked Apr 22 at 12:12

hps13hps13

346

asked Apr 22 at 12:12

hps13hps13

346

1 Answer
1

active

oldest

votes

4

$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.

share|cite|improve this answer

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
);



);

draft saved

draft discarded

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

Name

Email

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

Name

Email

Required, but never shown

4

$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.

share|cite|improve this answer

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

4

$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.

share|cite|improve this answer

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.

share|cite|improve this answer

answered Apr 22 at 12:47

orlporlp

6,4851927

$endgroup$

share|cite|improve this answer

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