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

31

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!

Phil Wright
fuente
66
Parece que esto se remonta a Kleene y su estudio de los sets regulares .
Kaveh

Respuestas:

28

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 +abaa+

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.

David Lewis
fuente
66
"Regular" está muy sobrecargado y hay lenguajes no racionales con funciones generadoras racionales. Ambos términos apestan.
Raphael
2
Gracias por desenterrar el papel seminal de Kleene. Yo diría que, cuando los autómatas se usan como modelos de cómputo , a diferencia de los reconocedores de idiomas, todavía usamos el término "eventos" para los símbolos de entrada / salida. Pero, vale la pena leer el artículo de Kleene por otra razón. La informática también debe estudiar cómo ocurre la computación en los mundos naturales y sociales, además de estudiar cómo sucede en nuestras propias máquinas. Hemos estado perdiendo ese enfoque a lo largo de los años porque la marcha inexorable de la tecnología nos consume.
Uday Reddy
1
El documento en realidad no recibió amplia circulación hasta que se publicó en un volumen de AMS de 1956 llamado Automata Studies, que contenía varios documentos iniciales importantes en la teoría de autómatas. Ah, los maravillosos días antes de la web y la publicación instantánea, cuando las cosas se movían mucho más lentamente. Puede obtener el libro en Amazon por solo $ 72.50, o usarlo por $ 12 + envío.
David Lewis
4

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).

Uday Reddy
fuente
1
{anbncn} se puede "aprender" después de ver algunos pequeños ejemplos.
Raphael