0
$\begingroup$

The unrestricted grammars characterize the recursively enumerable languages. This is the same as saying that for every unrestricted grammar G there exists some Turing machine capable of recognizing L(G) and vice versa.

Context: Grammars are Turing-complete. Therefore complexity classes like NL have equivalences in grammars.

One important NL-complete problem is ST-connectivity (or "Reachability") (Papadimitriou 1994 Thrm. 16.2), the problem of determining whether, given a directed graph G and two nodes s and t on that graph, there is a path from s to t. ST-connectivity can be seen to be in NL, because we start at the node s and nondeterministically walk to every other reachable node. ST-connectivity can be seen to be NL-hard by considering the computation state graph of any other NL algorithm, and considering that the other algorithm will accept if and only if there is a (nondetermistic) path from the starting state to an accepting state.

Given a directed graph, deciding if a->b is a directed path is NL-complete.

We will reduce the directed graph to a grammar rules with one symbol on each side:

For each directed edge in the graph, add a grammar rule. The directed edge a->b becomes the grammar rule a|b.

The NL-complete query becomes, "If I set a to the start symbol, can I derive symbol b using the grammar rules?"

Each grammar rule has one symbol on each side (i.e. a|b).

Therefore grammar rules with one symbol on each side is NL-complete.

Are grammars consisting only of rules with one symbol on each side NL-complete?

Related questions:

What complexity class does is this set of grammars? L-complete?

What complexity class does is this set of grammars? P-hard?

What complexity class does this correspond to?

Improve this question
$\endgroup$
4
  • $\begingroup$ Grammars can't be NL-complete. Languages can be. What language did you have in mind? $\endgroup$
    – D.W. ♦
    Commented Apr 18, 2020 at 23:47
  • $\begingroup$ @D.W. Turing machines can decide questions about Turing machines. Grammars recognize languages. Can grammars recognize grammars? Can grammars be formulated as a language? $\endgroup$
    – Jesus is Lord
    Commented Apr 19, 2020 at 0:09
  • $\begingroup$ @D.W. The "computational hierarchy" (not sure what to call it) of L, NL, P, NP, etc. "manifests" from studying Turing machines or logic/descriptive complexity. Since unrestricted grammars are Turing-complete, I was wondering how the "computational hierarchy" "manifests" with unrestricted grammars. This question attempts to "manifest" NL to unrestricted grammars. $\endgroup$
    – Jesus is Lord
    Commented Apr 19, 2020 at 0:15
  • $\begingroup$ @D.W. I suppose the "language" is the set of all grammars consisting of a start symbol (which would be a grammar rule), a target symbol (not a grammar rule; the start and target symbols correspond to the directed path we're querying for) and grammar rules with one symbol on each side (corresponding to directed edges) $\endgroup$
    – Jesus is Lord
    Commented Apr 19, 2020 at 0:22

1 Answer 1

Reset to default
1
$\begingroup$

Yes, you can build a reduction to show that the following problem is NL-complete:

Given a grammar where every rule has the form $X \to Y$ or $X \to a$ where $X,Y$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, determine whether $S$ can derive $a$.

This problem is equivalent to testing whether $a$ is reachable from $S$ in the corresponding directed graph, which is exactly the ST-connectivity problem.

I didn't understand what you meant by a|b.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks! I thought I had seen grammar rules written that way (a|b)! $\endgroup$
    – Jesus is Lord
    Commented Apr 19, 2020 at 13:07

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.