# Is the word problem of CFLs in NC?

Consider the membership problem for a context-free language. An instance of this problem can be described as pair $(G,w)$, where $G$ is a context-free grammar and $w$ is a string.

Lets say I have a PRAM and I want it to decide in $\log^k n$ time and $n^c$ space complexity whether $w$ is in $L(G)$ ($c$ and $k$ are both constants) – that is, the complexity stays within Nick's class.

Is there such an algorithm? If so what would be an idea?

• Alright, so the exact task can be rewritten like this: Assume MEM problem, problem which has CF grammar $G$ and word $w$ on input and asks if $w \in L(G)$. Next assume problem EMP, which has CFL G on the input and asks if there is a word $w$ s.t. $w \in L(G)$. Proof that $MEM \leq_{NC} EMP$. I just assumed that reduction can be done via solving the $MEM$ problem (with PRAM) and then return NON-empty / empty grammar – Smarty77 May 22 '16 at 9:08

• Is this what the question's asking for? I interpret "$\mathrm{CFL}\subseteq\mathrm{NC}^2$" as meaning "every context-free language can be decided in $\mathrm{NC}^2$" but the question seems to be asking "Is the language $\{\langle G\rangle;w\mid G \text{ is a context-free grammar that generates }w\}$ in $\mathrm{NC}$?" – David Richerby May 21 '16 at 0:53