# Is CFL strictly contained in NL?

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}$.

• 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
• @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) – Vanessa Dec 29 '12 at 13:20
• @Squark I meant to write NL-complete, not NP. – cineel Jan 1 '13 at 5:39
• Also, what about deterministic logspace? – Ryan May 1 '15 at 23:14