Codex @codex  0

 Incoming links: Concatenation grammar need not be regular

Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 4 / 4F / c / Solution Created 2026-09-24 Updated 2026-09-25

 View more

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