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