Por que um idioma comum é chamado de 'regular'?

Acabei de concluir o primeiro capítulo da Introdução à Teoria da Computação, de Michael Sipser que explica o básico dos autômatos finitos.

Ele define uma linguagem regular como qualquer coisa que possa ser descrita por um autômato finito. Mas não consegui encontrar onde ele explica por que um idioma comum é chamado de "regular?" Qual é a origem do termo "regular" neste contexto?

NOTA: Sou iniciante, por favor, tente explicar em termos simples!

Como Kaveh diz em um comentário, Kleene deu o nome de volta quando lançou a teoria dos autômatos e as linguagens formais. Acredito que o termo foi arbitrário, embora tenha passado muitos anos desde que li seu artigo original.

Os matemáticos têm o hábito de seqüestrar substantivos e adjetivos comuns para objetos e propriedades matemáticas, às vezes com bons motivos, como analogias ou metáforas geométricas ou outras, e às vezes arbitrariamente. Basta olhar para "grupo", "anel", "espaço", "feixe", "atlas", "coletor", "campo" e assim por diante.

De fato, o termo "regular" para linguagens de estado finito, embora ainda predominante na teoria de autômatos, não é muito usado em seu primo algébrico, teoria de semigrupos finitos ou álgebra abstrata em geral. Por quê? Como o termo já foi adotado para um semigrupo que está próximo a um grupo em um sentido técnico específico, não era possível combinar um idioma regular no sentido de Kleene com um semigrupo regular correspondente . Terceiro, Kleene definiu outro tipo de evento chamado "definitivo", que foi muito estudado por um tempo, mas acabou não sendo particularmente proveitoso. Hoje, conjuntos finitos de linguagem desempenham o papel de eventos definidos como base para eventos regulares.

O termo preferido na álgebra é "racional" tanto para a classe de idiomas de Kleene quanto para os semigrupos e monóides mais gerais. Esse uso também reflete uma analogia importante entre o termo "racional" na álgebra como solução de uma equação linear com coeficientes inteiros e o conceito de séries de potências racionais na teoria dos autômatos e da linguagem formal.

Informação adicional. O artigo original de Kleene de 1951, intitulado "Representação de eventos em redes nervosas e autômatos finitos" pode ser encontrado aqui . Na p. 46 estabelece a arbitrariedade do termo "regular" com esta afirmação:

Neste momento, descreveremos uma classe de eventos que chamaremos de "eventos regulares". (Gostaríamos de receber sugestões sobre um termo mais descritivo.)

Aparentemente, ninguém apresentou um termo mais descritivo. ;-)

Como costuma ser o caso de artigos seminais que levam ao desenvolvimento intensivo de áreas totalmente novas, a terminologia e os conceitos são quase irreconhecíveis nos termos atuais. Primeiro, o artigo tratava de modelos de neurônios, daí o uso de "eventos" em vez de "idiomas" ou "conjuntos". O termo "eventos" persistiu até as décadas de 60 e 70, mesmo depois da importância dos conceitos de Kleene para autômatos e linguagens formais superarem amplamente qualquer valor para a neurociência.

$a^*b$$a^*$$a^+$que usamos hoje. A motivação de Kleene era evitar a corda vazia (ou evento com duração zero em seus termos). Essa foi uma intuição extraordinariamente presciente, uma vez que a teoria subsequente mostrou quão crucial é a escolha de incluir ou excluir a cadeia vazia das definições em muitos contextos. Terceiro, Kleene definiu um conceito chamado "eventos definidos" e desenvolveu eventos regulares a partir deles, mas hoje em dia usamos conjuntos finitos para esse fim. Eventos definidos foram estudados por um tempo, mas se revelaram muito menos importantes que eventos / conjuntos / idiomas regulares.

De qualquer forma, uma leitura completa deste artigo provavelmente não vale o tempo de ninguém hoje, exceto para fins históricos. Eu apenas procurei as definições e idéias cruciais, e isso foi divertido.

Eu sempre entendi o termo "regular" como significando que ele se baseia em um padrão que se repete. Depois de enumerar todas as seqüências de caracteres de um determinado comprimento, você as viu todas. Não haverá nada de novo depois.

(É apenas uma intuição vaga, é claro.)