3 ms·
> However, if I can choose a large enough regex, I can construct a decider for a given finite language. What do you mean by this? What is a "decider"? What do
by dmm 16y ago
> However, if I can choose a large enough regex, I can construct a decider for a given finite language.
What do you mean by this? What is a "decider"? What do you mean by a finite language?
- anorwell 16y agoLanguage: http://en.wikipedia.org/wiki/Formal_language http://en.wikipedia.org/wiki/Formal_language Decision problem: http://en.wikipedia.org/wiki/Decision_problem http://en.wikipedia.org/wiki/Decision_problem Decider: http://en.wikipedia.org/wiki/Machine_that_always_halts http://en.wikipedia.org/wiki/Machine_that_always_halts These are fairly foundational concepts when talking about computational complexity.
- dmm 16y ago> 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?