Is this language context-sensitive?

44 Views Asked by At

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?

1

There are 1 best solutions below

2
On

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.