I'm looking for a context-sensitive grammar that describes the following language: $L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\}$ .
I've got problems with the fact that no rules such as $X \to \varepsilon$ are allowed and therefore I can't place any nonterminal indicating the "middle" of the word. Is there any trick to the problem?
Indeed, there is a simple trick that allows you to add extra information at a certain position: just replace a letter adjacent to the position and mark it with the information, and the original letter.
In your example, have a nonterminal $M$ for the middle, but as it can not be deleted, it also counts as a normal letter. Thus we have two copies $M_a$ and $M_b$ to indicate the letters replaced. In the end of the derivation the markers should be replaced by their letter content, by simple productions like $M_a\to a$.
In most cases the application of $M_a\to a$ needs to be performed at the end of the derivation process. In some constructions this does not need to be "timed": when the $M$ disappears too soon, the derivation cannot find a proper position and the process will not stop successfully. In other cases one does need a kind of control. This is sometimes done by introducing a nonterminal as a signal that moves along the letters. Again, this signal should also carry a terminal otherwise you end up in the same problems.
Moving information around is easy in so-called monotonic grammars ($\alpha\to \beta$ with $|\alpha|\le\beta|$) using rules like $XA \to AX$, which can be seen as $X$ jumping over $A$. For proper context-sensitive grammars one needs to split this in three steps: $XA \to XA^X, XA^X\to AA^X, AA^X\to AX$. in each production one letter is changed in a proper context. It takes quite some imagination to see this process does not interact with other parts of the derivation. E.g., what happens when the $A$ in the last step is first involved in another derivation step?
This might not work for very short words, when there is more information than positions available. The most simple solution to that is to ignore short strings in your construction, and generate them separately.
Short default answer: come up with an LBA which accepts the language and use the simulation used to prove that context-sensitive grammars and LBA define the same set of languages. But that is of course not what you are after.
In this specific case, try to think of using a right-linear grammar for $\Sigma^*$ twice, one for the left and one for the right half. All you have to ensure that both grammars derive "in sync".
This can be done by swapping around a control token. That is to say, the left grammars picks a rule, generates the fitting control token and passes it to the right grammar. The right grammar sees the control token and executes the fitting rule. Note that you can also implement two-way communication in this way, but it's not necessary here.
There is one problem with context-sensitive grammars: they can never delete non-terminals (except $S \to \varepsilon$ if the empty word is in the language). Therefore, we have to create only as many non-terminals as we are going to need; none can be redundant.
One way to achieve this is to use the same trick as for certain proofs about LBA: generate all non-terminals you are going to need first, i.e. prepare the "tape". Later, "move around" on that tape. Only "at the end", replace all non-terminals with terminals.
So let $G=(N, \Sigma, \delta, S)$ with $\Sigma = \{a,b\}$ (the construction readily extends to larger alphabets) and $N$, $\delta$ given by the following rules.
$\qquad \begin{align} S &\to \hat{X}_l S' X_r \mid aaaa \mid abab \mid baba \mid bbbb \mid aa \mid bb \mid \varepsilon \\ S' &\to X_l S' X_r \mid X_l \hat{X}_r \end{align}$
are the rules for generating the "tape". Note that the hat denotes the "head position" and indices $l,r$ denote which half of the word a non-terminal belongs to. The short words are generate thus in order to safe some rules below. Now we need rules to derive one symbol in the left part:
$\qquad \begin{align} \hat{X}_l X_l &\to X_\gamma \hat{X}^\gamma_l \\ \hat{X}_l X_\alpha &\to X_\gamma X^\gamma_\alpha \end{align}$
for all $(\alpha, \gamma) \in \Sigma^2$. Note how we use the upper index to carry the generated symbol to the right. $X_a$ and $X_b$ are "final" non-terminals which will only be used for moving the control token around and to derive terminals later. Note furthermore that the second rule is (only) used for the last symbol of the right half.
For moving the carry to the right half, we have to move past both remaining $X_l$ and already generated $X_\alpha$:
$\qquad \begin{align} \hat{X}^\gamma_l X_l &\to \hat{X}_l X^\gamma_l \\ \hat{X}^\gamma_l X_\alpha &\to \hat{X}_l X^\gamma_\alpha \\ X^\gamma_l X_l &\to X_l X^\gamma_l \\ X^\gamma_l X_\alpha &\to X_l X^\gamma_\alpha \\ X^\gamma_\alpha X_\beta &\to X_\alpha X^\gamma_\beta \end{align}$
for all $(\alpha, \beta, \gamma) \in \Sigma^3$. Now, once the carry reaches the right control token, we have to mimic the rule used on the left:
$\qquad\begin{align} X^\gamma_l \hat{X}_r &\to X_l \hat{X}^\gamma_r \\ X^\gamma_\alpha \hat{X}_r &\to X_\alpha \hat{X}^\gamma_r \\ \hat{X}^\gamma_r X_r &\to X_\gamma \hat{X}_r \\ \hat{X}^\gamma_r &\to X_\gamma \end{align}$
for all $(\alpha, \gamma) \in \Sigma^2$. Note that the first rule is used for the first symbol of the right half, and that the last rule can only be used for the very last symbol, otherwise the derivation never terminates. Now we only need the terminating rules
$\qquad X_\alpha \to \alpha$
for all $\alpha \in \Sigma$ and we are done. These rules, too, can only be applied after everything (to the left) is done, otherwise the derivation will not terminate.
Note that this grammar is ambiguous. Not only can can $X_\alpha \to \alpha$ (safely) be applied anywhere to the left of the left "head" at any time, but there can also be multiple carries underway at the same time. Since they can never overtake each other the correct order is maintained.
One remark has to be made still: above grammar is not context-sensitive as many rules changes both of the symbols on the left-hand side. This is not allowed for context-sensitive grammars. Luckily, we can simulate any rule $R$ of the form
$\qquad A B \to C D$
by
$\qquad \begin{align} A B &\to A Y_R \\ A Y_R &\to X_R Y_R \\ X_R Y_R &\to X_R D \\ X_R D &\to C D \end{align}$
so we are good and can work with the smaller grammar. Showing that interference between multiple such simulations does not hurt is left as an exercise.
Do you see how to extend this to $L_k = \{ w^k \mid w \in \Sigma^*\}$? Does it also work for $L = \bigcup_{i\geq 1} L_k$? Can you use the same construction for any $L^k$ for regular $L$?
Although I don't know how the context-sensitive grammar will look like, you can circumvent your problem with the symbol $X$ as follows.
You know that your concatenated words $w$ must be at least of length $|w| \ge 1$. Hence, you could simply "encode" those $\varepsilon$-rules of your grammar by some rules like: $$aXa \to aa,\ \ aXb \to ab,\ \ bXa \to ba,\ \ bXb \to bb$$
Though, I cannot yet see the overall solution, because to my mind it seems like your left-hand sides of your grammar rules potentially get arbitrarily long, because I think you would try to consider the prefixes of $w$ somehow in your rules.
