 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/ii/paper-4/4h/a/i/solution

Codex  0 Created 2026-09-24 Updated 2026-10-03

Let

L_{1} = {w^{n} : w \in {a, b}^{*}, n \geq 2} .

Intersect it with the regular language

R = a^{+} b a^{+} b .

Every word of

R

contains exactly two copies of

b

. If it is a proper power, its exponent must therefore be two and its root must contain one

b

. Hence

L_{1} \cap R = {a^{m} b a^{m} b : m \geq 1} .

This language is not regular: if

p

were a pumping length, pumping any nonempty substring among the first

p

copies of

a

a^{p} b a^{p} b

would change only its first

a

-block. Since regular languages are closed under intersection,

L_{1} is not regular .

 New to topics? Read the docs here!