<p>This question is inspired by the great <a href="https://cstheory.stackexchange.com/a/36931/29116">answer</a> given by Jeffrey Shallit on my <a href="https://cstheory.stackexchange.com/questions/36907/mistake-in-wikipedia-csg-example">question</a> about proper CSG for $a^n b^n c^n$ language.</p>

<p><strong>Disclaimer:</strong>: I'm <strong>not</strong> arguing about correctness of this grammar. <strong>This grammar is absolutely correct</strong>. My question is about classification.</p>

<p>In his version of grammar which is</p>

<ol>
<li>$S \rightarrow ABSc$</li>
<li>$S \rightarrow Abc$</li>
<li>$BA \rightarrow XA$</li>
<li>$XA \rightarrow XY$</li>
<li>$XY \rightarrow AY$</li>
<li>$AY \rightarrow AB$</li>
<li>$A \rightarrow a$</li>
<li>$Bb \rightarrow bb$,</li>
</ol>

<p>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_? ?$.</p>

<p>I know that it <strong>doesn't</strong> prevent grammar to generate proper language $a^n b^n c^n$.</p>

<p>What I'm troubling about is <strong><em>classification</em></strong> 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 <a href="https://cstheory.stackexchange.com/a/36909/29116">10-ruled version of this grammar</a>).  </p>

<p>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. </p>

<p>It possibly could be relation to the efficiency of constructed linear-bounded automaton using <a href="http://www.sciencedirect.com/science/article/pii/S0019995864901202" rel="nofollow noreferrer">algorithm given by Kuroda</a>, but I'm still wondering are any known classification for such cases? </p>

CC BY-SA 3.0
2016-11-08T12:48:22.177Z
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.
Peter Leupold
CC BY-SA 3.0
2016-11-08T12:50:32.880Z
@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.
Andrey Lebedev
<fl.formal-languages><grammars>
Grammar with "dead" derivation chains
Andrey Lebedev
# Grammar with "dead" derivation chains

(Asked by: username_0 on 2016-11-06)

This question is inspired by the great [answer](https://cstheory.stackexchange.com/a/36931/29116) given by Jeffrey Shallit on my [question](https://cstheory.stackexchange.com/questions/36907/mistake-in-wikipedia-csg-example) 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](https://cstheory.stackexchange.com/a/36909/29116)).

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](http://www.sciencedirect.com/science/article/pii/S0019995864901202), but I'm still wondering are any known classification for such cases?

**Tags:** fl.formal-languages, grammars
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  

---

## 0 answers

