1
$\begingroup$

I know all the regular languages are decidable but not sure whether it can be done in LogSpace.

$\endgroup$
3
$\begingroup$

It is unknown whether context-free languages can be decided in logarithmic space. The best known result shows that they can be decided in nondeterministic space $O(\log^2 n)$. It is also known that if all context-free languages can be decided in deterministic logarithmic space then $\mathsf{L} = \mathsf{NL}$, which is considered unlikely.

For references, see this question and this question on cstheory.

$\endgroup$
3
$\begingroup$

For regular languages, we have $$ \text{REG = DSPACE}(O(1)) = \text{NSPACE}(O(1))$$ where REG is the class of regular languages. This can be easily seen from the equivalent formalisms of regular languages. A language is a regular language iff it is the language accepted by a deterministic finite automaton. A language is a regular language iff it is the language accepted by a nondeterministic finite automaton.

In fact, $\text{REG = DSPACE}(o(\log \log n))$. That is, $Ω(\log\log n)$ space is required to recognize any non-regular language [1].

For context-free languages, please see the answer by Yuval Filmus.

$\endgroup$
  • $\begingroup$ Is it same for context free language? $\endgroup$ – user730119 Sep 6 '18 at 14:05
  • $\begingroup$ No. If a language can be decided using constant space, then we can use a deterministic finite automaton to recognize the strings in that language. $\endgroup$ – Apass.Jack Sep 6 '18 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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