Recientemente se me ha presentado el mismo problema dos veces; una en mi clase de la universidad de Procesadores de lenguaje y otra en Codewars.
El problema en cuestión es el siguiente:
https://www.codewars.com/kata/54de279df565808f8b00126a/javascript
In this kata, your task is to create a regular expression capable of evaluating binary strings (strings with only 1s and 0s) and determining whether the given string represents a number divisible by 3.
Consiste en encontrar una expresión regular para atrapar cualquier string que tenga un número múltiplo de tres representado en binario.
Para resolverlo primero hay que conocer dos conceptos importantes:
Aqui dejo una buena explicación de las máquinas finitas de estados en video:
https://www.youtube.com/watch?v=SuCjAhGzyHs
Una máquina finita de estados es un modelo matemático que describe un sistema capaz de estar en un número limitado de estados y cambiar entre ellos según las entradas que recibe.
Siempre comienza en un estado inicial, puede tener uno o varios estados de aceptación, y se desplaza entre estados a través de transiciones que dependen de los símbolos de entrada.
La importancia de este modelo es que nos permite razonar de manera estructurada sobre problemas de reconocimiento de patrones o validación de cadenas, ya que todo lenguaje regular puede ser representado mediante una máquina finita.
Las expresiones regulares son una forma compacta de describir patrones dentro de cadenas de texto. Permiten definir de manera concisa secuencias de caracteres que deben cumplirse para que una cadena sea aceptada.
Entre los símbolos más comunes tenemos ? que indica que un elemento es opcional, * que significa que puede repetirse cero o más veces, . que representa cualquier carácter, () que sirve para agrupar expresiones, y los símbolos de anclaje ^ y $ que marcan el inicio y el final de una cadena respectivamente.
Con estos componentes básicos se pueden construir descripciones muy potentes capaces de validar cadenas con un nivel de detalle preciso.
Para atacar el problema primero construí en una hoja de cálculo todos los números hasta el 100 junto con su representación en binario.
En google spreadsheets podemos pasar a binario tan fácil como agregar lo siguiente en la casilla apuntado a la que queramos transformar;
=DEC.A.BIN(A1)
Luego añadí el cálculo de su resto al dividir entre 3 y marqué condicionalmente aquellos casos que eran múltiplos de 3. Esto me permitió visualizar claramente qué cadenas eran válidas y cuáles no.
Después diseñé la máquina de estados correspondiente. Cada estado representaba un resto posible al dividir entre 3: resto 0, resto 1 y resto 2.
A partir del estado de estos estados he ido construyendo la expresión regular.
Primero para el estado de resto 0. Vemos que si a partir del 0 repetimos agregando el número 0 se queda en el mismo estado. Por eso es seguro repetir el 0.
0*
Ahora si agregamos un número 1 pasamos al estado resto 1 en cuyo caso tenemos dos opciones posteriormente, agregar un 0 o un 1.
Según nuestro diagrama de estados con el 1 volvemos al estado anterior y con el 0 pasamos al estado de resto 2.
Razonando de esta forma podemos ir agrupando los siguientes casos siguiendo el diagrama de los estados.
La expresión regular final que obtuve es la siguiente:
(0?(1(01*0)*1)*)*
Para las pruebas he reutilizado los datos de mi hoja volcandolos a https://regex101.com/
