<p>Actually as several viewers agreed original grammar was incorrect. As @EmilJeřábek noticed, there was already discussion of this problem here: <a href="https://en.wikipedia.org/wiki/Talk:Context-sensitive_grammar#Wrong_grammar_for_language" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Talk:Context-sensitive_grammar#Wrong_grammar_for_language</a></p>

<p>So it appears that neither 7-rule grammar (which I was inquiring above in my question), neither 9-rule grammar which was here before and present in other-languages articles, both are incorrect. This 9-rule grammar:</p>

<blockquote>
  <ol>
  <li>S       →       a   B   C</li>
  <li>S   →   a   S   B   C</li>
  <li>C   B   →   W   B</li>
  <li>W   B   →   W   C</li>
  <li>W   C   →   B   C</li>
  <li>a   B   →   a   b</li>
  <li>b   B   →   b   b   </li>
  <li>b   C   →   b   c   </li>
  <li>c   C   →   c   c</li>
  </ol>
</blockquote>

<p>is incorrect example as it can produces words of the form "<code>aaa bb cccc</code>" `which doesn't fit formula $a^nb^nc^n$.</p>

<p>So I suggest following enhancement of this grammar by replacing rules 3-5 to four rules:</p>

<ol>
<li>S       →       a   B   C</li>
<li>S   →   a   S   B   C</li>
<li>C   B   →   C   Z</li>
<li>C   Z   →   W   Z   </li>
<li>W   Z   →   W   C   </li>
<li>W   C   →   B   C</li>
<li>a   B   →   a   b</li>
<li>b   B   →   b   b   </li>
<li>b   C   →   b   c   </li>
<li>c   C   →   c   c   </li>
</ol>

<p>Rules 3-6 will help avoid problem with replacing CB to WB and then WC to BC.</p>

<p><strike><strong>EDIT</strong>: As @EmilJeřábek suggested again, rules #7 and #8 can be simplified to one rule $B\rightarrow b$</strike>.</p>

CC BY-SA 3.0
2016-11-03T11:57:56.580Z
2016-11-04T23:25:31.567Z
2016-11-04T23:25:31.567Z
Andrey Lebedev
<p>If I am not mistaken, a simpler CS grammar is possible.  Here it 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>A derivation for the string $aaabbbccc$ is</p>

<p>$\Rightarrow_1 ABSc\\\Rightarrow_1 AB\textbf{ABSc}c\\\Rightarrow_2 ABAB\textbf{Abc}cc\\\Rightarrow_3 A\textbf{XA}BAbccc\\\Rightarrow_4 A\textbf{XY}BAbccc\\\Rightarrow_5 A\textbf{AY}BAbccc\\\Rightarrow_6 A\textbf{AB}BAbccc\\\dots\\\Rightarrow_{3-6}AAB\textbf{AB}bccc\\\Rightarrow_{3-6}AA\textbf{AB}Bbccc\\\Rightarrow_{7...}\textbf{aaa}BBbccc\\\Rightarrow_8 aaaB\textbf{bb}ccc\\\Rightarrow_8 aaa\textbf{bb}bccc$</p>

CC BY-SA 3.0
2016-11-06T08:50:08.557Z
2016-11-06T18:28:08.303Z
2016-11-06T18:28:08.303Z
Jeffrey Shallit
<p>I'm confused about the example given in Wikipedia article about Context-sensitive grammar:</p>

<p><a href="https://en.wikipedia.org/wiki/Context-sensitive_grammar" rel="noreferrer">https://en.wikipedia.org/wiki/Context-sensitive_grammar</a></p>

<p><strong>Disclamer</strong>: I've already changed discussed section in wikipedia article, so current state of article will differ from what I'm discussing in this question. Original version is here: <a href="https://en.wikipedia.org/w/index.php?title=Context-sensitive_grammar&amp;oldid=747616366" rel="noreferrer">https://en.wikipedia.org/w/index.php?title=Context-sensitive_grammar&amp;oldid=747616366</a></p>

<blockquote>
  <p>The following grammar, with start symbol S, generates the canonical
  non-context-free language { anbncn : n ≥ 1 } :</p>
  
  <ol>
  <li>S       →       a   b   c</li>
  <li>S   →   a   S   B   c</li>
  <li>c   B   →   W   B</li>
  <li>W   B   →   W   X</li>
  <li>W   X   →   B   X</li>
  <li>B   X   →   B   c</li>
  <li>b   B   →   b   b</li>
  </ol>
</blockquote>

<p>They do not claim directly that this grammar <strong>is</strong> <em>context-sensitive</em>, but next sentence implies that that they consider it as <em>context-sensitive</em>:</p>

<blockquote>
  <p>rules 3 to 6 allow for successively exchanging each cB to Bc (four
  rules are needed for that since a rule cB → Bc wouldn't fit into the
  scheme αAβ → αγβ)</p>
</blockquote>

<p>So they appeal to the canonical form of context-sensitive grammar rules: αAβ → αγβ, implying that whole grammar is context-sensitive. </p>

<p><strong>What I'm confused about is rule #3</strong>, which seems to be not fitting scheme αAβ → αγβ. I consider terminal $c$ here as part of $\alpha$, variable $B$ as $A$ in scheme, $\beta$ is empty. This implies that $cB$ can not produce $WB$, as $c$ should be saved on same place ($cB\rightarrow c\dots$).</p>

<p>Did I missed something or this grammar was really placed here mistakenly (as it is not real context-sensitive)?</p>

CC BY-SA 3.0
2016-11-03T10:43:39.633Z
I think you are right.
Emil Jeřábek
CC BY-SA 3.0
2016-11-03T11:15:31.110Z
@EmilJeřábek Looks like we made change in that section of wiki article at same time: I've introduced there proper version of grammar
Andrey Lebedev
CC BY-SA 3.0
2016-11-03T11:25:26.133Z
Unfortunately, your grammar is wrong. See https://en.wikipedia.org/wiki/Talk:Context-sensitive_grammar#Wrong_grammar_for_language .
Emil Jeřábek
CC BY-SA 3.0
2016-11-03T11:33:27.563Z
@EmilJeřábek I'm sorry, what's wrong with my grammar (9 rules grammar) which I've placed in new article version? Could you point what rule is wrong?
Andrey Lebedev
CC BY-SA 3.0
2016-11-03T11:36:03.853Z
@EmilJeřábek Ah, do you mean that this grammar can produce "aaa bb cccc" as well?
Andrey Lebedev
CC BY-SA 3.0
2016-11-03T11:45:09.277Z
Yes. Your grammar is in fact identical to the one discussed on the talk page up to renaming $H$ to $W$.
Emil Jeřábek
CC BY-SA 3.0
2016-11-03T11:46:00.177Z
@EmilJeřábek You are absolutely right. I even know from which paper this mistake arrived. Please look at my new edit, I've introduced additional rule which eliminates this problem.
Andrey Lebedev
<fl.formal-languages><grammars>
Mistake in Wikipedia CSG example?
Andrey Lebedev
# Mistake in Wikipedia CSG example?

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

I'm confused about the example given in Wikipedia article about Context-sensitive grammar:

<https://en.wikipedia.org/wiki/Context-sensitive_grammar>

**Disclamer**: I've already changed discussed section in wikipedia article, so current state of article will differ from what I'm discussing in this question. Original version is here: <https://en.wikipedia.org/w/index.php?title=Context-sensitive_grammar&oldid=747616366>

> The following grammar, with start symbol S, generates the canonical
> non-context-free language { anbncn : n ≥ 1 } :
>
> 1. S → a b c
> 2. S → a S B c
> 3. c B → W B
> 4. W B → W X
> 5. W X → B X
> 6. B X → B c
> 7. b B → b b

They do not claim directly that this grammar **is** *context-sensitive*, but next sentence implies that that they consider it as *context-sensitive*:

> rules 3 to 6 allow for successively exchanging each cB to Bc (four
> rules are needed for that since a rule cB → Bc wouldn't fit into the
> scheme αAβ → αγβ)

So they appeal to the canonical form of context-sensitive grammar rules: αAβ → αγβ, implying that whole grammar is context-sensitive.

**What I'm confused about is rule #3**, which seems to be not fitting scheme αAβ → αγβ. I consider terminal $c$ here as part of $\alpha$, variable $B$ as $A$ in scheme, $\beta$ is empty. This implies that $cB$ can not produce $WB$, as $c$ should be saved on same place ($cB\rightarrow c\dots$).

Did I missed something or this grammar was really placed here mistakenly (as it is not real context-sensitive)?

**Tags:** fl.formal-languages, grammars
> **Comments:**
> **username_1**: I think you are right.  
> **username_0**: @EmilJeřábek Looks like we made change in that section of wiki article at same time: I've introduced there proper version of grammar  
> **username_1**: Unfortunately, your grammar is wrong. See https://en.wikipedia.org/wiki/Talk:Context-sensitive_grammar#Wrong_grammar_for_language .  
> **username_0**: @EmilJeřábek I'm sorry, what's wrong with my grammar (9 rules grammar) which I've placed in new article version? Could you point what rule is wrong?  
> **username_0**: @EmilJeřábek Ah, do you mean that this grammar can produce "aaa bb cccc" as well?  
> **username_1**: Yes. Your grammar is in fact identical to the one discussed on the talk page up to renaming $H$ to $W$.  
> **username_0**: @EmilJeřábek You are absolutely right. I even know from which paper this mistake arrived. Please look at my new edit, I've introduced additional rule which eliminates this problem.  

---

## 2 answers

### Answer by username_2 on 2016-11-06. Score: 9 | Accepted answer

If I am not mistaken, a simpler CS grammar is possible. Here it 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$.

A derivation for the string $aaabbbccc$ is

$\Rightarrow\_1 ABSc\\\Rightarrow\_1 AB\textbf{ABSc}c\\\Rightarrow\_2 ABAB\textbf{Abc}cc\\\Rightarrow\_3 A\textbf{XA}BAbccc\\\Rightarrow\_4 A\textbf{XY}BAbccc\\\Rightarrow\_5 A\textbf{AY}BAbccc\\\Rightarrow\_6 A\textbf{AB}BAbccc\\\dots\\\Rightarrow\_{3-6}AAB\textbf{AB}bccc\\\Rightarrow\_{3-6}AA\textbf{AB}Bbccc\\\Rightarrow\_{7...}\textbf{aaa}BBbccc\\\Rightarrow\_8 aaaB\textbf{bb}ccc\\\Rightarrow\_8 aaa\textbf{bb}bccc$


---

### Answer by username_0 on 2016-11-03. Score: 3

Actually as several viewers agreed original grammar was incorrect. As @EmilJeřábek noticed, there was already discussion of this problem here: <https://en.wikipedia.org/wiki/Talk:Context-sensitive_grammar#Wrong_grammar_for_language>

So it appears that neither 7-rule grammar (which I was inquiring above in my question), neither 9-rule grammar which was here before and present in other-languages articles, both are incorrect. This 9-rule grammar:

> 1. S → a B C
> 2. S → a S B C
> 3. C B → W B
> 4. W B → W C
> 5. W C → B C
> 6. a B → a b
> 7. b B → b b
> 8. b C → b c
> 9. c C → c c

is incorrect example as it can produces words of the form "`aaa bb cccc`" `which doesn't fit formula $a^nb^nc^n$.

So I suggest following enhancement of this grammar by replacing rules 3-5 to four rules:

1. S → a B C
2. S → a S B C
3. C B → C Z
4. C Z → W Z
5. W Z → W C
6. W C → B C
7. a B → a b
8. b B → b b
9. b C → b c
10. c C → c c

Rules 3-6 will help avoid problem with replacing CB to WB and then WC to BC.

**EDIT**: As @EmilJeřábek suggested again, rules #7 and #8 can be simplified to one rule $B\rightarrow b$.


---

