Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We know that $\mathsf{REG}=\mathsf{NSPACE}(O(1))$ and $\mathsf{CSL}=\mathsf{NSPACE}(O(n))$.

What is the relation of $\mathsf{CFL}$ and $\mathsf{NSPACE}(O(\log n))=\mathsf{NL}$?
Is $\mathsf{CFL}$ a proper subset of $\mathsf{NL}$?

Note that $\{0^k1^k2^k \mid 0 \leq k \}$ is not context-free, but in $\mathsf{NL}$.

share|cite|improve this question
I have found a 1977 paper (Log Space Recognition and Translation of Parenthesis Languages by Nancy Lynch) with states that this is an open problem (and that $\mathsf{CFL} \subset \mathsf{L}$ implies $\mathsf{L} = \mathsf{NL}$). Hopcroft and Ullman showed that $\mathsf{CFL} \subset \mathsf{DSPACE}(O(\log^2 n))$. – Max Dec 27 '12 at 13:00
Btw, the language you have is not just in $\mathsf{NL}$ but in $\mathsf{L}$. Generally grammar classes are not that interesting from complexity theory point of view because they are not closed. The more natural complexity class to study is $\mathsf{LogCFL}$ which contains $\mathsf{NL}$. – Kaveh Dec 27 '12 at 14:16
Does anybody know an NP-complete context-free language? – cineel Dec 29 '12 at 9:53
@cineel : CFL is in LOGCFL which is in AC1 which is in NC which is in P. So it is definitely disjoint with NPC (if you believe P is not NP) – Squark Dec 29 '12 at 13:20
@Squark I meant to write NL-complete, not NP. – cineel Jan 1 '13 at 5:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.