# Why isn't every monotonic grammar context sensitive free?

The question is really confusing me. I know every context sensitive grammar is monotonic but not vice versa. e.g. AB--->BA is monotonic but not context sensitive. Can someone explain to me in simple terms why this is?

• I think you mean 'monotonous' to be 'monotonic'? – AndrewK Jan 10 '14 at 0:38
• What have you tried? Can you be any more specific about what you are confused about? Do you understand why $AB \to BA$ is not a context-sensitive grammar? Do you understand the definition of a context-sensitive grammar? Have you tried mechanically plugging into the definition to see that example grammar satisfies the definition? Which definition are you using? As it stands it looks like this question is trivial if you understand the definition of context-sensitive grammars, so I'm not clear on where you are confused. – D.W. Jan 10 '14 at 1:08
• @AndrewK Or perhaps 'monotone'? – Yuval Filmus Jan 10 '14 at 9:15
• I went ahead and made the edit. I can find only one source for "monotonous grammars", which was a textbook whose authors' names suggest they are not native speakers of English. I'm pretty sure they were making the same mistake. For the OP, "monotonous" means "boring"; "monotonic" or "monotone" means various things in mathematics: e.g., a monotone function is one where making the input bigger makes the output bigger, too. – David Richerby Jan 10 '14 at 15:19
• @YuvalFilmus I've heard that a few times, but I like 'monotonic' better, as it's not already a commonly used Standard English word. – AndrewK Jan 10 '14 at 21:41

## 3 Answers

If you're asking why the grammar with the rule $AB \to BA$ is not context-sensitive, you can find an explanation here.

The short answer is that it depends on the definition, but with one standard definition, the rule $AB \to BA$ simply doesn't satisfy the criterion for a rule to be allowable in a context-sensitive grammar.

When you use the classic definition, context-sensitive grammars may inspect the context of a non-terminal and use it to select the correct rule (cf context-free grammars), but they may not change it. Thus, rules like

$\qquad\displaystyle ab\mathbf{S}cD \to ab\mathbf{dca}cD$

are allowed, but like

$\qquad\displaystyle abScA \to edcBba$

are not. Note that a grammar made up of rules like this last one is monotone.

There are other definitions that characterise the same set of languages (not grammars, obviously); some are exactly that of monotone grammars (you have to allow $S \to \varepsilon$, though). See e.g. here.

In simple terms? I'm assuming you've had enough definitions and want an intuitive understanding, so I'll orient my answer in that direction.

Monotic grammars are much like monotonic functions in that they never decrease. That is, the length of your string after the rule is applied is always greater than or equal to what it was before.

So, in the case of $AB \implies BA$, when the rule is applied, the length of the string is exactly the same; you're simply interchanging two parts. Therefore it can't decrease, therefore it is monotonic.

Context-sensitive grammars were introduced by Chomsky in an attempt to describe natural languages (such as English). Context-sensitive means that meaning is dependent on a term's environment. Homonyms are a great example of this:

• "Bow towards starboard if you can see it." Bow is an imperative verb.
• "If you can see it towards starboard bow." Bow is a subject noun.

An example of a context-sensitive grammar rule is $aAb \implies aBb$, because it says that you can transform an $A$ into a $B$, but only if it is between an $a$ and a $b$.

You might think that $$S \implies AB$$ $$AB \implies BA$$ is context-sensitive because $A$ needs to be next to $B$, but look; you can make a substitution to rewrite that grammar as: $$S \implies AB\ |\ BA$$ Which is clearly context-free. In fact, it's almost Chomsky Normal Form. As to whether that means the original is actually context-free or not, that kind of depends on your definition of context-sensitive, but it is effectively context-free.

• By "effectively context-free" you mean "generates the same language"? That's fine, but probably not a good metric: it's an undecidable property and exploiting more expressive power can shorten the description of a language. – Raphael Jan 10 '14 at 18:26
• @Raphael By "effectively context-free" I refer to the context-free requirement that, in a rule $R \implies w$, the $R$ is a single symbol. So it's not technically context-free, just going by definition. But if you substitute $S\implies X; X\implies AB; X\implies BA$, then you can reduce that to $S\implies AB|BA$, which is definitely context-free. – AndrewK Jan 10 '14 at 21:34
• My main objective is to give an intuitive understanding, since that seems to be what he wants, and what most people I've tutored have struggled with. I'll edit my answer to make that clear. – AndrewK Jan 10 '14 at 21:37
• I see, so you want to say "If a context-sensitive grammar is the image of a homomorphism applied to a context-free grammar, it's effectively context-free". I don't see which problems that solves, but if it helps some people, fine. :) – Raphael Jan 11 '14 at 10:14