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

LetBoth are regular grammars and their variable sets are disjoint. Their ordinary concatenation grammar adds a new ruleThis 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.