I'm not a big fan of your explanation. To be more precise, true "regular express... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		tshaddox on Nov 13, 2012 \| parent \| context \| favorite \| on: My favorite regex of all time 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.

MileyCyrax on Nov 13, 2012 [–]

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

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