# What kind of Grammar could this be

I am trying to sort Grammar into the Chomsky Hierarchy and I can do so for most of my examples but I am stumped by the following one:

bX -> abY

which Type of Grammar would this be, unrestricted grammar, context-sensitive grammar context-free grammar or regular grammar

• Have you read the definitions of all the grammars types? What difficulties did you face checking if your grammar satisfies context-sensitive grammar definition? – Vladislav Mar 30 at 12:13

$$\alpha A \beta \to \alpha \gamma \beta$$ where $$A \in N, \alpha,\beta,\gamma\in (\Sigma\cup N)^* \text{ and } |\gamma| \ge 1$$.
Assuming $$\Sigma=\{a,b\}$$ and $$N=\{X,Y\}$$, the production $$bX\to abY$$ does not satisfy this criterion. The only possible decomposition of the left-hand side is $$\alpha=b,\beta=\epsilon$$, and that doesn't match the right-hand side. So it's not a context-sensitive grammar.
However, that doesn't stop the language generated by that production from being context-sensitive. There is an alternative characterisation of grammars (which is, in fact, often used instead of Chomsky's original context-sensitive criterion), which are the non-contracting grammars. A non-contracting grammar consists only of productions of the form $$\alpha\to\beta$$ where $$\alpha,\beta\in(\Sigma\cup N)^+\text{ and }|\alpha|\le|\beta|$$. These grammars are weakly equivalent to context-sensitive grammars; in other words, for any context-sensitive grammar, there exists at least one non-contracting grammar which generates the same language, and vice versa. (This is a weak equivalence because the grammars don't produce the same derivations.) Furthermore, there is a mechanical procedure which can convert a non-contracting grammar into a context-sensitive grammar.