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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.