This question is inspired by the great answer given by Jeffrey Shallit on my question about proper CSG for $a^n b^n c^n$ language.

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

  1. $S \rightarrow ABSc$
  2. $S \rightarrow Abc$
  3. $BA \rightarrow XA$
  4. $XA \rightarrow XY$
  5. $XY \rightarrow AY$
  6. $AY \rightarrow AB$
  7. $A \rightarrow a$
  8. $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?

  • $\begingroup$ The "complexity of full language generation process" is probably not an easy concept to define, since for any infinite language this is an infinte process. Probably you are better off only arguing with the parsing complexity. $\endgroup$ Commented Nov 8, 2016 at 12:48
  • $\begingroup$ @PeterLeupold I'm not arguing about correctness of this grammar (if it isn't clear from my question, please, tell me - I will make emphasise on it). I'm asking exactly about this point - about difference in complexity of parsing. $\endgroup$ Commented Nov 8, 2016 at 12:50


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.