Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2018/ii/paper-1/4g/b/iii/solution

This language is not context-free. Let be a proposed pumping length and choose with . In any pumping decomposition of the unary word , pumping once more increases its length by an integer with . But
so the pumped length is not a power of three, contrary to the pumping lemma for context-free languages. This is also an instance of the fact that a unary context-free language is regular, whereas the powers of three are not ultimately periodic.

New to topics? Read the docs here!