Setting Exactly as the title stated:

Give an example of an $\mathsf{NL}$-complete context free language. $\newcommand{\angle}[1]{\langle #1 \rangle}$

Current Solution

Recall in the past we proved that $E_{DFA}$ is regular, so it is also context free. $E_{DFA}$ is in $\mathsf{NL}$ since given DFA $\mathcal M$ over $n$ states, we can start at the initial state and nondeterminstically traverse through states of $\mathcal M$ for at most $n$ steps, storing only the current state ($\log n$ space). Note if there is a path to an accept state, then it must be $\le n$ steps long. So if there is no path to an accept state within $n$ steps, then $\mathcal M$ does not accept any string, thus $\mathcal M \in E_{DFA}$.

Now we show $\overline{PATH} \le_l E_{DFA}$ and since $PATH$ is $\mathsf{NL}$-complete and $\mathsf{NL} = \mathsf{coNL}$, it follows that $E_{DFA}$ is also $\mathsf{NL}$-complete. Given an instance $\angle{G,s,t}$, we construct a DFA $\mathcal M$ by letting $s \in G$ be $q_{initial}$, and $t \in G$ be $q_{accept}$. We label the edge arbitrarily from $\{0,1\}$. Clearly this can be done in log-space. So now we show $$\angle{G,s,t} \in \overline{PATH} \Leftrightarrow \mathcal M \in E_{DFA}.$$

Suppose $\angle{G,s,t} \in \overline{PATH}$, then there is no path from $s$ to $t$, so there is no path from $q_{initial}$ to $q_{accept}$ in $\mathcal M$, then $\mathcal M$ does not accept any strings so it is in $E_{DFA}$. Conversely, suppose $\angle{G,s,t} \not\in E_{DFA}$, then there is a path from $s$ to $t$, taking this path in $\mathcal M$ correspond to a $\mathcal M$ accepting some string, so $\mathcal L(\mathcal M) \ne \emptyset$ and $\mathcal M \not\in E_{DFA}$.


I don't think my algorithm for proving $E_{DFA} \in \mathsf{NL}$ is correct.

  • 2
    $\begingroup$ You are not likely to get an example, perhaps this post can explain why. $\endgroup$
    – Shaull
    Commented May 1, 2015 at 20:09
  • $\begingroup$ would empty DFA be a candidate? $\endgroup$
    – chibro2
    Commented May 1, 2015 at 21:04
  • $\begingroup$ What research/self-study have you done? Where have you looked? We expect you to do a significant amount of research and self-study before asking and to tell us in the question what you've tried / where you've looked / what you do and don't understand. See cs.stackexchange.com/help/dont-ask. I encourage you to edit your question to flesh it out a bit more. $\endgroup$
    – D.W.
    Commented May 1, 2015 at 21:08
  • $\begingroup$ @D.W. I provided a solution, it seems too good to be true though ... $\endgroup$
    – chibro2
    Commented May 1, 2015 at 22:09
  • 3
    $\begingroup$ Can you define $E_{DFA}$? I understand that it is the language of DFAs accepting the empty language, but you have to explain how these DFAs are encoded. I can't think of any reasonable encoding for which this language would be regular, or even context free. $\endgroup$ Commented May 1, 2015 at 22:59

1 Answer 1


In other words, you are asked to find an $\rm NL$-complete language $A$ and a context-free language $B$ such that $A \equiv_{\rm{L}} B$. We choose $A = \it{PATH}$ and $\{{\tt{0}, \tt{1}, \tt{\#}}\}^* \supseteq B = f(A)$, in which $f: A \to B$ is defined as follows. $$ \newcommand{\Bra}[1]{\langle #1 \rangle} f(\Bra{G, s, t}) = \Bra{s}^{\mathcal{R}}({\tt{\#}} \Bra{e_1} \Bra{e_2} \cdots \Bra{e_m} {\tt{\#}} )^n\Bra{t}, $$ where $G = (V, E)$, $|V| = n$, $E = \{e_1, \dots, e_m\}$, $\Bra{e_i} = {\tt{\#}}\Bra{u_i}{\tt{\#}}\Bra{v_i}^{\mathcal{R}{}}{\tt{\#}}$ if $e_i = (u_i, v_i)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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