# 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.
Commented Apr 18, 2020 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? Commented Apr 19, 2020 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. Commented Apr 19, 2020 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) Commented Apr 19, 2020 at 0:22

## 1 Answer

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.

• Thanks! I thought I had seen grammar rules written that way (a|b)! Commented Apr 19, 2020 at 13:07