where the overlap notion, trips vast majority of people trying to regex it.
in this case, the issue has to do with overlapping match.
so, given a thing, and a pattern, what happens if the pattern can match multiple parts that overlap? (most lang's regex functions do not have a option to specify this. WolframLang does.)
and, u have the issue of greedy match vs lazy match.
and, u have the issue of captured patterns or all occurrences.
and, u have the issue of complete match vs contains.
then, when u add in functionality of replacement, u have more complex issues, such as whether replacements happen sequentially.
[see Find Replace Feedback Loop Problem]
Examples of Natural Complexity: Regular Expression, Lambda, Recursion
these complexity, are natural complexity. or, mathematical complexity.
not artificial complexity such as c and unix.
that is, no matter how well u design ur lang's functions or the regex syntax, these complexity are still there.
such as, infinite loop, divide by zero.
and algorithmic complexity, recursion, recurrence relation, etc. the whole comp sci complexities.
recursion is another good example.
the concept is simple. but when u actually do computation using recursion, as the scheme lisp fans often do, u run into a lot complexities.
recurrence relation, such as when u need to compute fibonacci number, is a example of recursion complexity.
which in turn, gets u into the memoizing concept. another complexity.
this is why, pattern matching, in particular the symbolic pattern matching of wolfram lang, takes few years to master. just like regex.
the symbolic pattern matching, is basically just like regex, except that, regex act on linear flat sequence of symbols (called string), but wolfram's symbolic pattern matching works on basically purely nested brackets text.)
and this is called “term rewriting system” in comp sci.
btw, another illustration of natural complexity in programing, is function as expression. aka lambda.
once u allow function to be returned, or as argument, what u got is a comp sci lambda.
then, all sorta complexity arise.
u arise, the concept of closure. and, u arise, the concept of combinators or y-combinator.
Artificial Complexity
if ur lang does not allow function as a value or arg, that is, no lambda in ur lang. u don't have this complexity.
u have a weak lang, like C.
just like abacus is a tedious computer.
but C is also very complex.
the complexity of C is called artificial complexity.
that is, humans made it complex.
for example, which syntax is for loop, what syntax is the printf, and when certain syntax means what thing where, etc. and how this syntax maps to the cpu and memory, another man-made artificial complexity.
