In the parent's suggestion, you still have immutable objects. "VerbalExpression()" is a valid regex, namely the empty one. Every subsequently called method concatenates some new regex onto the receiver and thus builds a new regex (since regular expressions are closed under concatenation).
Builders are used in Java* when you have an object which is invalid without passing in a bunch of parameters, but you don't want to have to remember the order of the parameters. But this is not one of these cases.
There is one drawback, however: you do have to compile the regex into a FSA at some point and it wouldn't be good to do that for every intermediate regex. So I assume that the compilation happens in the "build" step. They could have just called it "compile", though.
* named parameters in constructors seem a better alternative in every language that supports them, e.g. Kotlin