# Do regular languages belong to Space(1)?

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

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.
• 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). – DreamConspiracy Apr 22 at 15:04
• @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. – orlp Apr 22 at 18:48