Can a regex match valid card numbers?

A colleague recently posed the question of whether it's possible to validate credit card numbers using regex and the Luhn algorithm, which piqued the author's interest. To address this, the author will outline the problem and provide a solution using concepts such as Deterministic Finite Automata (DFA), regular languages, and modular arithmetic. The author will also include Python code to make the explanation clearer.

Credit card numbers adhere to an ISO standard format, which includes a check digit for error detection. The Luhn algorithm calculates this check digit by walking over the digits from right-to-left, alternating between adding the digit and the "Luhn double" (a permutation function) of the digit to a rolling sum. The sum must be divisible by 10 for the number to be valid.

However, DFAs cannot process strings in reverse order, and regular languages are closed under reversal, but this alone is insufficient to construct a DFA for the Luhn algorithm. The author proposes working with a left-to-right formulation based on the parity of the length of the digits.

To solve the problem, the author will examine if a DFA can recognize the language of numbers written in base 10 that satisfy the Luhn check digit algorithm. If such a DFA exists, then the language is regular, and a regular expression should match all words in the language.

The author revisits the concept of divisibility DFA, which is equivalent to the Luhn algorithm, and proposes constructing a transition function for a DFA that recognises such numbers. This approach gives hope that a DFA for the Luhn algorithm might exist.