The X answer is a lecture on language theory including the construction and inversion of finite state automata.
To be helpful and educational, one must describe/illustrate the failure mode of X. For example just demonstrate how unwieldy pure regex is for more constrained question like “regex to check if there is no ‘ab’ within 3 char string”. “a[^ab].|.a[^b]|[^a][^a].”. (Solution complexity grows with length of the string within which we are searching)
(Solution complexity grows with length of the string within which we are searching)
No it doesn't. It's something like '([^a]|a[^b]|a$)*'.
In general it scales like '([^a]|a([^b]|$)|ab([^c]|$)|abc([^d]|$)|...)*' (ie, quadratically with the length of the needle, if I haven't overlooked a optimization), but the complement of a regular language is regular, and fixed strings are always regular, so it's always a pure regular expression (including being independent of haystack length).
And, proving that any curt correction of a silly error will likely contain its own silly error, I think that should actually be '^([^a]|a[^b]|a$)*$', since grep defaults to searching rather than matching.
Comments
To be helpful and educational, one must describe/illustrate the failure mode of X. For example just demonstrate how unwieldy pure regex is for more constrained question like “regex to check if there is no ‘ab’ within 3 char string”. “a[^ab].|.a[^b]|[^a][^a].”. (Solution complexity grows with length of the string within which we are searching)
No it doesn't. It's something like '([^a]|a[^b]|a$)*'.
In general it scales like '([^a]|a([^b]|$)|ab([^c]|$)|abc([^d]|$)|...)*' (ie, quadratically with the length of the needle, if I haven't overlooked a optimization), but the complement of a regular language is regular, and fixed strings are always regular, so it's always a pure regular expression (including being independent of haystack length).
And, proving that any curt correction of a silly error will likely contain its own silly error, I think that should actually be '^([^a]|a[^b]|a$)*$', since grep defaults to searching rather than matching.
Thanks.
Good to know that there was no repealment for Cunningham’s law.