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