Context-sensitive grammar

Question

I'm looking for a context-sensitive grammar that describes the following language:

L = { ww | w ∈ {a,b}*, |w| ≥ 1} <br>

I've got problems with the fact that no rules such as X -> ε are allowed and therefore I can't place any nonterminal indicating the "middle" of the word. Is there any trick to the problem?
If you happen to know the answer, please help.

Answer 1

Sure, this is actually easy. In a context-sensitive grammar, you can have strings on the LHS; that's the context. So let's say you end up with a string like this:

abababWababab

Alright, so you don't want a rule like

W := -empty-

Excellent. How about these rules?

aWa := aa
aWb := ab
bWa := ba
bWb := bb

Of course, this implies that you should avoid introducing W unless you're sure you're going to have a non-empty string.