Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 120 / 1 / f / Solution

Construct $z$ as above, and run the equality group multiplier automaton $M_{\epsilon }$ on $z\otimes \gamma$. Both inputs belong to $L$, soThe final finite-state automaton run takes $O(\max (|z|,|\gamma |)+1)=O(n+1)$ time. The word problem for a group is therefore decidable in quadratic time:The empty word is accepted immediately. Comparing $z$ and $\gamma$ as literal strings would be incorrect, since an automatic structure for a group need not give unique representatives.