Es fácil describir una máquina de estados finitos que reconoce múltiplos de 9: realice un seguimiento de la suma de dígitos (mod 9) y agregue cualquier dígito que se acepte a continuación. Tal FSM tiene solo 9 estados, ¡muy simple! Por la equivalencia entre el reconocimiento de FSM y los lenguajes regulares, existe una expresión regular para múltiplos de 9. Sin embargo, cualquier expresión regular es probable ... muy ... larga. Como en, probablemente del orden de un gigabyte.

Hay un ejemplo trabajado en https://www.quaxio.com/triple/ para múltiplos de 3. En la parte inferior de la página, el autor proporciona una solución algo "optimizada a mano" que es un poco más corta que la conversión ingenua de FSM para regex.

El reto:

Debe hacer una expresión regular para detectar múltiplos de 9. Como se espera que tal expresión regular sea muy larga, le pido que proporcione un programa que pueda imprimir su expresión regular. (Si realmente quiere dar una expresión regular completa, ¡quizás la aloje en otro lugar y vincule aquí!)

Debe poder decirnos el recuento exacto de caracteres de la salida de su programa, por lo que tener un programa que simplemente intente todas las expresiones regulares hasta una cierta longitud, hasta que encuentre una que funcione, no es aceptable a menos que se ejecute lo suficientemente rápido como para que pueda ejecutarlo hasta su finalización y darnos la longitud de expresión regular resultante!

Los puntos son por tener la expresión regular de salida más corta, no basada en la duración del programa, por supuesto. Dado que la expresión regular es el "programa" que estoy solicitando, y es demasiado largo para transmitir convenientemente aquí, todavía estoy etiquetando este código de golf.

Reglas:

• La entrada solo incluirá caracteres coincidentes [0-9]*.
• Su expresión regular debe coincidir con múltiplos de 9, pero nada más. Los casos que no están compuestos completamente por los dígitos 0-9 y son entradas inválidas pueden coincidir o fallar como lo desee.
• Dada la motivación de que un DFA lo reconoce fácilmente, la expresión regular resultante debe ser una expresión regular en la terminología más teórica, es decir, solo operadores bajo los cuales los lenguajes regulares están cerrados. Para ser precisos, las únicas cosas que están permitidas:
  • Literales, rangos de caracteres ( [ab], [a-f], [^k]), Kleene estrella ( *), los anclajes ( ^y $), la agrupación a través de paréntesis, alternancia ( |), términos opcionales ( ?), uno-o-más términos ( +), símbolos de anticipación ( (?=)), símbolos de anticipación negativos ( (?!)), lookbehinds ( (?<=)), lookbehinds negativos ( (?<!)), condicionales (como en https://www.regular-expressions.info/conditional.html - (?(?=test)then|else)) y referencias posteriores de longitud limitada (ver más abajo).
• Ejemplos de cosas que no están permitidas:
  • Referencias posteriores de longitud arbitraria, referencias directas, recursividad, subrutinas, construcciones en bucle, código ejecutable, cualquier variación de 'eval' o construcciones integradas para convertir la cadena a un valor aritmético.
• Las referencias posteriores que pueden mostrar que tienen una cadena de enlace de longitud limitada son aceptables, ya que pueden almacenarse en estado finito y no alteran la regularidad del idioma. Por ejemplo, la expresión regular (..2.[3-5])4\1.\1es aceptable, ya que hay una longitud limitada en el grupo de captura \1. Esta es una construcción regular. Una construcción como (2*)0\1no es aceptable, ya que el grupo capturado no puede almacenarse en estado finito.
• Su expresión regular es libre de aceptar o rechazar enteros con ceros a la izquierda extraños como desee. Sin embargo, la cadena "0"debe ser aceptada.

Haskell , 207,535 202,073 bytes

5,462 bytes guardados usando en 0|9lugar de [09]donde sea posible.

digits n
  | x == 0    = "0|9"
  | otherwise = show x
  where x = mod n 9

regex 0 = "[09]*"
regex n = (regex' n (-1) (-1)) ++ "*"

regex' 0 start end = digits (end - start)
regex' n start end = '(':(regex' 0 start end) ++ (concat ['|':(regex' (n-x) (start-x) (-1)) ++ (regex (n-x))
                                                  ++ (regex' (n-x) (-1) (end-x)) | x <- [1..n]]) ++ ")"

main = do
  putStr ("^" ++ (regex 8) ++ "$")

Pruébalo en línea!

Solo una rápida adaptación de la expresión regular dada en las notas al pie del artículo vinculado para comenzar las cosas.

Pastebin de salida regex , cortesía de Herman Lauenstein.

Si bien no he podido probar la expresión regular completa, la modificación del programa para verificar la divisibilidad por 3 en cambio da algo exactamente equivalente a la expresión regular en la que basé esto. Además, modificar el programa para verificar la divisibilidad de la suma de dígitos entre 4 o 5 también parece funcionar en los números en los que lo probé.