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

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.

Posted on Categories proxies