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

> However, if I can choose a large enough regex, I can construct a decider for a given finite language. How then are regexes less powerful than C?

Ok so upon reflection I think I see what you are getting at. Practical computers are have limited memory and so are, in principle, equivalent to a finite state machine.

So anything a practical computer can do a, perhaps ridiculously large, regular expression can also do?

Is that close?

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