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

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?

• Grammars can't be NL-complete. Languages can be. What language did you have in mind? – D.W. Apr 18 '20 at 23:47
• @D.W. Turing machines can decide questions about Turing machines. Grammars recognize languages. Can grammars recognize grammars? Can grammars be formulated as a language? – Jesus is Lord Apr 19 '20 at 0:09
• @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. – Jesus is Lord Apr 19 '20 at 0:15
• @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) – Jesus is Lord Apr 19 '20 at 0:22

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.
• Thanks! I thought I had seen grammar rules written that way (a|b)! – Jesus is Lord Apr 19 '20 at 13:07