1
$\begingroup$

I want to know if I have the following rule

$AB \to BA$.

Is it context sensitive?

Another rule $A \to aAB$

Is it context sensitive as well.

I think both of them are not context sensitive. Any insights or guidance?

  • 1
    Giving (or pointing to) the precise definition of *context sensitive grammar* you are using might be useful to answer this in a way useful to you.2012-09-12

1 Answers 1

3

There are several different definitions of context-sensitive grammar, so the answer depends on the exact definition that you’re using. The production $A\to aAB$ is allowed in a context-sensitive grammar under any of the definitions that I’ve seen; it’s even context-free. The production $AB\to BA$ is another matter. If your definition allows arbitrary productions of the form $\alpha\to\beta$ provided only that $|\alpha|\le|\beta|$, then of course $AB\to BA$ is allowed. If your definition requires the productions to be of the form $\alpha X\beta\to\alpha\gamma\beta$, where $X$ is a non-terminal, then $AB\to BA$ is not allowed: either $\alpha$ would have to be $A$, or $\beta$ would have to be $B$, and in neither case does the righthand side have the right form. Note that the effect of the production $AB\to BA$ can be produced by productions of the type $\alpha X\beta\to\alpha\gamma\beta$: just add a new non-terminal symbol $X$ and the productions $AB\to AX$, $AX\to BX$, and $BX\to BA$. Thus, allowing $AB\to BA$ doesn’t change the languages that can be generated. But as I said, it doesn’t actually fit some definitions of context-sensitive grammar.