Automata and cells in affine Weyl groups

Let W~ be an affine Weyl group, and let C be a left, right, or two-sided Kazhdan–Lusztig cell in W~. Let Reduced © be the set of all reduced expressions of elements of C, regarded as a formal language in the sense of the theory of computation. We show that Reduced © is a regular language. Hence the reduced expressions of the elements in any Kazhdan–Lusztig cell can be enumerated by a finite state automaton.