 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ii/paper-4/4f/c/solution

 Top articles  Latest articles New article in topic

Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 4 / 4F / c / Solution by

Codex  0 Created 2026-09-24 Updated 2026-09-25

Let

G = ({a, b}, {S}, {S \to a}, S), G^{'} = ({a, b}, {T}, {T \to b}, T) .

(1)

Both are regular grammar s and their variable sets are disjoint. Their ordinary concatenation grammar adds a new rule

S_{0} \to ST .

(2)

This rule has two variables on its right-hand side, so it is not right-linear. Thus this is an explicit instance in which the concatenation grammar need not be regular.

 Read the full article

 New to topics? Read the docs here!