On Fri, Mar 27, 2015 at 7:40 PM, Steven D'Aprano <steve+comp.lang.pyt...@pearwood.info> wrote: > Excluding that, the consensus seems to be that Perl's regexes are stronger > than Chomsky regular expressions, but nobody quite knows how much stronger. > It's likely that they are at least as powerful as context-free grammars, > but not as powerful as a Turing machine (excluding embedded Perl code), but > that covers a lot of ground in the hierarchy of language power:
Intuitively, I should think that the combination of recursive subpatterns and assertions would make them able to generate at least the context-sensitive languages. > So it's an open question as to whether or not you could prove a Sudoku grid > solvable using a Perl regex. Python regexes are less powerful than Perl's, > so if you can't do it in Perl, you can't do it in Python. As somebody else in the thread pointed out, the set of all valid Sudoku grids is a finite language, and all finite languages are regular. QED. -- https://mail.python.org/mailman/listinfo/python-list
