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

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

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

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