¿Por qué un lenguaje regular se llama 'regular'?

Acabo de completar el primer capítulo de Introducción a la teoría de la computación de Michael Sipser que explica los conceptos básicos de los autómatas finitos.

Él define un lenguaje regular como cualquier cosa que pueda ser descrita por un autómata finito. Pero no pude encontrar dónde explica por qué un lenguaje común se llama "regular". ¿Cuál es el origen del término "regular" en este contexto?

NOTA: Soy un novato, ¡así que intenta explicarlo en términos simples!

Como dice Kaveh en un comentario, Kleene le otorgó el nombre cuando inició la teoría de los autómatas y los lenguajes formales. Creo que el término fue arbitrario, aunque han pasado muchos años desde que leí su artículo original.

Los matemáticos tienen la costumbre de secuestrar sustantivos y adjetivos comunes para objetos y propiedades matemáticas, a veces con buenas razones, como analogías o metáforas geométricas u otras, y otras veces de manera arbitraria. Simplemente mire "grupo", "anillo", "espacio", "gavilla", "atlas", "múltiple", "campo" y así sucesivamente.

De hecho, el término "regular" para las lenguas de estado finito, aunque todavía prevalece en la teoría de autómatas, no se usa mucho en su primo algebraico, teoría de semigrupo finito o álgebra abstracta en general. ¿Por qué? Debido a que el término ya se tomó para un semigrupo que está cerca de un grupo en un sentido técnico específico, por lo que no se puede combinar un idioma regular en el sentido de Kleene con un semigrupo regular correspondiente . Tercero, Kleene definió otro tipo de evento llamado "definitivo", que fue muy estudiado durante un tiempo, pero que resultó no ser particularmente fructífero. Hoy, los conjuntos finitos de lenguaje juegan el papel de eventos definidos como la base para eventos regulares.

El término preferido en álgebra es "racional" tanto para la clase de idiomas de Kleene como para los semigrupos y monoides más generales. Ese uso también refleja una analogía importante entre el término "racional" en álgebra como la solución de una ecuación lineal con coeficientes enteros y el concepto de serie de potencia racional en autómatas y teoría del lenguaje formal.

Información Adicional. El documento original de Kleene de 1951, titulado "Representación de eventos en redes nerviosas y autómatas finitos" se puede encontrar aquí . En P. 46 resuelve la arbitrariedad del término "regular" con esta declaración:

A continuación describiremos una clase de eventos que llamaremos "eventos regulares". (Agradeceríamos cualquier sugerencia sobre un término más descriptivo).

Aparentemente, a nadie se le ocurrió un término más descriptivo. ;-)

Como suele ser el caso con los documentos seminales que conducen al desarrollo intensivo de áreas completamente nuevas, la terminología y los conceptos son casi irreconocibles en los términos actuales. Primero, el artículo trataba sobre modelos de neuronas, de ahí el uso de "eventos" en lugar de "lenguajes" o "conjuntos". El término "eventos" persistió bien en los años 60 y 70, incluso después de que la importancia de los conceptos de Kleene para autómatas y lenguajes formales superara ampliamente cualquier valor para la neurociencia.

En segundo lugar, hay algunas diferencias matemáticas, como definir lo que se llamó "Cierre de Kleene" como una operación binaria, equivalente a , en lugar de la operación unaria más simple o que usamos hoy. La motivación de Kleene era evitar la cadena vacía (o evento con duración cero en sus términos). Esa fue una intuición notablemente profética, ya que la teoría posterior ha demostrado cuán crucial es la elección de incluir o excluir la cadena vacía de las definiciones en muchos contextos. Tercero, Kleene definió un concepto llamado "eventos definidos" y desarrolló eventos regulares a partir de ellos, pero hoy en día usamos conjuntos finitos para ese propósito. Los eventos definidos se estudiaron durante un tiempo, pero resultaron ser mucho menos importantes que los eventos / conjuntos / idiomas regulares.a ∗ a $a^*b$$a^*$$a^+$

De todos modos, una lectura completa de este documento probablemente no merezca el tiempo de nadie hoy, excepto para fines históricos. Lo hojeé por las definiciones e ideas cruciales, y eso fue divertido.

Siempre he entendido que el término "regular" significa que se basa en un patrón que se repite. Después de enumerar todas las cadenas de cierta longitud, las ha visto todas. No habrá nada nuevo después.

(Es solo una vaga intuición, por supuesto).