What complexity class does is this set of grammars? NL-complete?
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.