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?