Disclaimer:: I'm not arguing about correctness of this grammar. This grammar is absolutely correct. My question is about classification.
In his version of grammar which is
- $S \rightarrow ABSc$
- $S \rightarrow Abc$
- $BA \rightarrow XA$
- $XA \rightarrow XY$
- $XY \rightarrow AY$
- $AY \rightarrow AB$
- $A \rightarrow a$
- $Bb \rightarrow bb$,
there is possibility of "dead" derivations which doesn't give us a string, e.g.: $\Rightarrow_1 ABSc\Rightarrow_2 ABAbcc\Rightarrow_7 ABabcc\Rightarrow_7aBabcc\Rightarrow_? ?$.
I know that it doesn't prevent grammar to generate proper language $a^n b^n c^n$.
What I'm troubling about is classification of such kind of grammars. Because there is obvious difference between weakly equivalent grammars (which produce same language), where one of them contains such kind of "dead end" derivations, and another one doesn't (see my 10-ruled version of this grammar).
I thought that this difference should be classified somehow, because at least it influences on complexity of full language generation process or on brute-force parsing process (generators which deal with "dead" generation chains have to make more backtracking steps or produce more parallel derivations). For instance, JFLAP tool produces string $aaabbbccc$ using 20 levels and 792 nodes on Jeffrey Shallit's 8-ruled grammar, and using 16 levels and 194 nodes for my 10-rules case. But I didn't find any kind of such classification.
It possibly could be relation to the efficiency of constructed linear-bounded automaton using algorithm given by Kuroda, but I'm still wondering are any known classification for such cases?