Gdtyjr

Why not use the yoke to control yaw, as well as pitch and roll?

Is there a verb for listening stealthily?

If something is halfway in a bag of holding... what happens to it?

Pointing to problems without suggesting solutions

Bash script to execute command with file from directory and condition

Can I cut the hair of a conjured korred with a blade made of precious material to harvest that material from the korred?

Table formatting with tabularx?

Which types of prepositional phrase is "toward its employees" in Philosophy guiding the organization's policies towards its employees is not bad?

How to ask rejected full-time candidates to apply to teach individual courses?

How to show a density matrix is in a pure/mixed state?

Improvising over quartal voicings

Is a copyright notice with a non-existent name be invalid?

As a dual citizen, my US passport will expire one day after traveling to the US. Will this work?

Magento 2 Editing phtml files in Production Mode

How to achieve cat-like agility?

How do you cope with tons of web fonts when copying and pasting from web pages?

draw a pulley system

Magento 2 - Add additional attributes in register

Changing order of draw operation in PGFPlots

Proving that any solution to the differential equation of an oscillator can be written as a sum of sinusoids.

Who's the Giant Batman in the back of this dark knights metal Batman picture?

Question on Gÿongy' lemma proof

Combining list in a Cartesian product format with addition operation?

Should man-made satellites feature an intelligent inverted "cow catcher"?

Do regular languages belong to Space(1)?

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

share|cite|improve this question

edited 39 mins ago

Yuval Filmus

197k15186350

asked 1 hour ago

hps13hps13

276

$endgroup$

add a comment | 

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

share|cite|improve this question

edited 39 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

share|cite|improve this question

edited 39 mins ago

Yuval Filmus

197k15186350

asked 1 hour ago

hps13hps13

276

$endgroup$

share|cite|improve this question

edited 39 mins ago

Yuval Filmus

197k15186350

asked 1 hour ago

hps13hps13

276

share|cite|improve this question

edited 39 mins ago

Yuval Filmus

197k15186350

asked 1 hour ago

hps13hps13

276

edited 39 mins ago

Yuval Filmus

197k15186350

edited 39 mins ago

Yuval Filmus

197k15186350

asked 1 hour ago

hps13hps13

276

asked 1 hour ago

hps13hps13

276

1 Answer
1

active

oldest

votes

2

$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 40 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
  27 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
  11 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
);



);

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

2

$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 40 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
  27 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
  11 mins ago
  

  
  
  
  

add a comment | 

2

$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 40 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
  27 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
  11 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.

share|cite|improve this answer

answered 40 mins ago

orlporlp

6,0451826

$endgroup$

share|cite|improve this answer

answered 40 mins ago

orlporlp

6,0451826

answered 40 mins ago

orlporlp

6,0451826

answered 40 mins ago

orlporlp

6,0451826