It's a crude bound on the complexity of an algorithm that isn't using the right data structures. I don't think that there's much to explain other than that the authors clearly did not care to optimize here, probably because their main point was that regular expressions are at least as expressive as DFAs and because they feel that it's pointless to optimize this exponential-time algorithm.
There are three nested loops of n iterations each; the regular expressions constructed during iteration k of the outer loop inductively have size O(4^k), since they are constructed from at most four regular expressions constructed during the previous iteration. If the algorithm copies these subexpressions and we overestimate the regular-expression size bound at O(4^n) for all iterations, then we get O(n^3 4^n).
Obviously we can do better. Without eliminating the copying, we can get O(sum_{k=1}^n n^2 4^k) = O(n^2 (n + 4^n)) by bounding the geometric sum properly. Moreover, as you point out, we don't need to copy at all, except at the end if we agree with templatetypedef that the output must be completely written out, giving a running time of O(n^3) to prepare the regular expression and O(4^n) to write it out. The space complexity for this version equals the time complexity.