Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2018/ii/paper-3/4g/b/solution

Add a fresh start symbol with .
Find the nullable nonterminals, add the variants obtained by omitting nullable occurrences, and remove all epsilon productions. Omit as well because the requested language excludes .
Remove every unit production by copying the non-unit productions reachable from to .
Remove nonterminals that are unreachable from or cannot derive a terminal word.
In every right-hand side of length at least two, replace a terminal by a fresh nonterminal with .
Replace each right-hand side of length greater than two by a chain of binary productions using fresh nonterminals.
Each remaining production is of the required binary or terminal form, and these transformations preserve every nonempty generated word. Thus .

New to topics? Read the docs here!