I am studying for an upcoming exam and this is an old exam question from two years ago (all exams were made available through our lecturer):

Show that $ L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}$ is context-sensitve.

I could easily construct a LBA for this language. But since the notation/construction of LBAs weren’t really explained, I would have to define it in the exam.

So I assume this task was expected to be done by constructing a context-sensitive grammar.

**NOTE:** In our lecture the definition of a context-sensitive grammar was in fact the definition of a noncontracting grammar. So any rule like this **x -> y** is allowed if **|x| <= |y|**

So this is allowed:

`aAb -> bXaa `

My best idea goes like this:

`S -> AB B -> bB | b A -> CA | C Cb -> abC Ca -> aC `

so to generate `aaabaaabaaab`

I do this:

`S AB AbB AbbB Abbb CAbbb CCAbbb CCCbbb (let all C-Variables run through the word and leave an 'a' before every 'b') CCabCbb CCababCb CCabababC ... aaabaaabaaabCCC `

But I can’t make all the ‘C’-Variables disappear.