3
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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