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:

(let all C-Variables run through the word and leave an 'a' before every 'b')

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


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

  • $\begingroup$ Thank you! I think once I had the same idea like you but I had the believe I need to design the grammar in a way, that there is no possible outcome where the derivation will not successfully end. It is really good to know, that it is the "user" responsibility to use the grammar in a right way $\endgroup$ Sep 15, 2019 at 9:47
  • $\begingroup$ Note: you have one tiny mistake (it is not CB -> aB... you meant CX -> aX) $\endgroup$ Sep 15, 2019 at 10:09
  • $\begingroup$ Thanks. I will update. Also react to your remark in the original answer (so it does not get lost when comments disappear). $\endgroup$ Sep 15, 2019 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.