Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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
Thank you for your help
The definition of context-sensitive grammar requires that every production be of the form
$$\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.
The production you ask about is certainly non-contracting, so (unless other productions in the grammar are contracting) the language is context-sensitive.
If this question appears on a test or class assignment, you should verify which definition of "context-sensitive grammar" your professor uses. Because of they generate exactly the same languages, and because non-contracting grammars are often easier to write, some people use the non-contracting criterion as a definition of "context-free grammar".
