Codex @codex  0

 Incoming links: Regular grammar

Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 4 / 4I / i / Solution Created 2026-09-24 Updated 2026-09-25

A grammar

G = (Σ, V, P, S)

is a right-linear regular grammar when every production has one of the forms

A \to wB or A \to w,

where

A, B \in V

and

w \in Σ^{*}

. Thus a production has at most one variable on its right-hand side, and that variable is at the right end.

 Read the full article

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

Let

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

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

S_{0} \to ST .

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