While reading Bill Thurston's obituary in the Notices of the AMS I came across the following fascinating anecdote (pg. 32):
Bill’s enthusiasm during the early stages of mathematical discovery was infectious. Once, while sitting in his
living room, Bill said to me, “I can do this group with
grep,” which was sort of strange to hear at first. But being
his student I knew just enough computerese to have an
inkling of what he was saying: he was able to compute
in that group with the UNIX utility for processing regular
expressions using finite deterministic automata. From
there, it was exciting to observe the quick unfolding of
the theory of automatic groups.
Looking through David Epstein's Word Processing in Groups I can see that there are indeed connections between automatic groups and regular expressions that should allow faster algorithms for certain computations e.g. solving the word problem.
But is there a concrete example of a group-theoretic computation with grep?
Best Answer
I wrote that quote, and I'll take the hint of @SamNead and try to write an answer, although the best I can do is to write a somewhat speculative extension of the story behind the quote, laced with some mathematical musings.
From my memories of that period (sometime in the mid-late 1980's), I only vaguely recall looking at any actual output of Bill Thurston's computer experiments using grep to compute in groups. My memory is not at all precise enough regarding any actual examples he might have produced, but I suspect that they must have been pretty simple examples, for the following reasons.
In the theory of regular languages and FDAs (finite deterministic automata), there are reasonably simple algorithms for going back and forth between regular expressions and finite deterministic automata, producing an expression matching exactly the words accepted by a given automaton, and producing an automaton accepting exactly the words matched by a given expression. The algorithm from regular expressions to FDAs works pretty efficiently and is the basis of the grep utility. The algorithm from FDAs to regular expressions seems to be horribly inefficient, as reported by Derek Holt in his comment. So one might expect that writing an actual regular expression that matches normal forms for a certain group could be quite tedious.
Nonetheless if one is clever enough one can sometimes just manually come up with a regular expression to match a given language. See the exercise Derek Holt suggests in his comment; carrying out that exercise will likely give you the most direct answer to your question.
I suspect that this is what Thurston was doing during this discovery period: noticing that certain finitely generated groups have a regular language of normal forms.
Thurston was also very familiar with concepts of cone types (developed by Jim Cannon around that time; Thurston and Cannon talked together a lot during that period). So at some point during this process he certainly also noticed the connections between cone types and what we now call the 2-tape "multiplier automata" which are at the heart of the theory of automatic groups. It is tempting to speculate whether Thurston's grep experiments extended to writing regular expressions for 2-tape multiplier automata, but honestly I have no idea.