And if you allow multiple pattern-replacement pairs, you don't even need regex (the pattern can be a single fixed string) as it is enough to simulate semi-Thue systems [1].

[1] https://en.wikipedia.org/wiki/Semi-Thue_system