# What is a good example of an NL-complete context free language?

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

Problem

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

• You are not likely to get an example, perhaps this post can explain why. – Shaull May 1 '15 at 20:09
• would empty DFA be a candidate? – chibro2 May 1 '15 at 21:04
• 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. – D.W. May 1 '15 at 21:08
• @D.W. I provided a solution, it seems too good to be true though ... – chibro2 May 1 '15 at 22:09
• 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. – Yuval Filmus May 1 '15 at 22:59

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