The deceptively simple question—"Can regex validate credit card numbers via the Luhn algorithm?"—unlocks a fascinating journey through automata theory, modular arithmetic, and the hidden structure of payment systems. While superficial regex solutions abound for checking card number patterns, true validation requires verifying the check digit through Hans Peter Luhn's 1960s algorithm. This mathematical safeguard detects typos by calculating a weighted sum of digits, but its stateful computation appears fundamentally at odds with regex's pattern-matching nature.

Inside the Luhn Algorithm

Payment card numbers follow ISO standards: an issuer identifier (6-8 digits), an account ID, and a final check digit computed via:

def luhn_double(d: int) -> int:
    return 2*d if 2*d < 10 else 2*d - 9

def validate_luhn(number: str) -> bool:
    digits = [int(d) for d in number]
    parity = len(digits) % 2
    total = 0
    for i, d in enumerate(digits):
        total += luhn_double(d) if i % 2 == parity else d
    return total % 10 == 0

Crucially, luhn_double acts as a permutation function over digits (e.g., 5→1, 8→7), ensuring transposition errors alter the checksum. This stateful accumulation seemed to defy regex implementation—until automata theory offered a path.

The Automaton Breakthrough

Since regular expressions describe regular languages recognized by deterministic finite automata (DFAs), the existence question reduces to: Is the infinite set of Luhn-valid numbers a regular language? The solution emerged through a 100-state DFA tracking partial sums modulo 10 for even and odd digit positions:

def luhn_dfa(number: str) -> bool:
    state = (0, 0)  # (even_parity_sum, odd_parity_sum)
    for d in map(int, number):
        # Transition: δ((E,O), d) = ((O+d) % 10, (E + luhn_double(d)) % 10)
        state = ((state[1] + d) % 10, 
                (state[0] + (2*d if 2*d < 10 else 2*d - 9)) % 10)
    return state[0] == 0  # Accept if even-sum residual is 0

This elegant construction works because:
1. Modular arithmetic distributes over the Luhn sum
2. State pairs (E,O) track cumulative sums for both possible string-length parities
3. Transitions alternate roles between digit addition and Luhn doubling

Theoretical Triumph, Practical Reality

While Kleene's theorem guarantees a regex exists since the DFA recognizes the language, converting 100 states with 1,000 transitions yields combinatorial explosion. Enumerating all 10¹⁵ possible 16-digit valid numbers is equally infeasible. Thus, while DFAs compactly encode the logic through state transitions, regex's declarative nature struggles with arithmetic constraints.

This duality has practical implications: financial systems needing PCI DSS compliance could theoretically use such automata for log scanning—but shouldn't. As the author cautions: "You definitely should not rely on a regex to detect or scrub... flagrant violations." Yet the exercise illuminates how computational models reveal constraints invisible in everyday code.

The beauty lies in witnessing abstract automata precisely model real-world validation—a reminder that behind every swipe or tap, permutations of finite states stand guard against human error.

Source: Can a regex match valid card numbers? (abstractnonsense.xyz)