Is this language context-sensitive?

Question

I want to make a grammar for the language consisting of all strings of $a, b$ and $c$ (including $\epsilon$) such that the number of $a$'s, $b$'s and $c$'s is equal.

The idea is to use nonterminals $A,B$ and $C$ and permute them in every way and in between them we should be able to put more strings with equal number of $a$'s, $b$'s and $c$'s. So the grammar would be \begin{align*} S &\rightarrow ASBSC\; | \; BSASC\; |\; ASCSB \; |\; CSBSA\; |\; CSASB\; |\; BSCSA\; | \; \epsilon\\ A &\rightarrow a\\ B &\rightarrow b\\ C &\rightarrow c \end{align*}

Is this grammar context-sensitive?

The grammar being context-free should be a hint that something is wrong, since the language isn't. In fact, it cannot generate the word aabbcc which is in the target language. — Klaus Draeger, Dec 18 '23 at 14:43

score 1 · Answer 1 · answered Dec 18 '23 at 11:58

1

No I don't think so. In a context-sensitive grammar the right-hand side of a rule must never be shorter than the left-hand side. In your proposed grammar, the production rule $S → ε$ violates this condition because the right-hand side ε is shorter than the left-hand side S.

Notably, the production rule S -> ε is valid in a context-free grammar. This rule indicates that the non-terminal S can be replaced by the empty string, which is allowed in a context-free grammar.

in fact its a context-free.

answered Dec 18 '23 at 11:58

Amirreza Hashemi

560

Ir is not true that in a context-sensitive grammar the right-hand side of a rule may not be shorter than the left-hand side. The grammar presented by the OP is obviously context-free because each rule has a single non-terminal symbol on its right hand side. – Rob Arthan Dec 18 '23 at 23:42
But how am I supposed to get $\epsilon$ elseway, because it should be in my language? – likeAvirgin Dec 20 '23 at 09:27

Is this language context-sensitive?

1 Answers1