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

The regular language $L$ is nonempty because it represents every element of the group. Find any accepted word $t=a_1\cdots a_k$ using breadth-first search in its finite-state automaton. If $t$ is the empty word, it already represents the identity.

Otherwise begin with $t\in L$ and repeatedly apply the linear-time multiplication in an automatic structure to the lettersThese letters belong to $A$ by symmetry of the alphabet. All intermediate words lie in $L$, and the final word $\gamma$ representsHence an identity representative can be constructed effectively:This is a finite preliminary computation depending only on the fixed automatic structure for a group; it uses no test for whether an arbitrary word represents the identity.