= Solution
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 letters
$$
a_k^{-1},a_{k-1}^{-1},\ldots,a_1^{-1}.
$$
These letters belong to $A$ by symmetry of the <alphabet>. All intermediate words lie in $L$, and the final word $\gamma$ represents
$$
\overline t\,a_k^{-1}\cdots a_1^{-1}=1.
$$
Hence \b[an identity representative can be constructed effectively]:
$$
\boxed{\gamma\in L,\qquad\overline\gamma=1.}
$$
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.
Back to article page
