Can a regex match valid card numbers?
18 points by bediger4000
18 points by bediger4000
Regex as syntax is a bit unfortunate since it naturally pushes people towards NFAs, when the theory with DFAs around reduction, minimality and equivalence is so much cleaner.
As the author notes, NFA -> DFA conversion is worst-case exponential, but here, he has a DFA, and all DFA are NFA with no non-deterministic transition arrows. A fun exercise I recall given in Intro to Complexity Theory was write an algorithm to print the shortest regex for a given DFA (hint: don't try to make it efficient!).
Linear scans with constant space strike me as one of the most fundamental paradigms in computation, I wish they were introduced/emphasized independently of Turing Machines/Computation Theory.
You called out regex syntax as something that pushes people towards NFAs. Are there any alternative syntaxes that would push folks towards DFAs instead? (That is, some syntax that is more likely or guaranteed to compile to a sub-exponential DFA?)
I've been steeped in regexes for so long, it's hard for me to imagine alternatives.
Are there any alternative syntaxes that would push folks towards DFAs instead?
Sort of: for a while in the 90s and early 2000s there was the whole subset of 1-ambiguous regexes, usually discussed around SGML.
But the problem is these don't cover the full set of regular languages (you obtain a strict subset, consider (a+b)*a(a+b), strings of length >= 2 with an "a" before the final character).
The fundamental tension though is that algebraically, what makes regexes so ergonomic is the existential quantifier. You want the non-determinism (i.e. repetition, there exists an "n" for which an expression is repeated, concatenation there exists a split x = uv, branching W|V there exists an accepting branch). They're easier to work with than the minimal DFA (that characterizes the language L).
Since all finite languages are regular, that means it’s possible to simply enumerate all possible valid card numbers and union them together with
|into a mammoth regex.[...]
But the more general question is the one that kept me up at night: Does there exist a DFA that recognises the language L of numbers written in base 10 that satisfy the Luhn checkdigit algorithm?
Well, yes, take your mammoth regex of length 1.7 * 10^16 and turn it into an NFA and then turn that into a DFA. You may or may not exceed 10^100 states. The question that really kept you up at night is not whether there exists such a DFA, but whether there exists one that isn't larger than the observable universe. :)
His more general question involves strings of arbitrary (unbounded) length, so this doesn't work