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.
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. :)
vpr | 9 hours ago
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.
bitshift | 6 hours ago
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.
tomsmeding | 3 hours ago
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. :)
drmorr | 3 hours ago
His more general question involves strings of arbitrary (unbounded) length, so this doesn't work