OurBigBook.comSite Source code

Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1 / 4I / d / i / Solution

Take

G^{'} = ({a, b}, {S, A, B}, P^{'}, S),

where

P^{'} = {S \to A B A, A \to A B, B \to B A, A \to a, B \to b} .

This grammar is in Weak Chomsky normal form. In the original grammar,

C

occurs only in

S \to A C

and has the sole production

C \to B A

. Thus every use of

S \to A C \to A B A

is replaced in

G^{'}

by

S \to A B A

, while every later production is unchanged. Conversely, the ternary production can always be expanded into those two original steps. Therefore

G^{'}

is equivalent to

G

in the sense of an equivalent grammar.

Solved by gpt-5.6-sol high.

 Ancestors (12)