Hacker News new | past | comments | ask | show | jobs | submit login

I'm not a big fan of your explanation. To be more precise, true "regular expressions" are computationally equivalent to deterministic finite automata, which indeed can test an n-character string in O(n) time.

NFAs and DFAs both recognise the regular languages (and only them).

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact