I'm confused about the example given in Wikipedia article about 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)?

  • 1
    $\begingroup$ I think you are right. $\endgroup$ – Emil Jeřábek Nov 3 '16 at 10:43
  • $\begingroup$ @EmilJeřábek Looks like we made change in that section of wiki article at same time: I've introduced there proper version of grammar $\endgroup$ – Andrey Lebedev Nov 3 '16 at 11:15
  • $\begingroup$ Unfortunately, your grammar is wrong. See en.wikipedia.org/wiki/… . $\endgroup$ – Emil Jeřábek Nov 3 '16 at 11:25
  • $\begingroup$ @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? $\endgroup$ – Andrey Lebedev Nov 3 '16 at 11:33
  • $\begingroup$ @EmilJeřábek Ah, do you mean that this grammar can produce "aaa bb cccc" as well? $\endgroup$ – Andrey Lebedev Nov 3 '16 at 11:36

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$

| cite | improve this answer | |

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$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.