The unrestricted grammars characterize the recursively enumerable languages. This is the same as saying that for every unrestricted grammar
Gthere 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
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.
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?