Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  Mariano Suárez-Alvarez Sep 12 '12 at 19:39
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.