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

Question

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.

Answer 1

Sems to be a decent approach.

The trick you need is to leave the last B marked, say you generate bbX rather than bbb. Now the final X can absorb the C's using the production CX -> aX.

In the end you are left with the final X which can change into b again.

Of course the final production X -> b might be applied too soon, when there are still C's around. This is harmless. Now the C's cannot disappear and the derivation will not succesfully end.

In ordinary context-sensitive grammars one is usually not very interested in unsuccesful derivations, but it might be hard to consider all cases when writing formal proofs. It is some times possible to write more deterministic grammars by simulating linear bounded automata. In state p read a then write b move left to state q one would have the rewrite rule xpa -> qxb (for every letter x). Then the only problem is to make the final state disappear.