undefined | Better HN

0 pointsfalserum2y ago0 comments

> 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)

0 comments

a13692099932y ago

> (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).

a13692099932y ago

> It's something like '([^a]|a[^b]|a$)*'.

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.

falserumOP2y ago

Thanks.

Good to know that there was no repealment for Cunningham’s law.

j / k navigate · click thread line to collapse

0 comments

a13692099932y ago

> (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$)*'.

a13692099932y ago

> It's something like '([^a]|a[^b]|a$)*'.

falserumOP2y ago

Thanks.

Good to know that there was no repealment for Cunningham’s law.

j / k navigate · click thread line to collapse